attacking RSA via lattice reductions (LLL)
This repo host implementations and explanations of different RSA attacks using lattice reduction techniques (in particular LLL).
First, we'll see how Coppersmith found out that you could use lattice reduction techniques to attack a relaxed model of RSA (we know parts of the message, or we know parts of one of the prime, ...). And how Howgrave-Graham reformulated his attack.
Second we'll see how Boneh and Durfee used a coppersmith-like attack to factor the RSA modulus when the private key is too small (
d < N^0.292). Followed by a simplification from Herrman and May.
If you want to use the implementations, see below for explanations on Coppersmith and Boneh-Durfee. If you want to dig deeper you can also read my survey or watch my video.
I've also done some personal researches on the Boneh-Durfee algorithm and they are being used in
boneh_durfee.sageby default, just use
helpful_only = Falseto disable the improvements. I talk quantitatively about the improvements here.
The latest research on the subject is:
I've implemented the work of Coppersmith (to be correct the reformulation of his attack by Howgrave-Graham) in coppersmith.sage.
I've used it in two examples in the code:
For example if you know the most significant bits of the message. You can find the rest of the message with this method.
The usual RSA model is this one: you have a ciphertext
ca modulus
Nand a public exponent
e. Find
msuch that
m^e = c mod N.
Now, this is the relaxed model we can solve: you have
c = (m + x)^e, you know a part of the message,
m, but you don't know
x. For example the message is always something like "the password today is: [password]". Coppersmith says that if you are looking for
N^1/eof the message it is then a
small rootand you should be able to find it pretty quickly.
let our polynomial be
f(x) = (m + x)^e - cwhich has a root we want to find
modulo N. Here's how to do it with my implementation:
dd = f.degree() beta = 1 epsilon = beta / 7 mm = ceil(beta**2 / (dd * epsilon)) tt = floor(dd * mm * ((1/beta) - 1)) XX = ceil(N**((beta**2/dd) - epsilon)) roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
You can play with the values until it finds the root. The default values should be a good start. If you want to tweak: * beta is always 1 in this case. *
XXis your upper bound on the root. The bigger is the unknown, the bigger XX should be. And the bigger it is... the more time it takes.
Another case is factoring
Nknowing high bits of
q.
The Factorization problem normally is: give
N = pq, find
q. In our relaxed model we know an approximation
q'of
q.
Here's how to do it with my implementation:
let
f(x) = x - q'which has a root modulo q
beta = 0.5 dd = f.degree() epsilon = beta / 7 mm = ceil(beta**2 / (dd * epsilon)) tt = floor(dd * mm * ((1/beta) - 1)) XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000 roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
What is important here if you want to find a solution:
q >= N^beta
XXis the upper bound of the root, so the difference should be: |diff| < X
note:
diff = |q-q'|
The implementation of Boneh and Durfee attack (simplified by Herrmann and May) can be found in boneh_durfee.sage.
The attack allows us to break RSA and the private exponent
d. Here's why RSA works (where
eis the public exponent,
phiis euler's totient function,
Nis the public modulus):
ed = 1 mod phi(N) => ed = k phi(N) + 1 over Z => k phi(N) + 1 = 0 mod e => k (N + 1 - p - q) + 1 = 0 mod e => 2k [(N + 1)/2 + (-p -q)/2] + 1 = 0 mod e
The last equation gives us a bivariate polynomial
f(x,y) = 1 + x * (A + y). Finding the roots of this polynomial will allow us to easily compute the private exponent
d.
The attack works if the private exponent
dis too small compared to the modulus:
d < N^0.292.
To use it:
look at the how to use section at the end of the file in boneh_durfee.sage and replace the values according to your problem: the variable
deltais your hypothesis on the private exponent
d. If you don't have
d < N^deltayou will not find solutions. Start small (delta = 0.26) and increase slowly (maximum is
0.292)
Run the program. If you get an error: "Try with highers m and t" you should increase
m. The more you increase it, the longer the program will need to run. Increase it until you get rid of the error.
If you do not want to increase
m(because it takes too long for example) you can try to decrease
Xbecause it happens that it is too high compared to the root of the
xyou are trying to find. This is a last recourse tweak though.
If you still don't find anything for high values of
delta,
mand
tthen you can try to do an exhaustive search on
d > N^0.292. Good luck!
Once you found solutions for
xand
y, you can easily insert them into the equation:
e d = x [(N + 1)/2 + y] + 1
The example in the code should be clear enough, there is also a write-up of a CTF challenge using this code.
PS: You can also try to use
research.sage. It tries to remove unhelpful vectors when it doesn't break the triangular form of the lattice's basis. It might help you to use a lower
mthan necessary!