I’ve implemented the work of Coppersmith (to be correct the reformulation of his attack by Howgrave-Graham) in Sage.
You can see the code here on github.
I won’t go too much into the details because this is for a later post, but you can use such an attack on several relaxed RSA models (meaning you have partial information, you are not totally in the dark).
I’ve used it in two examples in the above code:
Stereotyped messages
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 c a modulus N and a public exponent e. Find m such 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/e of the message it is then a small root and you should be able to find it pretty quickly.
let our polynomial be f(x) = (m + x)^e - c which 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.
* XX is 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.
Factoring with high bits known
Another case is factoring N knowing 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.
This is because x - q' = x - ( q + diff ) = x - diff mod q with the difference being diff = | q - 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:
- we should have
q >= N^beta
- as usual
XX is the upper bound of the root, so the difference should be: |diff| < XX
