Can e = 2 be used in unpadded RSA?

I am wondering whether $e = 2$ can be used in unpadded RSA... It seems like it is not possible to use it: the value of e needs to be coprime with $tot(n)$. $tot(n) = (p - 1)(q - 1)$ where $p$ and $q$ are prime numbers.

The way I see it, there are two scenarios.

1) Neither $p$ nor $q$ are equal to $2$. This means they are odd. The product of $(p - 1)(q - 1)$ would be even i.e. not coprime with $2$.

2) Let's say $p = 2$ and $q$ is any prime greater than $2$. This would give $tot(n) = 1(q - 1)$ and since we know that $q$ is odd, the result will be even anyway.

Is there something I am overlooking here or is my reasoning correct?

The encryption in the Rabin cryptsystem is basically textbook RSA with an exponent of $2$.

1) Neither p nor q are equal to 2. This means they are odd. The product of (p−1)(q−1) would be even i.e. not coprime with 2.

Well, yes. That is one of the basic problems in Rabin's cryptosystem. If we want that $$c=m^e$$ is a bijection, $e$ has to be coprime to the order of the multiplicative group. In your scenarios you realized, for normal RSA-moduli this is not true for $e=2$(and $N=2\cdot p$, with $p$ prime, is quite useless cryptographically).

Soo... why are there 4 square roots then? Let's look at the square roots of $1$ for simplicity. Now we could have the following solutions:

$$x_1 = 1 \mod p; x_1=1 \mod q$$ $$x_2 = 1 \mod p; x_2=-1 \mod q$$ $$x_3 = -1 \mod p; x_3=1 \mod q$$ $$x_4 = -1 \mod p; x_4=-1 \mod q$$

With the help of the Chinese Remainder Theorem we can calculate those four solutions mod $N=pq$. For arbitrary elements, this works pretty much the same: Calculate the roots in both $\mod p$ and $\mod q$, then combine the result. And this is the decryption in Rabin.

So with $e=2$ we get 4 possible roots. But the choice which root was the correct one has to be done outside the encryption scheme.

As a final note, there is a crucial difference between RSA and Rabin, when it comes to security property:

• If you have a decryption oracle, then the result of the Rabin decryption (even if it just outputs one of the roots every time), reveal the integer factorization. How to do this: Pick a random number, square it and give it to the oracle. The oracle can't know which of the roots you started with and will return a random root. In 1/2 of the cases this reveals the factorization.
• This means, that breaking Rabin is actually equivalent to factorization (unknown for RSA). Thus making it "stronger".
• On the other hand, a decryption oracle for RSA does not reveal the factorization (as far as we know yet).
• For IND-CPA security, Rabin as well as plain RSA are insecure. However, with a proper padding scheme RSA can be made IND-CPA. For Rabin we can apply adaptions (e.g. redundancy or error detection codes), but so far it is unknown if those are CPA secure.

As a final note for RSA: Knowing both $e$ and $d$ is deterministic polynomial to factorization. What is unknown: Can a decryption oracle (with $d$ fixed) help you find $d$ in polynomial time (or equivalent information, e.g. a nontrivial root of $1$, a zero divisor, etc.)

RSA with $e = 2$ is Rabin, it works a bit differently and is slightly more mathematically involved, but it is a valid cryptosystem.

• Decryption is not unique (as there are two square roots), so you do need some way to tell the real message from another root. So unpadded RSA, where any number < $N$ can be a message, seems a problem for a Rabin scheme. Nov 2 '15 at 9:48
• @HennoBrandsma Hence "it works a bit differently." ;) Of course "RSA with $e = 2$ is Rabin" was not to be taken literally. Nov 2 '15 at 9:49
• He was asking about unpadded RSA, so I saw some issues... Nov 2 '15 at 9:50
• There are in general not only two but 4 square roots.
– user27950
Nov 2 '15 at 11:47
• @HennoBrandsma Is "A boy called Evelyn" a new song by Johny Cash? Nov 7 '15 at 13:36