7
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ @JanDvorak Just comparing the modulus would do it. And searches on the internet have been performed. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 6, 2013 at 22:22

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Evil Washing Machine
    Commented Jan 7, 2013 at 21:28
  • 1
    $\begingroup$ @SchwitJanwityanujit: I have never heard about such a case for a real RSA key. $\endgroup$
    – poncho
    Commented Jan 7, 2013 at 21:38
  • 1
    $\begingroup$ Could one create such a key pair intentionally? $\endgroup$
    – Paŭlo Ebermann
    Commented Jan 12, 2013 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
    Commented Jan 12, 2013 at 21:41
-5
$\begingroup$

Ciphertext C= 10 sent to user whose public key is e= 5, n = 35 if you calculate d, it will be 5, i.e. e= d = 5.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The question asks "is it possible for big prime numbers?" and "Is this possible in industry?". This answer does not touch this. $\endgroup$
    – fgrieu ♦
    Commented Sep 5, 2023 at 13:41

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.