Given a private key, is it possible to derive its public key?

Question

From whatever little I understand by reading various material, public-private key pair are the basis of asymmetric encryption and also something about choosing 2 prime numbers (which is roughly your private key) and multiplying them (which is roughly your public key). It appears to me that it is possible to generate a public key if you know the private key. Is it correct or I am mistaking something?

What made me more confusing was that it is not possible to serialize the RSA key to XML with only private key (using .NET class RSACryptoServiceProvider). Not sure whether this limitation is intentional or not!

Answer 1

In most asymmetrical crypto system implementation, the only fact that is ensured is that you cannot find the private key from the public key. The other way round, finding the public key from the private key is trivial in most case.

For instance, in RSA, you can create public key from private key with:

openssl rsa -in private.pem -pubout -out public.pem 

What is misleading is the terminology: "private key" refers to 2 different concepts whether you are speaking of the theory, or wether you are speaking of practical implementation:

• The theoretical private key is the couple (d, n) which shares perfect symmetrical (mathematical) relation with (e, n). If you are comparing these, one cannot be computed from the other.
• The practical private key (as in openssl implementation for example), refers to a file containing (d, n) but also several important intermediate values for decoding speed purpose. In addition to that, the theoretically "unknown" part of the public key e is often fixed to common values by convention (which is 0x10001 by default in openssl and albeit it can be changed, it is strongly recommended to stick to only very specific values). So deducing the public key (e, n) from the private key is trivial for more than one reason.

Answer 2

That depends on the crypto system.

In RSA, we have (citing Wikipedia):

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.

Now if we have n and d (the private key), we are only missing e for the public key. But e is often fairly small (less than three digits), or even fixed (a common value is 65537). In these cases getting the public key is trivial.

For Elliptic Curve Diffie-Hellman, the private key is d, and the public key dG (with G also public), so it's trivial as well.