# RSA

## Cryptography

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.

# 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 cryptographic 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 message m at 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 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 in the end we only need to proove

m = m^(e*d) mod n


or using another form of e*d ≌ 1 mod phi where c is a positive integer

m = m^(1 + c * phi) mod n


apply power rule again

m = m^1 * (m^phi)^c mod n


and last congruence using Euler’s theorem that says a^phi(n) ≌ 1 mod n

m ≌ m * 1^c mod n


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