2
$\begingroup$

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

$\endgroup$
  • $\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. Dec 11 '15 at 12:25
  • $\begingroup$ Hint: $(2^{100} \cdot m)^e = (2^{100})^e \cdot m^e$ $\endgroup$ – poncho Dec 11 '15 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 Dec 11 '15 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 Dec 11 '15 at 14:11
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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