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?


2 Answers 2


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.

  • $\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, 2017 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, 2017 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, 2017 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!!

  • 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$ Jun 6, 2017 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, 2017 at 11:21

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.