Alice wants to send Bob a message of the form
or
In these cases, the message is of the form
for some integer . We’ll present an attack that works when the encryption exponent is small.
Suppose Bob has public RSA key . Then the ciphertext is
We assume that Eve knows , and , so she only needs to find . She forms the polynomial
Eve is looking for such that . In other words, she is looking for a small solution to a polynomial congruence .
Eve applies the LLL algorithm to the lattice generated by the vectors
This yields a new basis , but we need only . The theorem in Subsection 23.2.2 tells us that
We can write
with integers and with
It is easy to see that
Form the polynomial
Then, since the integer satisfies and since the coefficients of and are congruent mod ,
Assume now that
Then
where the last inequality used the Cauchy-Schwarz inequality for dot products (that is, ). Since, by (17.3) and (17.4),
we obtain
Since , we must have . The zeros of may be determined numerically, and we obtain at most three candidates for . Each of these may be tried to see if it gives the correct ciphertext. Therefore, Eve can find .
Note that the above method replaces the problem of finding a solution to the congruence with the exact, non-congruence, equation . Solving a congruence often requires factoring , but solving exact equations can be done by numerical procedures such as Newton’s method.
In exactly the same way, we can find small solutions (if they exist) to a polynomial congruence of degree , using a lattice of dimension . Of course, must be small enough that LLL will run in a reasonable time. Improvements to this method exist. Coppersmith ([Coppersmith2]) gave an algorithm using higher-dimensional lattices that looks for small solutions to a monic (that is, the highest-degree coefficient equals 1) polynomial equation of degree . If , then the algorithm runs in time polynomial in and .
Let
(which happens to be the product of the primes and , but Eve does not know this). Alice is sending the message
where ** denotes a two-digit number. Therefore the message is where and . Suppose Alice sends the ciphertext . Eve forms the polynomial
where
Note that .
Eve uses LLL to find a root of . She lets and forms the vectors
The LLL algorithm produces the vector
Eve then looks at the polynomial
The roots of are computed numerically to be
It is easily checked that , so the plaintext is
Of course, a brute force search through all possibilities for the two-digit number could have been used to find the answer in this case. However, if is taken to be a 200-digit number, then can have around 33 digits. A brute force search would usually not succeed in this situation.