handcrafted rsa

rsa.rb

require './rsa_math.rb'

class RSA
  class << self

    PUBLIC_EXPONENT = 65537

    def gen_key(bits)
      e = PUBLIC_EXPONENT
      p = RSAMath.gen_prime(bits/2)
      q = RSAMath.gen_prime(bits/2)
      d = gen_d(e, p, q)
      n = p*q
      return {n: n, e: e, d: d}
    end

    def gen_d(e, p, q)
      phi = (p-1) * (q-1)
      d, = RSAMath.extended_gcd(e, phi) 
      d += phi if d < 0
      d
    end

    def encrypt(message, e, n)
      RSAMath.mod_pow(message, e, n)
    end

    def decrypt(cipher, d, n)
      RSAMath.mod_pow(cipher, d, n)
    end

  end
end

rsa_math.rb

class RSAMath
  class << self
  
    MILLER_RABIN_LOOPS = 20

    def gen_prime(bits)
      loop do
        n = random_num(bits)
        return n if is_prime?(n)
      end
    end

    def random_num(bits)
      ret = 1 # MSB must be set
      (bits-1).times { ret <<= 1; ret += rand(2) }
      ret
    end

    def is_prime?(n)
      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

      MILLER_RABIN_LOOPS.times do
        a = rand(n-2) + 1
        t = d
        y = 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
      true
    end

    def mod_pow(base, power, mod)
      res = 1
      while power > 0
        res = (res * base) % mod if power & 1 == 1
        base = (base * base) % mod
        power >>= 1;
      end
      res
    end

    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

  end
end

util.rb

class Util
  class << self

    def bin2int(bin)
      ret = 0
      bin.each_byte { |b| ret *= 256; ret += b }
      ret
    end

    def int2bin(int)
      bytes = []
      bytes.unshift(int % 256) while (int /= 256) > 0
      bytes.pack('C*')
    end

  end
end

This code is based on https://github.com/chrishulbert/crypto and http://www.lukaszielinski.de/blog/posts/2013/07/04/the-rsa-algorithm-in-ruby/