It’s been a while since I looked at how public-key encryption actually works. I thought I need to refresh my knowledge, so here’s a quick summary of the RSA algorithm.

The Idea

The idea is that there are two keys, one public and one private. If I wanted to send you an encrypted message, I would encrypt it with your public key. But using the same public key, I could no longer decrypt it.

Only you can do it, with the private key which, of course, is private and only in your posession.

The public and the private key are just very (very very) big numbers.

It’s impossible (or rather completely, totally unlikely) to calculate the private key from the public key.

Mathematically speaking..

Encryption is, basically, just raising a number (=message) to an exponent (public) modulo some value (public).

Decryption is, basically, just raising a number (=encrypted message) to an exponent (private) modulo some value (public).

It just works with numbers, but any data is bascially a number. If you took this blog post, it would be just one veeeeery long number that, given the encoding (= meaning), represents this post.

So for encryption we have

    c = m ^ e (mod n) 

And for decryption it’s

    m = c ^ d (mod n)

where

    m = plaintext
    c = ciphertext
    e = public exponent
    n = public modulus
    d = private exponent

and the sign = in the above two equasions is actually not “equals to” but “congruent to”, since we are doing modular arithmetic.

That’s it.

The only difficulty is in calculating the keys. the random numbers p * q that make up the product n have to be very large for the cipher ot be secure. And calculating the secret exponent d is a matter of finding the multiplicative inverse for e “under” modulo(phi(n)).

That sounds weird, but it’s very similar to the reciprocal that everyone knows, namely the one, where multiplying the number and its inverse yields 1. For example 5, where the multiplicative inverse is 1/5, because 5 * 1/5 = 1. Same here, except we’re doing modular arithmetic, and we’re dealing with large numbers.

Ruby implementation

Here’s some ruby code that generates keys and uses them to encrypt and decrypt a message.

Note that this only demonstrates the principle. It is probably not entirely secure and definitely not very useful. (See discussion below)

But it runs and you can try it out. :)

class Integer
  # This method to check for primes is not 100% reliable, but almost.
  # Advantage: speed
   def prime?
     n = self.abs
     return true if n == 2
     return false if n == 1 || n & 1 == 0
     return false if n > 3 && n % 6 != 1 && n % 6 != 5

     d = n-1
     d >>= 1 while d & 1 == 0
     20.times do
       a = rand(n-2) + 1
       t = d
       y = Integer.mod_pow( a, t, n )
       while t != n-1 && y != 1 && y != n-1
         y = (y * y) % n
         t <<= 1
       end
       return false if y != n-1 && t & 1 == 0
     end
     return true
   end

   # a^b mod c , using much quicker squaring-method
   # check out https://en.wikipedia.org/wiki/Modular_exponentiation
   # for more information.
   def self.mod_pow( base, power, mod )
     res = 1
     while power > 0
       res = (res * base) % mod if power & 1 == 1
       base = base ** 2 % mod
       power >>= 1
     end
     res
   end
end

class RSA
  # E is the public-exponent, must be positive and smaller than φ(n) = φ(p * q)
  # greatest common divisor of e and φ(n) is 1 (= they are coprime).
  # usually 65537, because we use binary exponentiation and this number is prime
  # and only has two 1's in binary representation (= less cpu-time).
  E = 65537

  class << self

    # Returns the public modulus, the public exponent and the private key.
    def generate_keys( bits )
      n, e, d = 0
      p = random_prime( bits )
      q = random_prime( bits )
      n = p * q
      d = get_d( p, q, E )
      [n, E, d]
    end

    # Encrypts a message with the public modulus (of the receiver).
    # First encode string as a (large) number.
    def encrypt( m, n )
      m = s_to_n( m )
      Integer.mod_pow( m, E, n )
    end

    # Decrypts using the private exponent
    def decrypt( c, n, d )
      m = Integer.mod_pow( c, d, n )
      n_to_s( m )
    end

    private

    # Convert number to string
    def n_to_s( n )
      s = ""
      while( n > 0 )
        s = ( n & 0xFF ).chr + s
        n >>= 8
      end
      s
    end
    
    # Convert string to number
    def s_to_n( s )
      n = 0
      s.each_byte do |b| 
        n = n * 256 + b 
      end
      n
    end

    # Generate a random number and check if
    # it's prime until a prime is found.
    def random_prime( bits )
      begin
        n = random_number( bits )
        return n if n.prime?
      end while true
    end

    # Concatenate string (begins and ends with 1)
    # to get desired length and an uneven value.
    def random_number( bits )
      m = (1..bits-2).map{ rand() > 0.5 ? '1' : '0' }.join
      s = "1" + m + "1"
      s.to_i( 2 )
    end

    # Euler's totient function, φ(p,q)
    # needed so a multiplicative inverse (private key)
    # can be calculated. https://en.wikipedia.org/wiki/Euler%27s_totient_function
    def phi( a, b )
      (a - 1) * (b - 1)
    end

    # Check out https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    # for the maths.
    def extended_gcd( a, b )
      return [0,1] if a % b == 0
      x, y = extended_gcd( b, a % b )
      [y, x - y * (a / b)]
    end

    # Calculate the multiplicative inverse d with d * e = 1 (mod φ(p,q)),
    # using the extended euclidian algorithm.
    def get_d(p, q, e)
      t = phi( p, q )
      x, y = extended_gcd( e, t ) 
      x += t if x < 0
      x
    end
  end
end

# (n,e) = public key
# (n,d) = private key
n,e,d = RSA.generate_keys( 256 )

# Something we can't possibly say in public
m = "The Fast And The Furious is a great movie!"

puts "public exponent: %x" % e
puts "public modulus : %x" % n
puts "private exp    : %x" % d

puts ""
puts "Message        : %s" % m
puts ""

c = RSA.encrypt( m, n )

puts "Encrypted      : %x" % c
puts ""
puts "Decrypt again  : %s" % RSA.decrypt( c, n, d )

Discussion

So the above code implements RSA. However, there are some downsides to this implementation.

1. The message cannot be longer than the key.
2. The cipher can probably be broken.

Actually, both problems are addressed with the same solution. (And please, take this with a grain of salt, I am a total amateur just scratching the surface here.)

What is missing here is a formatting or padding scheme. If we want to encrypt long messages (arbitrary length) we need to be able to split them up so they are in chunks that can be encrypted.

Also, we need to harden the algorithm against attacks. One such hardening measure is adding random noise to each block, which is used as padding. The result is that the ciphertext will be completely different each time, but the receiver, since he knows how to apply (or un-apply) the padding, will be able to remove it again.

These things are complicated, but the core algorithm is easy. However, they are necesary to avoid certain weaknesses. That’s why, generally, just because a software encrypts data, it does not necessarily mean they do it right. You have to know what you do and/or use well known and well tested libraries. (OpenSSL comes to mind.)

As you can see there’s also some “trickery” involved. And I just mean that you need to use special algorithms, because you can’t just tell the computer to take a number with 500 digits and raise it to the power of another number of 500 digits. It would typically fail or be very slow. Same thing with checking if such a large number is prime. Thus the “good enough” algorithm above.

That’s it

I don’t know. I just wanted to write this down. Just so you can see that it’s not very difficult. Even if the proofs why it’s secure, why it works in the first place, may be not.

Btw. this whole code is based on this great Github repository. This guy also has implementations of other algorithms and some great explanation docs.