When encrypting a small value $m\in\{1,\dots,100\}$ using textbook RSA, and since that is deterministic, an attacker could try every possible number to determine $m$.

To prevent this kind of attack, one could select a big random number $x$, and send $x^e\bmod n$ and $(m+x)^e\bmod n$.

What would be a problem with this encryption technique?


If $e$ is "small" (as all typical values of $e$ are!), this is vulnerable to the Franklin-Reiter related message attack.

In a nutshell, given $c_1=x^e\bmod n$ and $c_2=(x+m)^e\bmod n$, for each possible value of $m$, compute $$f:=\gcd(y^e-c_1,(y+m)^e-c_2)$$ in the polynomial ring $(\mathbb Z/n)[y]$. If you guessed the right $m$, then (possibly except for very rare cases) $$f=y-x\in(\mathbb Z/n)[y]$$ and you have recovered $x$ and verified that $m$ was correct. Otherwise, $f$ will most likely be $1$. Note that this $\gcd$ is technically not well-defined in all cases, but if you actually encounter a problem with that, you have effectively factored $n$.

Of course, this assumes that $e$ is small enough for this $\gcd$ computation to be feasible, and that the set of possible messages $m$ is small enough to be brute-forceable.

| improve this answer | |
  • $\begingroup$ And I just found out that SAGE is unable to natively compute GCD in a polynomial ring with composite characteristic. Ideas/other SW ? (except writing a custom GCD) $\endgroup$ – Ruggero Jun 6 '17 at 16:39
  • $\begingroup$ @Ruggero: Mathematica has PolynomialGCD with a Modulus option, but it has the same limitation that the modulus is expected to be prime. $\endgroup$ – fgrieu Jun 6 '17 at 17:16
  • $\begingroup$ At the end I implemented a super basic GCD in Sage to test this solution (spoiler: it works as expected). Anyone interested can find it here $\endgroup$ – Ruggero Jun 7 '17 at 11:47

Compared to regular RSA (textbook or with random padding of $m$ into a single large value, e.g. sending $(2^{8}x+m)^e\bmod n$ with random $x<2^{-9}n$, or using RSA-OAEP), some issues are that:

  • encryption and decryption require twice more modular exponentiation work;
  • ciphertext size is doubled;
  • the classical RSA problem of finding random $x<n$ given $x^e\bmod n$ does not seem reducible to the problem of finding $m$ under this proposed system (such reduction would prove the security of the proposed system under a commonly accepted hypothesis).

I do not rule out security issues, perhaps devastating; but fail to spot one.
Update: there is one! See this other answer!!

| improve this answer | |
  • 1
    $\begingroup$ Hey fgrieu, about the third point you wrote: If we had an oracle $\mathcal{O}$ to solve the RSA problem as you formulated, we could recover $m$ by calculating $\mathcal{O}\left( (m+x)^e \right)$ - $\mathcal{O}(x^e)$, right? $\endgroup$ – Hilder Vitor Lima Pereira Jun 6 '17 at 11:16
  • $\begingroup$ @Vitor: Yes. I meant the opposite of what I originally wrote. That's fixed now, thanks for correcting me. $\endgroup$ – fgrieu Jun 6 '17 at 11:21

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.