Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Jan 7 '13 at 19:05

This question came from our site for professional and enthusiast programmers.

    
@JanDvorak Just comparing the modulus would do it. And searches on the internet have been performed. –  Maarten Bodewes - owlstead Jan 6 '13 at 22:22

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
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? –  Evil Washing Machine Jan 7 '13 at 21:28
1  
@SchwitJanwityanujit: I have never heard about such a case for a real RSA key. –  poncho Jan 7 '13 at 21:38
    
Could one create such a key pair intentionally? –  Paŭlo Ebermann Jan 12 '13 at 21:11
1  
@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$). –  poncho Jan 12 '13 at 21:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.