# Encrypting a small value $m\in\{1,\dots,100\}$ using textbook RSA

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.

• 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) – Ruggero Jun 6 '17 at 16:39
• @Ruggero: Mathematica has PolynomialGCD with a Modulus option, but it has the same limitation that the modulus is expected to be prime. – fgrieu Jun 6 '17 at 17:16
• 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 – 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!!

• 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? – Hilder Vitor Lima Pereira Jun 6 '17 at 11:16
• @Vitor: Yes. I meant the opposite of what I originally wrote. That's fixed now, thanks for correcting me. – fgrieu Jun 6 '17 at 11:21