# RSA: is it easy to find the public key from the secret key?

I know that it is not easy to find the secret key from the public key . Is it relatively easy to find the public key from the secret key for scientists in the field?

If the answer is yes then is there any cryptography system such that only a particular person can encode and any one in public can decode? For an example scenario , a king writes his order and encodes it using his (secret) public key . Then his soldiers decode the code using the (open) secret key to check if it was truly written by the king.

Thank you very much.

-

For standard uses of RSA, the secret key is hard to find, and the public key is trivial. This is because most implementations use 65537 as the public key (the reason has to do with its primality and the efficiency of repeated squaring for $e=65537=2^{16}+1$).

Many systems will rechoose $p$ and $q$ if $\phi(pq)$ is not coprime to 65537, meaning that the public exponent is never anything else.

Several other answers note that $e$ and $d$ are interchangeable, but this ignores both practice and several important cryptanalytic results. In particular, even if we allow $e$ to vary, it can still be found given $d$ if it's sufficiently small. This is due to the fact that Coppersmith's algorithm can find small roots of polynomials modulo a composite of unknown factorization using LLL and some added cleverness. The bound keeps increasing, but (from memory) I believe if $e < n^{.33}$ it can be found from $n$ and $d$ (here $n=pq$). So saying $e$ and $d$ are equivalent is false (and dangerous). There is a conjecture that the "true" bound is $n^{.5}$, meaning that for security the secret exponent would have to be above $\sqrt{n}$.

Note: For those truly interested, Boneh has a nice survey of these results (and many others). And it's quite readable by non-cryptographers who have a moderately strong math background.

-
"Many systems" will rechoose $p$ and $q$? I would hope all systems, otherwise nothing works at all! –  TonyK Jun 8 '11 at 7:47
I'm uncertain about the exponents of $n$, do you mean $\sqrt[3]{n}$ and $\sqrt{n}$? If so, you can use \sqrt[k]{n} for the $k$-th root on $n$. –  Asaf Karagila Jun 8 '11 at 12:57
@TonyK Some systems will try other $e$-values beside 65537 since this is faster than having to start all over with new $p$ and $q$ (whose generation is the slowest part of making RSA keys), but most systems will stick with $e=65537$ and just regenerate $p$ and $q$; these days even commodity computers are so fast you wouldn't notice the time-loss for even a 2048-bit modulus. –  Fixee Jun 9 '11 at 2:07
@Asaf: In the survey I linked in my answer, Boneh shows that if a known exponent is $< n^{0.292}$, you can efficiently obtain the other exponent. A more recent result lifts this bound to $n^{.33}$ (which is close to, but not exactly, $\sqrt[3]{n}$ of course). Boneh notes that the likely correct bound is $n^{0.5}$ but that it was still open at the time of the survey. AFAIK, this remains open. –  Fixee Jun 9 '11 at 2:15
Thank you very much for the answer. –  seven_swodniw Jun 13 '11 at 18:24

No, finding the secret key from the public key is just as hard, in the abstract, as finding the secret key from the public key.

What you suggest is in fact the standard way in which RSA is used for "signing" messages. In order to authenticate a message (to make sure the message was sent by me), I encode it using my private key, which means that anyone can use the public key to decode it and find out that it was truly sent by me (because, presumably, nobody knows my private key except me).

But this has nothing to do with whether one can obtain the public key from the secret key; it has to do with the way RSA works (the roles of the public and private key are symmetric).

-
Thank you for the answer. –  seven_swodniw Jun 8 '11 at 5:34

No - they are equally difficult to find. In particular, the encryption key and the decryption key are modular inverses. The difficulty in finding the decryption key from the public key lies in the fact that they're inverses... mod $\varphi (n)$, and so one must factor or be incredibly witty to find the inverse.

If one chose backwards, and distributed the 'decryption' key instead and kept the 'encryption' key for oneself, the security would be the exact same. (I put them in quotes to show that they were the original decryption and encryption keys).

But to your second question, there is a method similar to RSA called digital signatures, where only the person who knows the secret key can distribute a message that everyone in public can decode. It's called a signature because it guarantees authenticity

-
Thank you for the answer. –  seven_swodniw Jun 8 '11 at 5:34
@seven: no problem! (but we love upvotes and accepted answers, too - makes us feel special) –  mixedmath Jun 8 '11 at 5:35

It depends what you mean by "private key". If the private and public keys are $(n,d)$ and $(n,e)$, with $ed=1 \mod \varphi(n)$, then the other answers are correct - it's just as hard to get $d$ from $e$ as $e$ from $d$. But the key was generated as $n=pq$ for two primes $p$ and $q$, and in practice the numbers $p,q$ are saved along with the private key. (This allows much faster computations using the Chinese Remainder Theorem.) And if you know $p$ and $q$, then you can calculate $d$ from $e$ (or $e$ from $d$) easily -- it's just a modular inverse.

-
In fact, in the standards that are used for computers (like PKCS7, 8 etc) the public key is (essentially) $(n,e)$ while the private key (for RSA) is, besides the also allowed $(n,d)$, (essentially) $(n,e,d,p,q, d \mod{p-1}, d \mod{q-1}, q^{-1} \mod {p})$, a very redundant set, but as said, convenient for computations. The private key info should be stored encrypted anyway, and a few bytes more... –  Henno Brandsma Jun 8 '11 at 7:19
+1 Yes, exactly. Typically the primes p and q are stored in the secret private key file. The public key (n,e) is trivial to calculate from that: n = pq, and e is usually fixed at 65537. –  David Cary Jun 12 '11 at 15:35
Even if you don't know p or q, if you have the private key (n,d), the public key (n, e) is usually (n, 65537). Even when e is not 65537, e is almost always a small number (compared to d), so it almost always takes a short amount of time to find e by brute force testing all possible values. –  David Cary Jun 12 '11 at 15:47
Thank you very much for the answer. –  seven_swodniw Jun 13 '11 at 18:24