At first sight asymmetric encryption (or public key encryption) seems very counterintuitive and confusing. How is this asymmetry even possible? Encrypting with one key and decrypting with another… what? People are mostly used to seeing symmetric mathematical functions such as:
2 + 5 = 7
47 * 2 = 94
45 / 15 = 3
To undo these manipulations we still use the same numbers; only the operators (plus, minus, times, etc.) are changed:
7 – 5 = 2
94 / 2 = 47
3 * 15 = 45
To revert an asymmetric manipulation however, we need entirely different numbers.
Juggling With Numbers
Asymmetric encryption was invented by British cryptographers James H. Ellis and Clifford Cocks in the early 60s. Rumour has it, that it only took them 10 minutes. This method was immediately classified as top secret and kept private by the British secret service. Independently, several years later, in 1977 the very same method was discovered by three american MIT students: Ron Rivest, Adi Shamir and Leonard Adleman. After making it publicly available, the method became known as RSA (after their first names).
RSA builds upon a very important principle: the factorisation problem of large prime numbers. This simply means that after multiplying two large prime numbers, it is very difficult to find the original two numbers (factors). Remember, that a prime number is only divisible by one and itself. For example 151 and 419 are both primes. Multiplying them gives 63269, which can only be the result of multiplying these two numbers. Given 63269 alone, it is very difficult to retrieve the two primes it consists of.
This is an example of a one-way-function. A one-way-function is easy to compute in one way, but extremely difficult to revert. More importantly, as the primes become larger, the process of factoring them becomes exponentially harder. This means that while a home computer can factor a 10-digit prime number in a reasonable amount of time (several milliseconds), a 30-digit number would be factorised in weeks, a 70-digit number in millenia, a 150-digit number in a few million years etc. etc. Even the most powerful computer network on the planet will need thousands of years.
Furthermore RSA makes use of modular arithmetic and something called Euler’s Totient Function.
Modulo operations are easily pictured as clock operations. For example, a clock is a modulo 24 operation. This means that no matter how many hours you add, substract, multiply, or divide, every time you reach 24, the number is reset to 0.
How much is 17 o’clock + 10? You start counting 18→19→20→21→22→23→0→1→2→3. Thus
(17 + 10) modulo 24 = 3
(48 * 3) modulo 50 = 44
(21 / 7 ) mod 2 = 1
Euler’s Totient Function is a way of finding out how many numbers there are, that do not share a common divider with a given number X other than 1 (these kind of numbers are said to be co-prime with X). For example:
for the number 10 there are 4 co-primes (1 2 3 4 5 6 7 8 9 10)
for the number 6 there are 2 co-primes (1 2 3 4 5 6)
for prime numbers, it is logically always the number taken minus one.
Knowing all this, let us jump straight to constructing a simple private-public key pair and see how this works in real life.
1. Pick two random prime numbers (of similar size):
P = 37 and Q = 11
2. Compute the modulus N as N = P * Q:
37 * 11 = 407
3. Compute Euler’s Totient Function (φ) for N. Note that this is multiplicative, e.g. φ(N) = φ(P) * φ(Q):
Because we are dealing with prime numbers, as previously mentioned φ(prime) = (prime – 1):
φ(37) = 36 and φ(11) = 10
φ(407) = φ(37) * φ(11) = 360
4. choose an integer E, so that 1 < E < φ(N). In addition E and φ(N) need to be co-prime (sharing no common divider other than 1):
E = 7
This will be our public key.
5. Solve D for D = (E-1) mod φ(N); this is the same as D*E = 1 mod φ(N):
D*7 = 1 mod 360 → “What number times 7 equals 1 if we modulo 360?”
Wolfram Alpha gives us the number D = 103.
Let this be our private key.
Now that we have a public and a private key, we can use them as follows:
encryption: (message(key)) mod N
decryption: (cipher(opposite key)) mod N
The word “hi” can be transformed into a number using the alphabetical order of each letter “8 9”
We encrypt the message with our private key D: (89103) mod 407 = 276.
A person possessing our public key E can decrypt this back to the original message: (2767) mod 407 = 89.
The same can be done by encrypting with the public key and decrypting with the private key.
This is how mind blowing math magic is used for public key encryption in real life.