Skip to content

Instantly share code, notes, and snippets.

/crazy_math.rb
Created Nov 21, 2009

Embed
What would you like to do?
just some math intensive calculations (diffie hellman, group key exchanges, ...)
class String
# Convert String to a string of binary digits, similar to Integer.to_s(2).
def to_bin
n = self.to_str
s = ''
n.each_byte do |b|
s << b.to_s(2)
end
s
end
# Do I need a Integer#to_integer and a String.to_integer? Strings should be
# allowed as inputs to a lot of the crypto APIs, but they will be treated as
# integers, internally! How to deal with this?
def to_integer
Integer.from_unsigned_bytes(self)
end
def to_bytes
self
end
end
class Integer
# +bytes+ is a sequence of octets in network byte order (most significant
# byte first) that comprises an unsigned integer.
def self.from_unsigned_bytes(bytes)
bytes = bytes.to_str
n = 0
bytes.each_byte do |b|
n <<= 8
n |= b
end
n
end
# Return self as a String of bytes in network byte order.
def to_bytes
a = []
n = self.to_int
while n != 0
a.unshift( (n & 0xff).chr )
n >>= 8
end
a.join
end
# Return self.
#
# Purpose is to allow a set of classes to declare themselves to be "duck-typed"
# to Integer. This set of classes includes String, see String#to_integer.
def to_integer
self
end
# Why isn't this a standard ruby method?
def []=(position, value)
bit = 2 ** position
i = self.to_int
if value
i |= bit
else
i &= ~bit
end
i
end
# Determine size of +self+ in bits.
def bit_size
i = self.to_int
hibit = i.size * 8 - 1
while( i[hibit] == 0 ) do
hibit = hibit - 1
break if hibit < 0
end
hibit + 1
end
end
class Integer
# Calculate the inverse of an Integer modulo +n+. The modular inverse of +a mod n+,
# +a^-1 mod n+, is a number +a^-1+ such that:
#
# a^-1 * a = 1 mod n
#
# There may not be such a number, in which case a RangeError is raised.
#
# Uses the 'Extended Euclidean Algorithm' implementation
# from Figure 4.1, +Cryptography Theory and Practice+, Stinson.
def modular_inverse(n)
n = n.to_int
b = self.to_int
n0 = n
b0 = b
t0 = 0
t = 1
q = (n0/b0).floor
r = n0 - q * b0
while r > 0 do
temp = t0 - q * t
if temp > 0 then temp = temp.modulo(n); end
if temp < 0 then temp = n - ((-temp).modulo(n)); end
t0 = t
t = temp
n0 = b0
b0 = r
q = (n0/b0).floor
r = n0 - q * b0
end
if b0 != 1
raise RangeError, "#{b} has no inverse modulo #{n}"
else
t.modulo(n)
end
end
# Calculate +self+ ** +exp+ modulo +n+.
#
# This method uses the "square and multiply" approach. Why should be fairly
# obvious from the code, see +Cryptography Theory and Practice+, Stinson,
# Chapter 4.4 for a description of the method.
def modular_exp(exp, n)
# x ** b mod n
x = self.to_int
b = exp.to_int
n = n.to_int
z = 1
(n.bit_size - 1).downto(0) do |i|
z = z ** 2 % n
if b[i] == 1 then
z = z * x % n
end
end
z
end
# Return whether +self+ is even, that is, evenly divisible by 2.
def even?
self[0] == 0
end
# True if +self+ is probably prime, false otherwise. Probabalistic primality
# test is the Miller-Rabin algorithm, aka "strong pseudo-prime test".
#
# +accuracy+ is the number of times to try the test, and error probablity
# will be aproximately 1 time out of 4**+accuracy+. Default is 10, wich gives
# an error rate of 1 in 1,048,076.
def prime?(accuracy = 10)
miller_rabin_prime?(accuracy)
end
# Determines if an odd number is prime, with an error probability of 1/4, at
# most. Implementation from Stinson, Figure 4.9.
def miller_rabin_prime?(accuracy)
# Two is prime
return true if self == 2
# Not prime if its even!
return false if self.even?
n = self.to_int
# Find k, m such that n - 1 = (2 ** k) * m, where m is odd
m = n - 1
k = 0
# Since n is odd, n-1 is even, and this will loop at least once
while m.even?
m >>= 1
k += 1
end
# Answers of 'composite' are always correct - n is not prime. Answers of
# 'prime' are not necessarily true, so we try again. If we answered 'prime'
# accuracy number of times, then maybe it is prime.
accuracy.times do
catch(:isprime) do
# Choose a, 1 <= a <= n - 1
a = Kernel.rand(n - 1) # 0..(n-2)
a = a + 1 # 1..n-1
# Compute b = a ** m mod n
b = a.modular_exp(m, n)
# puts "n #{n} m #{m} k #{k} a #{a} b #{b}"
# If b == 1 mod n, n is prime
if( b == 1 )
throw :isprime
end
# For i = 0 to k - 1 do
k.times do
# if b == -1 (mod n), n is prime
if( b == (n - 1) )
throw :isprime
else
b = b.modular_exp(2, n)
end
end
# It's composite.
return false
end
end
return true
end
end
def modular_power(a,exp,mod)
result = a
(exp-1).times do
result = (result * a) % mod
end
result
end
# Diffie-Hellman Key Exchange
print "Generator:\t\t\t"
puts generator = 7789
print "Prime:\t\t\t"
puts prime = 1017473
print "Alice's secret:\t\t"
puts alice_secret = 415492
print "Bob's secret:\t\t"
puts bob_secret = 725193
#Das sagt Alice dann Bob
print "from alice to bob:\t"
puts von_alice_an_bob = modular_power(generator, alice_secret, prime)
#Das sagt Bob dann Alice
print "from bob to alice:\t"
puts von_bob_an_alice = modular_power(generator, bob_secret, prime)
#and that's how they get the key
print "bob's key:\t\t"
puts bobs_key_calculation = modular_power(von_alice_an_bob, bob_secret, prime)
print "alice's key:\t\t"
puts alices_key_calculation = modular_power(von_bob_an_alice, alice_secret, prime)
def modular_power(a,exp,mod)
result = a
(exp-1).times do
result = (result * a) % mod
end
result
end
print "Generator:\t\t\t"
puts generator = 7789
print "Prime:\t\t\t"
puts prime = 1017473
print "Alice's secret:\t\t"
puts alice_secret = 415492
print "Bob's secret:\t\t"
puts bob_secret = 725193
print "Carlo's secret:\t\t"
puts carol_secret = 598843
#++++++++++++++++++++++++++++++++++++
#first round
#everybody sends info to his predecessor
#From Alice zu Bob
print "from alice to bob:\t"
puts runde_1_alice_an_bob = modular_power(generator, alice_secret, prime)
#From Bob zu Carol
print "from bob to carol:\t"
puts runde_1_bob_an_carol = modular_power(generator, bob_secret, prime)
#From Carol zu Alice
print "from carol to alice:\t"
puts runde_1_carol_an_alice = modular_power(generator, carol_secret, prime)
#++++++++++++++++++++++++++++++++++++
#second round
#From Alice zu Bob
print "from alice to bob:\t"
puts runde_2_alice_an_bob = modular_power(runde_1_carol_an_alice, alice_secret, prime)
#From Bob zu Carol
print "from bob to carol:\t"
puts runde_2_bob_an_carol = modular_power(runde_1_alice_an_bob, bob_secret, prime)
#From Carol zu Alice
print "from carol to alice:\t"
puts runde_2_carol_an_alice = modular_power(runde_1_bob_an_carol, carol_secret, prime)
#++++++++++++++++++++++++++++++++++++
#And that's how they get the groupkey
print "alice's group Key:\t"
puts alice_group_key = modular_power(runde_2_carol_an_alice, alice_secret, prime)
print "bob's group Key:\t"
puts bob_group_key = modular_power(runde_2_alice_an_bob, bob_secret, prime)
print "carol's group Key:\t"
puts carol_group_key = modular_power(runde_2_bob_an_carol, carol_secret, prime)
require "crazy_math.rb"
def modular_power(a,exp,mod)
result = a
(exp-1).times do
result = (result * a) % mod
end
result
end
print "Generator:\t\t\t"
puts generator = 7789
#puts generator = 13
print "Prime:\t\t\t\t"
puts prime = 1017473
#puts prime = 997
print "Alice's secret:\t\t"
puts alice_secret = 415492
#puts alice_secret = 41
print "Bob's secret:\t\t\t"
puts bob_secret = 725193
#puts bob_secret = 71
print "Carlo's secret:\t\t"
puts carol_secret = 598843
#puts carol_secret = 51
#++++++++++++++++++++++++++++++++++++
#first round
#everybody broadcasts
#From Alice to the group
print "from alice to group:\t"
puts runde_1_alice_an_group = modular_power(generator, alice_secret, prime)
#From Bob to the group
print "from bob to group:\t"
puts runde_1_bob_an_group = modular_power(generator, bob_secret, prime)
#From Carol to the group
print "from carol to group:\t"
puts runde_1_carol_an_group = modular_power(generator, carol_secret, prime)
puts "ROUND TWO"
puts "*************"
#From Alice to the group
print "from alice to group\t"
puts runde_2_alice_an_group = modular_power(((runde_1_bob_an_group * runde_1_carol_an_group.modular_inverse(prime))%prime), alice_secret ,prime)
#puts runde_2_alice_an_group = modular_power((runde_1_bob_an_group * modular_power(runde_1_carol_an_group, prime-2, prime)), alice_secret ,prime)
#From Bob to the group
print "from bob to group:\t"
puts runde_2_bob_an_group = modular_power(((runde_1_carol_an_group *runde_1_alice_an_group.modular_inverse(prime))%prime), bob_secret ,prime)
#From Carol to the group
print "from carol to group:\t"
puts runde_2_carol_an_group = modular_power(((runde_1_alice_an_group *runde_1_bob_an_group.modular_inverse(prime))%prime), carol_secret ,prime)
puts "GROUPKEY"
puts "*************"
#++++++++++++++++++++++++++++++++++++
#and that's how they get the groupkey
print "alice's group Key:\t"
alice_group_key = ((modular_power(runde_1_carol_an_group, 3 *alice_secret, prime) *modular_power(runde_2_alice_an_group,2,prime))%prime) * runde_2_bob_an_group
puts alice_group_key%prime
print "bob's group Key:\t\t"
bob_group_key = ((modular_power(runde_1_alice_an_group, 3 *bob_secret, prime) * modular_power(runde_2_bob_an_group,2,prime))%prime) * runde_2_carol_an_group
puts bob_group_key%prime
print "carol's group Key:\t"
carol_group_key = ((modular_power(runde_1_bob_an_group, 3 * carol_secret, prime) * modular_power(runde_2_carol_an_group,2,prime))%prime) * runde_2_alice_an_group
puts carol_group_key%prime
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.