just some math intensive calculations (diffie hellman, group key exchanges, ...)

crazy_math.rb

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

uebung2.rb

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)

uebung3a.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

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)

uebung3b.rb

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