Overview
"If you can't explain it simply, you don't understand it well enough" - Einstein
RSA (Rivest-Shamir-Adleman) needs no introduction, it is well known and most used public-key cryptosystem that governs our digital lives.
Here is my take, a simple implementation in 10 lines of Ruby code that is neither the best implementation nor the most efficient one but is enough for the purpose of this article.
1 p = 7
2 q = 11
3 n = p * q
4 phi = (p-1) * (q-1)
5 gcd = ->(a, b) { while(b != 0) do r, a = a % b, b; b = r end; a }
6 e = (2..phi).find{|i| gcd.call(i, phi) == 1 }
7 d = (2..phi).find{|i| (i * e) % phi == 1 }
8 m = 6
9 c = m**e % n
10 message = c**d % n
11 "Decrypted message: #{message}" if m == message
Except lines #5 that involves an algorithm and a while loop, everything else is mid-school math and `**` is the exponentiation operator.
The curious minds please read simple explanations below.
Integer factorization trapdoor
The very first thing to do is to choose 2 prime numbers, `p` and `q`:
1 p = 7
2 q = 11
Next, let's multiply the two numbers:
3 n = p * q
Now it's time to define our first function `phi`:
4 phi = (p-1) * (q-1)
Which is Euler's totient function defined as number of integers less than `n` that are coprime with `n` and has two interesting properties:
- the function is multiplicative and `phi(a*b) = phi(a) * phi(b)`
- if `n` is a prime number then `phi(n) = n - 1`
And finally we have the cryptographic trapdoor which is the most important primitive to understand. Trapdoors are based on asymmetric computation that is easy to do in one direction but it is very difficult to calculate in the opposite direction.
In our case, if one (an attacker) does not know the initial `p` and `q` prime numbers it will be very hard to calculate the `phi` because integer factorization of `n` is known to be infeasible to calculate for very large numbers.
Message encryption
Now it's time to define our first algorithm, `gcd` which is the greatest common divisor and is defined as the largest positive integer that divides both `a` and `b`.
If single-liner GCD looks scary then here is the formatted version of the Euclid's algorithm.
def gcd(a, b)
while(b != 0) do
r = a % b
a = b
b = r
end
a
end
The `e` key below is the encryption key and is defined as the smallest value for which `gcd(e, phi) == 1` is true.
To keep things simple we will just brute-force and find `e` but keep in mind that this will be very inefficient for large numbers.
5 gcd = ->(a, b) { while(b != 0) do r, a = a % b, b; b = r end; a } (gcd)
6 e = (2..phi).find{|i| gcd.call(i, phi) == 1}
Message encryption is modulo exponentiation of the message `m` and the encryption key `e`.
7 m = 6
8 c = m**e % n
Message decryption
The `d` key below is the decryption key and is defined as multiplicative inverse of `e` over finite field `phi`. Simply put `e * d mod phi = 1`.
Again we will just brute-force and calculate the inverse but there are better algorithms to do this, like Extended Euclidean algorithm.
9 d = (2..phi).find{|i| (e * i) % phi == 1}
Message decryption is another modulo exponentiation using the encrypted cipher `c` and decryption key `d`:
10 message = c**d % n
BINGO! You can try it yourself but I can bet that `m = message = 6`
Intuition
At first sight it looks like magic right? but if you reason about it, it's very easy.
Starting backwards, with the decryption/encryption formulas:
1 m = c^d mod n
2 c = m^e mod n
Let's substitute #2 in #1:
m = (m^e)^d mod n
Exponentials Power Rule says that `(ab)c == a(b*c)` and we also know that `d` is the multiplicative inverse of `e`, guess what is the value of the resulting exponent? :)
m = m^(e*d mod phi) mod p
If the intuition is valid then the following expression stands true, where 7 is `e` and 43 is `d` in our little example:
'YOU ARE A CRYPTOSTAR!!!' if 6 == 6**(7 * 43 % 60) % 77