Feasibility of finding public key when private key is known

Question

We all know that in a public key cryptosystem, given a public key it is extremely hard to compute private key from it.

Is it the same case in reverse?

Given a private key, how easy is it to compute public key out of it?

It would be great to have answers with respect to an algorithm like RSA.

Answer 1

In practice, no.

Firstly, RSA private keys are typically stored together with the public exponent. The standard definition includes the following information:

RSAPrivateKey ::= SEQUENCE {
  version           Version, 
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1) 
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL 
}

Obviously, if this is the information you got, deriving the public key is just a matter of extracting the fields modulus and publicExponent.

Secondly, the public exponent is typically a small pre-defined value, selected for making the public key operation as efficient as possible. Even if all information you got in the private key is modulus and privateExponent, it would be trivial to test the two most common publicExponent values $3$ and $65537$ and see if they check out. If not, the publicExponent is rarely greater than $2^{32}$, so checking every such odd value would still be feasible.

Checking if a known privateExponent matches a guessed publicExponent, is typically just a matter of performing a RSA encryption of arbitrary data with one key, and test if the resulting cipher text can be decrypted with the other.

Thirdly, should the publicExponent deliberatly be selected as a random value roughly the same size as the modulus, then deriving publicExponent from privateExponent and modulus, would indeed be as hard as deriving privateExponent from publicExponent and modulus. This is however not how RSA is typically used or how RSA keys are typically generated.

Answer 2

We all know that in a public key cryptosystem, given a public key it is extremely hard to compute private key from it.

Is it the same case in reverse?

Not in general. For example, in Diffie-Hellman the public key is just a constant raised to a private number, modulo another constant. In some elliptic curve algorithms, the public key is a curve element multiplied by the private key.

It would be great to have answers with respect to an algorithm like RSA.

In the case of RSA, there are several possible answers, depending on the circumstances:

1. If the private key includes the prime(s), as is common, you can derive the public exponent from the private just like the reverse is done during key generation.
2. Even if not, you can usually test a few likely public exponent values, like 3 and 65537, because it is usually chosen to be one of those. If one of them works as the public key, then that's it.
3. If the public exponent was chosen randomly and the primes are not known, then computing the private from the public is just as difficult as the reverse.

Answer 3

Theoretically there is no requirement for the public key to be hard to guess given the private key. The public key is assumed to be known by all parties, including the adversary, so there is usually not much point in making it hard to guess.

In fact, the question depends a lot on what you define as the private and public keys:

For example it is not uncommon in theoretical constructions to define the private key as the randomness used by the key generation algorithm. In this case the private key completely specifies the public key.

Sometimes private keys are defined more arbitrarily, to be just some information that needs to be secret. When this type of definition is used, you may actually need to know the public key to decrypt. With this type of private key part of the public key can be picked independently from the private key, so it may be hard to guess given the private key. Consider for example the LWE based public key encryption scheme described here, https://en.wikipedia.org/wiki/Learning_with_errors#Public-key_cryptosystem. Here the public key is clearly hard to guess given only the private key.