views:

1064

answers:

8

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!

A: 

If you are talking about RSA, yes. If you have enough computational power.

For some algorithms, this might be easier.

It's theoretically possible to compute the other key for every known asymmetric algorithm, but the key is that it requires too much computational power.

Mehrdad Afshari
-1: Calculating a public key from private key takes like seconds on an ordinary computer. So **enough** computational power is needed only to derive private key from public key. Both are not same.
Hemant
+2  A: 

It is theoretically possible but for large keys computationally infeasible.

Mark Probst
Can you explain this?
bowenl2
A: 

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

AnthonyWJones
Is it (your answer) applicable to RSA generally or specific to Microsoft CryptoAPI implementation (and the way it serializes the key to/from XML)?
Hemant
Actually this is not true either - they are both products of complex calculations.
AviD
The question was originally asked in principle, hence the answer is in princple. I don't know the internals of .NET encryption, however private keys may store the originating p and q. One should assume that a public key is derivable from a private key.
AnthonyWJones
+9  A: 

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.

sleske
In RSA, if we know d and n, we can compute p and q such that pq = n.With this, d and e are each other's inverses modulo (p-1)(q-1).
Henno Brandsma
@Henno Bransma: How do you compute "p and q such that pq = n"?
sleske
+1  A: 

see

http://www.danbrown.com/novels/digital_fortress/plot.html

very simple!

Adrian
Please tell me you're not quoting Dan Brown on a serious question about cryptography. Or at least tell me you're joking.
Joachim Sauer
I assumed it was a joke -- SO has no sense of humor (I've gotten downvoted for jokes as well)
Coderer
Yes - it is a Joke, sorry for any confusion caused!
Adrian
+3  A: 

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.

Adam Hawes
+4  A: 

It depends on the algorithm, and what you mean by "private key".

RSA private keys are often stored in their "Chinese Remainder Theorem" form. For example, the RSAPrivateKey structure defined in PKCS #1 and re-used by many other crypto standards take this form. This form includes the two secret numbers often denoted p and q, from which the totient is computed. With totient and the private exponent, the public exponent is quickly computed.

In any case, most RSA key pairs use 65537 as the public exponent, and the modulus is always carried as part of the private key.

erickson
+1  A: 

In most asymmetrical crypto system, 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.

in RSA, for example 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 fixed to a common value by convention (which is 0x10001 in openssl). So deducing the public key (e,n) from the private key is trivial for more than one reason.
  • vaab