Introduction to Cryptography with Coding Theory, 3rd Edition

23.3 An Attack on RSA

Alice wants to send Bob a message of the form

$$Theansweris\mathit{\ast }\mathit{\ast }$$

or

$$Thepasswordforyournewaccountis\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{\ast }\mathit{.}$$

In these cases, the message is of the form

$$m=B+x\text{,}\text{ where }B\text{ is fixed and }|x|\le Y$$

for some integer $Y$. We’ll present an attack that works when the encryption exponent is small.

Suppose Bob has public RSA key $(n\text{,}e)=(n\text{,}3)$. Then the ciphertext is

$$c\equiv (B+x{)}^3(\text{mod}n)\text{.}$$

We assume that Eve knows $B\text{,}Y$, and $n$, so she only needs to find $x$. She forms the polynomial

$$\begin{array}{lll}f(T)\hfill & =\hfill & \text{}{(B+T)}^3-c=T^3+3B{T}^2+3B^{2}T+B^3-c\hfill \\ \equiv \hfill & T^3+a_2{T}^2+a_{1}T+a_0(\text{mod}n)\text{.}\hfill \end{array}$$

Eve is looking for $|x|\le Y$ such that $f(x)\equiv 0(\text{mod}n)$. In other words, she is looking for a small solution to a polynomial congruence $f(T)\equiv 0(\text{mod}n)$.

Eve applies the LLL algorithm to the lattice generated by the vectors ...