# Attack on textbook RSA with small messages

We learned in class that if Alice wants to send a small message $m$, such that $m < N^{\frac{1}{e}}$, so we can break the system using $e$-th square of $m^e$.

But what if Alice knows this flaw and decides to sent $2^{100}\cdot m$ as her message. Is an attacker can still break the system (I assume that the attacker knows that Alice sent $2^{100}\cdot m$)?

• Do you mean by 2^100*m: $2^{100}\cdot m$ or $2^{100\cdot m}$? (I hope I got it right.) Either way this is a form of a padding. A padding should probably depend on the size of the message. Dec 11, 2015 at 12:25
• Hint: $(2^{100} \cdot m)^e = (2^{100})^e \cdot m^e$ Dec 11, 2015 at 13:47
• @poncho: now it is me begging for an extra hint. Would your hint help an elementary attack (simpler than the LLL) for e.g. $e=17$, $\log_2(N)\approx 1024$, random 80-bit $m$ ?
– fgrieu
Dec 11, 2015 at 14:04
• @fgrieu: no, the straight-forward approach I eluded to wouldn't for an 80-bit $m$. However, a MITM approach would solve it (assuming you don't use random padding, which you should) in about $2^{40}$ time, which is certainly easier than LLL Dec 11, 2015 at 14:11

The attacker sees $E(2^{100}\cdot m) = (2^{100} \cdot m)^e \,(N) = 2^{100e} \cdot m^e \,(N)$. The attacker can compute $A = 2^{100e} \,(N)$ from public parameters, so he can also compute $A^{-1} \,(N)$ (if not he would already have a factor of $N$). So he then knows $m^e \,(N) = E(2^{100}\cdot m) \cdot A^{-1} \,(N)$ and you can apply the previous attack. This abuses the homeomorphic property of RSA.