Implement RSA-PKCS#1 v1.5 in Ruby

rsa.rb

require 'securerandom'
require 'matrix'

module RSA
    module Calculator
        def self.powmod(base, exp, mod)
            return 1 if exp == 0
            exp.bit_length.times.inject(1) do |buf, i|
                (buf ** 2) * (base ** exp[exp.bit_length - 1 - i]) % mod
            end
        end

        def self.miller_rabin_prime?(num, trial)
            return false if num.even? || num < 3
            odd_factor = num - 1
            exp2 = 0
            while odd_factor.even? do exp2 += 1; odd_factor >>= 1 end

            srand()
            trial.times do 
                witness = rand(2...num)
                m = powmod(witness, odd_factor, num)

                return true if m == 1
                exp2.times do |i|
                    return true if m == num - 1
                    m = m ** 2 % num
                end
            end

            return false
        end

        def self.extended_euclidean_algorithm(m, n)
            reverse_flag = m < n
            m, n = n, m if reverse_flag
            gcd = m.gcd(n)

            quos = [m.div(n)]
            while m % n != 0
                m, n = n, m % n
                quos << (m.div(n))
            end

            sol = quos.reverse.inject(Matrix.I(2)) do |mtx, quo|
                mtx * Matrix[[0, 1], [1, -quo]]
            end

            return reverse_flag ? sol.row(0).to_a.reverse : sol.row(0).to_a
        end
    end

    def self.generate_keypair(key_len = 2048, exp = 0x10001, miller_rabin_trial = 2)
        rand_max = 1 << (key_len.div(2) - 2)

        p, q = 0, 0

        until Calculator.miller_rabin_prime?(p, miller_rabin_trial)
            p = ((SecureRandom.random_number(rand_max) + rand_max) << 1) + 1
        end

        until Calculator.miller_rabin_prime?(q, miller_rabin_trial)
            q = ((SecureRandom.random_number(rand_max) + rand_max) << 1) + 1
        end

        pub_key = p * q
        totient = (p - 1) * (q - 1)
        sec_key = Calculator.extended_euclidean_algorithm(exp, totient)[0]

        while sec_key < 0
            sec_key += totient
        end

        return exp, pub_key, sec_key
    end

    def self.encrypt(message, key, exp = 0x10001)
        raise(RuntimeError, 'message too long for key size') if message >= key
        Calculator.powmod(message, exp, key)
    end

    def self.decrypt(cipher, pub_key, sec_key)
        Calculator.powmod(cipher, sec_key, pub_key)
    end
end

module RSA_PKCS1_v1_5
    using Module.new {
        refine String do
            def b2i
                self.unpack('C*').inject {|m, n| (m << 8) + n}
            end
        end

        refine Integer do
            def i2b(byte = nil)
                byte ||= (self.bit_length + 7).div(8)
                [sprintf("%0*x", byte * 2, self)].pack('H' + (byte * 2).to_s)
            end
        end
    }

    def self.encrypt(message, key, exp = 0x10001)
        message = "\x00\x02" + rand(0x1_0000_0000_0000_0000).i2b(8) + "\x00" + message

        message = message.b2i
        return RSA.encrypt(message, key, exp).i2b 
    end

    def self.decrypt(cipher, pub_key, sec_key)
        cipher = cipher.b2i

        message = RSA.decrypt(cipher, pub_key, sec_key).i2b

        return message[10..-1]
    end
end

key = RSA.generate_keypair

message = Array.new(rand(247)){rand(0x100)}.pack('C*')

cipher = RSA_PKCS1_v1_5.encrypt(message, key[1])

p message, RSA_PKCS1_v1_5.decrypt(cipher, key[1], key[2])