RSA

The very first thing to do is to choose 2 prime numbers, p and q:

  p = 7                                                             # parameters
  q = 11

7
11

Next, let's multiply the two numbers:

  n = p * q

77

Now it's time to define our first function phi:

  phi = (p-1) * (q-1)

60

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 function 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.

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 Euclidean 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.

  gcd = ->(a, b) { while(b != 0) do r, a = a % b, b; b = r end; a } # encryption
  e = (2..phi).find{|i| gcd.call(i, phi) == 1 }

7

Message encryption is modulo exponentiation of message m at encryption key e.

  m = 6
  c = m**e % n

41

The d key below is the decryption key (or private/secret key) and is defined as multiplicative inverse of e over finite field phi. Simple put in math terms: 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.

  d = (2..phi).find{|i| (i * e) % phi == 1 }                        # decryption

43

Message decryption is another modulo exponentiation using the encrypted cipher c and decryption key d:

  message = c**d % n
  m == message ? "YOU ARE A CRYPTOSTAR!" : "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

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:

  m = c^d mod n #1
  c = m^e mod n #2

Let's substitute #2 in #1:

  m = (m^e)^d mod n

Exponentials power rule says that (a^b)^c == a^(b*c) and in the end we only need to prove

  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:

  6 == 6**(7 * 43) % 77 ? "YOU ARE A CRYPTOSTAR!" : "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://brilliant.org/wiki/rsa-encryption/