Dead simple RSA implementation in Ruby

rsa.rb

#!/usr/bin/ruby

require 'rubygems'
require 'number-theory'
require 'openssl'
include NumberTheory

#
# Simple RSA implementation
#
# Kyle C. Hale 2015
#

def gcd(a, b)

    raise ArgumentError, 'Arguments must be > 0' unless a > 0 and b > 0

    while (a != 0 and b != 0) do

        if (a >= b) then
            a = a - b
        elsif (b > a) then
            b = b - a
        end
    end

    if (a == 0) then
        return b
    else 
        return a
    end
end

# gets two primes in a given range
def get_primes(lower, upper)

    raise ArgumentError, 'Lower must be less than upper' unless upper > lower

    thresh = 5
    digits = 3
    primes = []
    p = Primes.randprime(lower, upper)
    q = Primes.randprime(lower, upper)

    # next one needs to be a few digits separated
    while ((p-q).abs() < 10**digits and gcd(p-1, q-1) > thresh) do
        q = Primes.randprime(lower, upper)
    end

    primes[0] = p
    primes[1] = q
    
    return primes
end


def find_e (phi, d)

    return Utils.mod_inv(phi, d)

end

def gen_keypair(length)

    
    # get two primes, p and q, of similar length
    # pq = n ... phi(n) = (p-1)(q-1) = (n - (p + q) + 1)
    ps = get_primes(1000000, 30000000)

    start = ps.max
    # whatever
    d = Primes.randprime(start, 10000000000)
    
    puts "d is #{d}"
    puts "p1 is #{ps[0]} p2 is #{ps[1]}"
    # we can now use phi(n)
    e = find_e((ps[0]-1)*(ps[1]-1), d)
    
    puts "pubkey=#{e} privkey=#{d}"

end


length = ARGV[0]

puts "Length: #{length}"

gen_keypair(length)

Found while digging through my old code sandbox on my Mac in June 2018