Rather, is it possible for big prime numbers?

Classroom examples usually involve smaller primes, so for example if you are given a prime number pair $p = 3$, $q = 13$ you would get $n = 39$ and $e = d = 5$, making encryption and decryption the same for a message $x$ or ciphertext $x$.

This can be a big problem, e.g. if a server sends you cipher $x$, you can decrypt it and get the message, then you encrypt the cipher $x$ itself and if you get the message again then you know the public key is the same as the private key.

Is this possible in industry?

  • $\begingroup$ @JanDvorak Just comparing the modulus would do it. And searches on the internet have been performed. $\endgroup$
    – Maarten Bodewes
    Jan 6 '13 at 22:22

No, the public and private exponents will never be the same for real (that is, not toy) RSA keys.

The public exponent is almost always be deliberately chosen as a small value (with 65537, 3 and 17 being the most popular choices). In contrast, the private exponent will always be a huge value; always at least $(p-1)/e$ (where $p$ is the larger prime factor of the modulus, and $e$ is the public exponent), and will generally (almost always) be much larger than that. This implies that if you have a 1024-bit RSA key, and a public exponent of 65537, then the private exponent will be at least 495 bits long.

Even if you (for some unknown reason) select a random large public exponent, then it is still extremely unlikely. If we look into the conditions that allow $d = e$, we see that both of the following must hold:

$e^2 \bmod (p-1) = 1$

$e^2 \bmod (q-1) = 1$

Having even one of $e^2 \bmod (p-1)$ and $e^2 \bmod (q-1)$ to be 1 is extremely unlikely; having both conditions happen is not something to worry about.

  • $\begingroup$ Thanks for your answer :) As a curious addendum, has there been a case where the public and private key ended up the same? If so, what happened? $\endgroup$ Jan 7 '13 at 21:28
  • 1
    $\begingroup$ @SchwitJanwityanujit: I have never heard about such a case for a real RSA key. $\endgroup$
    – poncho
    Jan 7 '13 at 21:38
  • 1
    $\begingroup$ Could one create such a key pair intentionally? $\endgroup$ Jan 12 '13 at 21:11
  • 3
    $\begingroup$ @PaŭloEbermann: sure, if one wanted to. The obvious way would involve selecting $p$ and $q$ such that $p-1$ and $q-1$ have known factorization; that'd make selecting the value $e$ straightforward ($e = 1, -1 \bmod r$ for every prime power factor of $p-1$ or $q-1$). $\endgroup$
    – poncho
    Jan 12 '13 at 21:41

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.