End-to-end encryption: How can a public key and a private key be different, yet compatible?

Question

Since the public key is used to encrypt the message and the private key is used to decrypt the message, then how is it possible for the private key and the public key to be compatible with each other? How can a green key unlock a red-locked door?

This is my way of thinking:

Hello is encrypted by the public key, becomes %/))=. The private key then decrypts the message. But since the keys are different, the resulting message may become different from what has been sent - &#(($, for example.

Of course, I know the encryption/decryption algorithm used in real life is different, but the question is comprehensible. How are the keys made such that one can only encrypt, and the other can only decrypt, while both having enough information so that they are compatible with each other? Is it the algorithm that handles this?

Answer 1

Public-key cryptography was first described by W. Diffie and M. Hellman in their groundbreaking paper "New Directions in Cryptography" (1976), in which they suggested that such system would be based on a trapdoor function. Such hypothetical function would be easy to calculate, but computing the inverse of it efficiently would require extra information, which would be the private key. (The paper is quite short and is worth reading in its entirety, rarely an 11-page paper contributes this much to its field.)

As mentioned in the other answer, one example of such function can be based on integer factorization problem: it's easy to multiply two primes, but there's no efficient (classical) algorithm to find the factorization of the product. Later, Rivest, Shamir and Adleman invented the first public-key algorithm based on that assumption (which is not proven, though quite plausible).

In short, you can take a pair of (e, N) to be a public key, where

• e is small prime number (quite often 65537)
• N is a product of two very large different primes p and q, such that gcd(e, φ(N))=1, where φ(N) = (p-1)*(q-1).

Then you can find d, such that:

cipher = plaintext ^ e mod N
plaintext = cipher ^ d mod N

This d is the private key. The trick here is that in order to find such d, it's necessary to know the factorization of N, i.e. p and q. (As @kelalaka pointed out in the comments and his post, the factorization may be not necessary to recover the plain text without a key, but nobody has found a way around it yet, so this is yet another assumption.) You can read more details in the RSA link above.

Answer 2

It's easy to do the math for RSA with pencil and paper. It doesn't provide any security, but it might help you understand how the public and private keys are different but work together.

Let's use a modulus, n = 143 with a public key, e = 7, and private key, d = 43. There's some "magic" in how these numbers are determined, and to provide real security, they'd need to be much, much bigger. The problem here is that 143 is part of the public key, and it's small enough to easily factor into the primes 11 and 13, which are the magic ingredients leading to the private key.

We can cipher numbers [0, n) with this key pair so we will substitute numbers 0–25 for letters A–Z.

RSA encryption is c = m^e mod n, where m is the "message," our coded letter, and c is the cipher text for that letter. Let's encrypt "HELO" letter by letter.

• H -> 7: 7⁷ mod 143 = 6
• E -> 4: 4⁷ mod 143 = 82
• L -> 11: 11⁷ mod 143 = 132
• O -> 14: 14⁷ mod 143 = 53

RSA decryption is m = c^d mod n

• 6⁴³ mod 143 = 7 -> H
• 82⁴³ mod 143 = 4 -> E
• 132⁴³ mod 143 = 11 -> L
• 53⁴³ mod 143 = 14 -> O

So, you can see the public key, 7, is different than the private key, 43, but they work together with the modulus, 143, under modular exponentiation to provide a reversible transformation.

Here's the "magic" used to come up with a key pair that works together.

1. Choose two primes: p = 11, q = 13
2. Compute the modulus: n = p x q = 143
3. Compute the totient: λ(n) = lcm(p - 1, q - 1) = lcm(10, 12) = 60
4. Choose public key e that is coprime with λ(n): e = 7
5. Determine private key d: d = e^-1 mod λ(n) = 43

Answer 3

I think you're misconceptialising it slightly; it's not like you'll get a wrong answer by trying to decrypt it by the wrong key, you won't be able to get a valid solution at all...

If you multiply 2 prime numbers (1 is the private key, the other is the public key) then the only thing it will be divisible by is itself, 1 and the 2 primes.

While you can go through every prime number to figure out which ones it's made of (by checking if it divides into a whole number) there's no fast way to do it.

For example, if I say 91, it's not immediately obvious that it's made of 7 & 13, and if you try to divide 91 by anything else, you won't get an integer answer.

When these numbers are far longer, it takes exponentially longer to calculate, so it would take a modern computer until the heat death of the universe to solve them, so it's effectively unbreakable.

Tom Scott explains it quite well in this video: https://www.youtube.com/watch?v=CINVwWHlzTY