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$)?

  • $\begingroup$ 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. $\endgroup$
    – Artjom B.
    Commented Dec 11, 2015 at 12:25
  • $\begingroup$ Hint: $(2^{100} \cdot m)^e = (2^{100})^e \cdot m^e$ $\endgroup$
    – poncho
    Commented Dec 11, 2015 at 13:47
  • $\begingroup$ @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$ ? $\endgroup$
    – fgrieu
    Commented Dec 11, 2015 at 14:04
  • 2
    $\begingroup$ @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 $\endgroup$
    – poncho
    Commented Dec 11, 2015 at 14:11

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.