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.

Is it possible to pre-choose a private RSA key, then obtain a public key from it?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Yes, in general the private key is generated at the same time as the public key in RSA, first the $p$, $q$ primes, then $n = pq$, then the public exponent $e$ and finally the private exponent $d$.

If the private key is given as $(p, q, d$) then you can recover the public key easily. As long as you know the public exponent and $n$, you have the public key (and this means that if you cannot guess $e$, you need $d$ and the factorization of $n$, this is an instance of the RSA problem).

However, as @fgrieu points out, if the private key is stored as $(n, d)$ and $e$ is not conventionally chosen and unknown, then the public key is lost and cannot be obtained from the private key.

The opposite (private key from public key) is meant to be infeasible though.

share|improve this answer
    
"... corresponding public key from it", except that we generally determine $e$ before $d$. $\hspace{1 in}$ –  Ricky Demer Jun 12 '13 at 9:26
    
@RickyDemer That is true. So it seems we actually determine half of the private key and half of the public key, then derive the missing halves. –  Thomas Jun 12 '13 at 9:32
1  
The method in this answer will not work if the private key is supplied as $(n,d)$. And there is no method that will work if $e$ is unknown, large, and random. –  fgrieu Jun 12 '13 at 13:51
    
@fgrieu If $e$ is unknown, large, and random, then it's not really public, is it? I will update nonetheless –  Thomas Jun 12 '13 at 13:54
1  
@Thomas: Two more nitpicks: 1) Most implementations choose $e$ before $(p,q)$. 2) If the private key is given as $(p,q,d)$, a working public key $(n,e)$ can be obtained (thus the answer to the question is yes); but any among several $e$ work, as long as $e\cdot d=1\pmod{\operatorname{lcm}(p-1,q-1)}$; so if $e$ is large and random, one can not necessarilly pinpoint the public key as $(n,e)$, as in the wording of the current answer. Which public key is used is very relevant, because revealing two different working public keys allows factorization of $n$. –  fgrieu Jun 12 '13 at 14:46
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.