The relationship between a private and public key? It's known that the relationship between public and private key allows data encrypted by the public key to be decrypted only by the corresponding private key.

As I understand it, this means that normally there is a relation between them (regarding obtain one from the other). 

But I found this:


  It is almost impossible to obtain the private key from the public key.


My question is how a private key can decrypt data encrypted with a public key, without it being possible to obtain the private key from the public key, since there has to be a relationship between them for decryption to work?
We'll assume RSA rather than elliptic curve, just because it's simpler.

A key consists of a modulus and an exponent. Both the public and private key use the same modulus, what differs is the exponent. To encrypt (or decrypt) you take your message, raise it to the power of the exponent, divide the modulus, and the remainder is your encrypted (or decrypted) answer.

How to generate your key

You start with two random prime numbers ("p" and "q"), if you have a 2048-bit key, then P and Q are both 1024 bits long. You multiply them together; that's your "modulus" -- the unique part of your public key. The other part of your public key (the "exponent") doesn't need to be unique, but it should be prime; most people just use 65537 because it's safe enough, and it makes your implementation fast.

Now let's figure out the corresponding private key. All you need to do is find the modulo multiplicative inverse of your public exponent with respect to (p-1) times (q-1). The math is simple, but not important here; it's just a simple calculation. That result you get, that's your private exponent; that's the "secret" part about your private key. You're done with P and Q now, throw 'em away.

So encrypt/decrypt a value: raise the value to either your public exponent or private exponent, divide by your modulus (same modulus for both keys) and the remainder is your answer.

Now let's try to attack it

I have the public key (which consists of the number 65537 as well as the modulus (P * Q) and what I'm trying to figure out is the number derived from (P-1) * (Q-1). If I knew what P and Q were, that would be dead-simple. But I don't. Instead, I know what P * Q is.

This is why people say that breaking RSA just boils down to factoring large numbers. Because if I could factor P * Q into P and Q, then I could re-derive the private key.

How are the keys related

The link between the two is this multiplicative inverse thing; it's like how 2 is linked to 1/2 and 13 is linked to 1/13. One can undo the other. Except that the relationship only exists in this finite field defined by the modulus. This is that wrap-around math world which is a lot like dealing with time on a clock -- where 10 plus 3 is 1 instead of 13 (because the clock only goes up to 12).

So to calculate that inverse relationship directly from the public key, you'd end up having to try to compute it over and over, with 1 trip around the clock, two trips, three, and so on until you got an answer that works. This turns out taking more time than the factoring challenge, so everybody just sticks to factoring.



This post contains mild technical inaccuracies mostly for brevity and simplicity. Feel free to leave a comment if you're the type of person who likes to argue on the Internet for fake points, but you will likely be summarily ignored.