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.

I know that the public exponent is always a prime, but what about the private exponent? Is it always a prime too?

share|improve this question
4  
The public exponent doesn't have to be a prime. –  Thomas May 14 at 23:54
    
The exponent has to be coprime to the totient $\phi(n)$. And then the private exponent will also be coprime to $\phi(n)$. –  tylo May 15 at 14:30
add comment

1 Answer 1

up vote 5 down vote accepted

Actually, the public exponent doesn't have to be prime; any odd number works just fine there. The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement.

Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make sure that $p-1$ and $q-1$ are both relatively prime to the public exponent $e$. If the public exponent $e$ happens to be prime, then this is equivalent to saying that $p \ne 1 \pmod e$ and $q \ne 1 \pmod e$; these can be easy tests to fold into the prime search. If $e$ is composite, then the conditions are slightly more complex -- certainly not impossible to accomplish, to be sure.

That said, the private exponent need not be a prime number. All the private exponent $d$ is is a number such that $de \equiv 1 \pmod{ \operatorname{lcm}(p-1, q-1) }$; $d$ will always be odd, but there's no specific reason why it can't be (say) a multiple of 3.

share|improve this answer
1  
Specifically, $d$ is going to be an integer such that $ed - 1 = k\cdot \mathrm{lcm}(p - 1, q - 1)$ for some integer $k$, that is, $d = \frac{k \cdot \mathrm{lcm}(p - 1, q - 1) + 1}{e}$, so, really, its prime factorization could be anything, except it will always be coprime to $\mathrm{lcm}(p - 1, q - 1)$, that's about all you can say. –  Thomas May 15 at 22:30
1  
@Thomas: indeed, you expressed it better than I did –  poncho May 16 at 0:53
add comment

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.