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?


Adding some more information to fkraiem's answer:

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.

  • $\begingroup$ 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. $\endgroup$ Nov 2 '15 at 9:48
  • $\begingroup$ @HennoBrandsma Hence "it works a bit differently." ;) Of course "RSA with $e = 2$ is Rabin" was not to be taken literally. $\endgroup$
    – fkraiem
    Nov 2 '15 at 9:49
  • $\begingroup$ He was asking about unpadded RSA, so I saw some issues... $\endgroup$ Nov 2 '15 at 9:50
  • 2
    $\begingroup$ There are in general not only two but 4 square roots. $\endgroup$
    – user27950
    Nov 2 '15 at 11:47
  • $\begingroup$ @HennoBrandsma Is "A boy called Evelyn" a new song by Johny Cash? $\endgroup$
    – Maarten Bodewes
    Nov 7 '15 at 13:36

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.