Asymmetric key encryption

An encryption key is a string of characters that you feed into an encryption algorithm to either encrypt or decrypt a message. An asymmetric key system has two keys. There’s a public key to encrypt a message. It’s public because anyone can see it and use that key. But once the message is encrypted using the public key, the message can only be retrieved by someone with the private key. Only the sender and the receiver should know the private key.

The encryption algorithm uses the properties of prime numbers to encrypt a message. As I explored in the last post, two randomly selected really large prime numbers (p and q), when multiplied together produce an even larger number n that is virtually impossible to factorize, i.e. to discover the p and q primes that produced n. We are here talking about an integer n that has over 100 digits. Here’s how the encryption algorithm works. I won’t attempt to explain why it does, just what it does, and with diagrams.

Multiplying primes

The encryption software chooses two random large prime numbers p and q, and multiplies them together. Think of p and q as the length of the side of a rectangle. To keep this demonstration simple, I’ll choose two very small primes, p=3 and q=5. So, n = p.q = 15. (Pretend that p, q are so large that no one could guess them as factors of n, i.e. n is impossible to factorize.) n = p.q = 3 x 5 = 15. These values are then fixed and hidden within this particular encryption algorithm. They don’t vary with the message or the occasion in which it is used.

The algorithm now calculates a smaller version of this product by subtracting 1 from each of the primes and multiplying them together.

z = (p-1).(q-1) = 8

The algorithm then has to create a new number e that is less than n and is not a factor of z.

e < n
z mod e ≠ 0

In this demonstration, with the values already decided, that means e must be less than 15 and doesn’t divide into 8 a whole number of times.

In this case the numbers that meet that requirement are 3, 5, 7, 9, 10, 11, 12, 13, 14. They are all less than 15 and none are factors of 8. The algorithm selects (randomly) e = 11.

The algorithm then has to create a number d such that when it’s multiplied by e and divided by z it produces a remainder of just 1. Some candidates for d are 3, 11, 19, 27, etc. The algorithm randomly chooses d = 3.

d x e = 3 x 11 = 33
d.e mod z must equal 1
33 mod 8 = 1 (it is)

Here’s a spatial representation of the d and e relationship.

The public and private keys are number pairs.

Public key = [n, e] = [15, 11]
Private key = [n, d] = [15, 3]

Encrypting the message

The sender and receiver of the message have access to the same encryption algorithm with the same p and q values coded in. Person A wants to dispatch a secret message m. To keep this demonstration simple, I’ll encrypt just a number, the message is “7” i.e. m = 7.

The formula to encrypt the message m into coded form c is

c = me mod n

n and e are parts of the public encryption key. The algorithm will multiply the number m by itself e times and divide the result by n. The value of c is whatever is left over from that division (the mod operation).

c = 711 mod 15

me is going to be very large. For visual confirmation, here are three gridded rectangles. The first is 72, the second is 73 , the third is 74. I don’t have the space to show what happens when you keep multiplying m by m eleven times.

me = 711 = 1,977,326,743

That number of grid units could be arranged in a huge rectangle with integer dimensions as follows. There are variants, but they are more stretched out than this one.

Divide that by n = 15 to give 131,821,782 whole numbers with 13 left over. That would be a very long thin rectangle of dimensions 15 x 131,821,782 with a tiny sliver of 13 cells left over at one end.

Recovering the message

So all those big number calculations result in c = 13 which is what gets transmitted as the encrypted message. The recipient B then uses the private encryption key pair d and n to decrypt the message.

m = cd mod n
m = 133 mod 15 = 7

Here’s the 133 = 13 x 13 x 13 gridded rectangle made up of 146 grid units

Here are the same number of grid units rearranged to a 146 x 15 rectangle with 7 grid units left over, which is the original message m.

Surprisingly, that tiny remaindered bit at the end is the original message. Even with very small primes (p and q) and a miniscule message m of just one number, the calculations involve extremely large integers and require iteration to find numbers that match various criteria.

So whatever the speed of the computer, this kind of encryption is computationally expensive. It’s therefore used for handshaking protocols, setting up a secure connection that enables the exchange of keys used for faster, simpler encryption.

References

Note

  • The references above explain the process. The diagrammatic approach and any errors that entails are my own.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.