How public and private keys work?

Question

I understand the basics. Public key can be used to encrypt data, but only private key can be used to decrypt it.
How is this possible? How can message be encrypted using public key and not be decrypted using that same key? And how can a private key be used to decrypt message that was not encrypted using different key?
People often use many analogies, but I am interested in how this mathematically even makes sense.
People say mathematics of this encryption system is too complex, but please try not to oversimplify too much. I will try to understand.

Answer 1

The two keys are mathematically related to each other, such that the same formula that encrypts a message (turns one big number into another) with one key can decrypt the message (turn a big number back into the original big number) with the other key. There's lots of exponents and modulo math going on but it makes sense once you strip out the computer science and math theory.



Take prime numbers P and Q, and multiply them to create rather large number N, which will be common to both the public and private keys.

Pick prime number E so that it is less than the least common multiple of P-1 and Q-1 (and also not a factor).

Calculate D based on E, P and Q. (I'm skipping the math, see Wikipedia.)

So now we have the very large number N, prime number E, and D which is magically related to E.



Let N and E be the public key, and N and D be the private key.



To encrypt plaintext message M, treat it as a number and raise it to the Eth power, and modulo it against N (repeatedly subtract N and keep the remainder), resulting in cryptogram C.



To decrypt cryptogram C, raise it to the Dth power and modulo it against N, resulting in the plaintext M.

Answer 2

It works because the encryption techniques used mean that even if you have the public key and the encrypted message you cannot use the public key to recreate the original unencrypted message - it's a one-way process (hopefully).

Answer 3

Keys,