# How to recover small messages from textbook RSA?

In the answer to the question Random unique key per message, safe to use key as IV? it was claimed that one can recover a random 128-bit textbook-RSA encrypted value using about $2^{64}$ steps.

How and why does this attack work?

Disclaimer: I did not come up originally with this attack, but rather it was first described in "Why Textbook ElGamal and RSA Encryption Are Insecure" by Boneh, Joux and Nguyen (PDF).

This answer will give a summary of the attack, similar to what is documented in Introduction to Modern Cryptography by Katz and Lindell.

First for the actual attack:
Let $c=m^e\bmod N$ be given as well as $(N,e)$ and let $m<2^l$ for some $l\in\mathbb N$. Then there exists $m=r\cdot s$ with $r,s<2^{\alpha\cdot l}$ for some $1/2<\alpha<1$ with decent probability:

1. Set $T:=2^{\alpha\cdot l}$.
2. For all $r$ from $1$ to $T$ compute and store $x_i=r^e\bmod N$.
3. Sort the pairs $(r,x_i)$ by the second component.
4. For all $s$ from $1$ to $T$ check (e.g. using binary search) whether $c\cdot s^{-e}\bmod N=x_i$ for some $i$, if so return $r\cdot s \bmod N$ as the message $m$.

(If $s^{-e}$ cannot be computed, then $s$ shares a non-trivial common divisor with $N$, and so one can trivially factor $N$ by calculating $\gcd(s,N)$.)

Now for the run-time of this algorithm: One needs about $2^{\alpha\cdot l}$ modular exponentiations for step 2, $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step three and about $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step four. So overall one does get away with "little more" than $2^{\alpha\cdot l}$ steps. Given that there's at least some chance (a few percent) that $\alpha=1/2$ will work, this would result in an attack with about $2^{l/2}$ run-time.

Note that steps 1 to 3 above don't depend on the ciphertext $c$, so they can be done in advance, and the resulting table reused for several ciphertext.

As for why this attack works, note that we effectively brute-force factor the message by exploiting the homomorphic property of RSA and that $c=m^e=(rs)^e=r^es^e\bmod N$.

• The details of the probabilities that certain $\alpha$ will work are documented in the linked paper. – SEJPM Dec 28 '16 at 15:58
• Would it not be more convenient to store $x_i = r^e \bmod N$ in the table, and look up $c \cdot s^{-e} \bmod N$ for each $s$? That way, the table can be precomputed once and reused for multiple messages. In fact, at a glance, that seems to be what the attack in section 5 of the linked paper is actually doing. – Ilmari Karonen Dec 28 '16 at 20:26
• @IlmariKaronen I CW'ed the A (originally planned to do it, then thought the other way and finally forgot that I made just about 0 contribution here). Feel free to optimize it :) – SEJPM Dec 28 '16 at 21:37