Q: How to recover an ECDSA private key from biased nonces?

Biased nonces reduce to the Hidden Number Problem, solved as CVP on a lattice built from the signatures. With roughly one leaked bit per nonce you need about 100 signatures; a fully reused nonce needs only two signatures and direct algebra, no lattice.

Q: LLL vs BKZ: which lattice reduction should I use?

LLL runs in polynomial time and suffices for most CTF challenges, so start there. If LLL fails to produce a short enough vector, switch to BKZ with block size 20-40, which gives better approximation at exponential cost in the block size.

Q: Why does SageMath small_roots return an empty list?

Empty results usually mean the root bound X exceeds the Coppersmith limit N^(1/d), or beta is set incorrectly. Reduce X, increase epsilon toward 1/100, and use beta=0.5 when finding roots modulo an unknown factor p of size about the square root of N.

Q: When does the knapsack lattice attack work?

The low-density subset sum attack works when the knapsack density n / max(log2 ai) is below 0.9408. Build the CJLOSS embedding lattice with a scaling factor near sqrt(n)/2 and apply LLL; super-increasing knapsacks need only a greedy algorithm instead.

Question 1

How do I use Coppersmith's method to attack RSA with partial information?

Accepted Answer

Coppersmith's method finds small roots of a polynomial modulo N using SageMath's small_roots function. For a stereotyped message, model f = (known_msb + x)^e - c and call small_roots with X set to the unknown bit bound, which must satisfy X < N^(1/e).

Question 2

How to recover an ECDSA private key from biased nonces?

Accepted Answer

Biased nonces reduce to the Hidden Number Problem, solved as CVP on a lattice built from the signatures. With roughly one leaked bit per nonce you need about 100 signatures; a fully reused nonce needs only two signatures and direct algebra, no lattice.

Question 3

LLL vs BKZ: which lattice reduction should I use?

Accepted Answer

LLL runs in polynomial time and suffices for most CTF challenges, so start there. If LLL fails to produce a short enough vector, switch to BKZ with block size 20-40, which gives better approximation at exponential cost in the block size.

Question 4

Why does SageMath small_roots return an empty list?

Accepted Answer

Empty results usually mean the root bound X exceeds the Coppersmith limit N^(1/d), or beta is set incorrectly. Reduce X, increase epsilon toward 1/100, and use beta=0.5 when finding roots modulo an unknown factor p of size about the square root of N.

Question 5

When does the knapsack lattice attack work?

Accepted Answer

The low-density subset sum attack works when the knapsack density n / max(log2 ai) is below 0.9408. Build the CJLOSS embedding lattice with a scaling factor near sqrt(n)/2 and apply LLL; super-increasing knapsacks need only a greedy algorithm instead.

lattice-crypto-attacks

SYSTEM DOCUMENTATION & REQUIREMENTS

Frequently Asked Questions about lattice-crypto-attacks

Related Skills

rsa-attack-techniques

rsa-attack-techniques

lattice-crypto-attacks

lattice-crypto-attacks