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

Question

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.

Answer 1

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.

Answer 2

No, the two are symmetrical (or interchangeable). So if it is hard to get the secret key from the public one, then it is equally hard to get the public from the private.

Answer 3

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

Answer 4

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).

Answer 5

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.