Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
socialist millionaire in ruby
#http://www.scribd.com/doc/34203336/How-to-Implement-RSA-in-Ruby#download
# Calculate a modular exponentiation eg: b^p mod m
def mod_pow(base, power, mod)
result = 1
while power > 0
result = (result * base) % mod if power & 1 == 1
base = (base * base) % mod
power >>= 1
end
result
end
# Convert a string into a big number
def str_to_bignum(s)
n = 0
s.each_byte {|b|n=n*256+b}
n
end
# Convert a bignum to a string
def bignum_to_str(n)
s=""
while n>0
s = (n&0xff).chr + s
n >>= 8
end
s
end
#http://rosettacode.org/wiki/Modular_inverse#Ruby
#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, remainder = a.abs, b.abs
x, last_x, y, last_y = 0, 1, 1, 0
while remainder != 0
last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
x, last_x = last_x - quotient*x, x
y, last_y = last_y - quotient*y, y
end
return last_remainder, last_x * (a < 0 ? -1 : 1)
end
def invmod(e, et)
g, x = extended_gcd(e, et)
if g != 1
raise 'Teh maths are broken!'
end
x % et
end
# A prime and a generator (primitive root) for that prime.
# Can be same as OTR: http://www.ietf.org/rfc/rfc3526.txt
prime = 97
h = 5
# The numbers being tested for equality.
x = 35
y = 34
a = rand(1..10)
alpha = rand(1..10)
r = rand(1..10)
b = rand(1..10)
beta = rand(1..10)
s = rand(1..10)
g = mod_pow(mod_pow(h,a,prime),b,prime)
gamma = mod_pow(mod_pow(h,alpha,prime),beta,prime)
p = mod_pow(gamma,r,prime)
q = mod_pow(gamma,s,prime)
t = p*invmod(q, prime) % prime
p_prime = (mod_pow(h,r,prime)*mod_pow(h,x,prime)) % prime
q_prime = (mod_pow(h,s,prime)*mod_pow(h,y,prime)) % prime
c = mod_pow((p_prime*invmod(q_prime, prime) % prime),(alpha*beta),prime)
puts c == t
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment