Given a private key, is it possible to derive its

Question

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

[EDIT]

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

public key is modulus N (and public exponent e, usually 65537), private key is given by the two primes p, q (and private exponent d, sometimes also CRT parts d_p, d_q for speedup) essentially you have N=pq and ed=1 mod ((p-1)(q-1)), you can also compute d_p and d_q using CRT given private key, computation of public key modulus is "boring" multiplication and public exponent is in specification or computed using extended euclid algorithm if standard e was not good enough. given public key, computation of private key requires either finding d (RSA problem) or p,q (factoring, see number field sieve for best algo to do this). These problems are shown to be equivalent under reasonable conditions [Breaking RSA Generically is Equivalent to Factoring, D. Aggarwal and U. Maurer, 2008]

Answer 2

In ANY public key crypto system the public key is mathematically related to the private key. It's very simple.

The public key is derived from the private key at generation time, and with the private key at any point in the future it is possible to re-derive the public key easily.

It is not feasible to go the other way. Given a public key it is not easy to derive the private key. That's why we can safely share public keys with other people. If you have enough time/CPU cycles you could brute force it but it's probably easier to wait for a mathematical attack on the key.

Answer 3

Yes with access to the private key the public key can be generated