An RSA encryption example, written in ruby

rsa.rb

=begin
 You are given RSA Public Key (391, 3).
 What is your decryption exponent?
 What is the encoding of M = 41?
=end

puts
puts

def gcd(a, b)
    b == 0 ? a : gcd(b, a % b)
end

def rel_prime(p , q)
	n = (p-1)*(q-1)
	$i = 3
	until $i >= n do
		if gcd($i,n) == 1
			break
		end
		$i = $i + 1
	end
	print "pub_e(#{p},#{q})\t= #{$i}\n"
	return $i
end

#based on pseudo code from http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2 and from translating the python implementation.
def extended_gcd(a, b)
  last, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  quotient = 0
  while remainder != 0
  	print "quotient\t", "= #{last} / #{remainder}" , "\n"
	print "remainder\t", "= #{quotient} * #{remainder} + #{remainder} % #{last} ", "\n"
    last, (quotient, remainder) = remainder, last.divmod(remainder)
	print "x \t\t= #{last_x} - #{quotient} * #{x},  x' = #{x}\n"
  	print "*quotient\t= ", quotient ,"\n"
    print "*remainder\t= ", remainder, "\n"
    print "*last_rem\t= ", last, "\n"
    x, last_x = last_x - quotient*x, x
    #y, last_y = last_y - quotient*y, y
    print "*x\t\t= #{x} \n*x'\t\t= #{last_x}\n"
    print "___________________\n"
  end

  return last, last_x * (a < 0 ? -1 : 1)
end
 
def invmod(pub_e, conj)
  remainder, decryption_exp = extended_gcd(pub_e, conj)

  if remainder != 1
    raise 'Teh maths are broken!'
  end
  print "\n decryption exponent(d)  #{decryption_exp % conj}  aka \"private key\""
  decryption_exp % conj
end

# 391
p = 17
q = 23
conj = (p-1)*(q-1)

# public
pub_N = p * q 
pub_e = rel_prime( p, q )

# private
d = invmod( pub_e, conj )

# message
message = 41

# encrypted
rsa = (message**pub_e) % pub_N

# decrypted
result = (rsa**d) % pub_N

print "\n p  #{p}\n q  #{q}\n N  #{pub_N}\n e  #{pub_e}\n d  #{d}\n message\t#{message}\n"
print "\n encrptyed::  #{rsa}  \n\n decrypted::  #{result}  \n"



puts
puts
puts
#print "  #{qp1} % #{e} =  #{qp1%e} \n\n  #{ e*-117 } "