In encryption, how is it you can decrypt with a private key what was encrypted with a public key, or decrypt with a public key what was encrypted with a private key, but not private-to-private or public-to-public?

Question

I am having a complete mental block understanding decryption with public and private keys. In my head, I am (apparently) falsely equating decryption to using a *Little Orphan Annie* decoder ring like in the movie *A Christmas Story*.

If a block of data was encrypted with a key, I can’t understand how a another key that is completely different is able to decrypt that data. I know there’s a fair bit of complex math involved, but if you multiple X by Y to get Z, then the only way to get X back from Z is to divide by Y.

* data->public key->encrypted->private key->data
* data->private key->encrypted->public key->data
* data->public key->encrypted->public key->error
* data->private key->encrypted->private key->error

In: 2

Answer 1

Actually it’s really simple at a conceptual level:

The numbers that compose your data are arranged in a ring and the encryption/decryption function can only move forward in that ring. The function that goes backward is much harder to compute.

Let me show an example with addition:

The data is a number from 0 to 9. To encrypt you add a number and take the rightmost digit, to decrypt you add the decryption key and take the rightmost digit.

In numbers:

your data: 2 (any digit from 0 to 9 is valid)
encryption key: 3
decryption key: 7

encryption procedure: 2+3 = 5. The encrypted data is 5
decryption procedure: 5+7 = 12 -> take the rightmost digit -> decrypted data is 2

Of course this scheme is easily crackable by subtracting one key from 10. But you can take a different encryption function which is stronger.

An example with multiplication:
To encrypt you multiply by 3 and take the rightmost digit.
To decrypt you multiply by 7 and take the rightmost digit.

In numbers:

your data: 2
encryption procedure: 2*3 = 6
decryption procedure: 6*7 = 42 -> take the righmost-> decrypted data is 2

As you can see, finding a way to derive one key from the other in this scheme is much harder but still solvable. The algorithm to crack the key is called Extended Euclidean algorithm.

There is an even strong pair of functions than can be used for encryption: power and its inverse, the discrete logarithm.

Example with power:
your data: 2
encryption procedure: 2^3 = 8
decryption procedure: 8^7 =2097152-> take the rightmost -> decrypted data is 2

Computing the power of a number is easy. Computing the discrete logarithm is impossible. Good luck trying to crack this scheme.

This pair of functions is used in most modern encryption algorithms. Another pair of functions that is popular is multiplication of prime number/factorization of the result.