Large Exponents in Ruby?

Question

I'm just doing some University related Diffie Hellmann exercises and tried to use ruby for it. Sadly, ruby doesn't seem to be able to deal with large exponents:

warning: in a**b, b may be too big
NaN
[...]

Is there any way arround it? (e.g. a special math class or something along that line?)

p.s. here is the code in question:

generator = 7789
prime = 1017473
alice_secret = 415492
bob_secret = 725193

puts from_alice_to_bob = (generator**alice_secret) % prime
puts from_bob_to_alice = (generator**bob_secret) % prime

puts bobs_key_calculation = (from_alice_to_bob**bob_secret) % prime
puts alices_key_calculation = (from_bob_to_alice**alice_secret) % prime

Answer 1

You need to do what is called, modular exponentiation.

Answer 2

If you can use the OpenSSL bindings then you can do rapid modular exponentiation in Ruby

puts some_large_int.to_bn.mod_exp(exp,mod)

Answer 3

There's a nice way to compute a^b mod n without getting these huge numbers.

You're going to walk through the exponentiation yourself, taking the modulus at each stage. There's a trick where you can break it down into a series of powers of two.

Here's a link with an example using it to do RSA, from a course I took a while ago: Specifically, on the second page, you can see an example: http://www.math.uwaterloo.ca/~cd2rober/Math135/RSAExample.pdf

More explanation with some sample pseudocode from wikipedia: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Answer 4

I don't know ruby, but even a bignum-friendly math library is going to struggle to evaluate such an expression the naive way (7789 to the power 415492 has approximately 1.6 million digits).

The way to work out a^b mod p without blowing up is to do the mod ping at every exponentiation - I would guess that the language isn't working this out on its own and therefore must be helped.

Answer 5

I've made some attempts of my own. Exponentiation by squaring works well so far, but same problem with bigNum. such a recursive thing as

def exponentiation(base, exp, y = 1)
    if(exp == 0)
        return y
    end
    case exp%2
        when 0 then 
            exp = exp/2
            base = (base*base)%@@mod
            exponentiation(base, exp,  y)
        when 1 then
            y = (base*y)%@@mod
            exp = exp - 1
            exponentiation(base, exp, y) 
    end
end

however, it would be, as I'm realizing, a terrible idea to rely on ruby's prime class for anything substantial. Ruby uses the Sieve of Eratosthenes for it's prime generator, but even worse, it uses Trial division for gcd's and such....

oh, and @@mod was a class variable, so if you plan on using this yourselves, you might want to add it as a param or something. I've gotten it to work quite quickly for

puts a.exponentiation(100000000000000, 1222555345678)

numbers in that range.

(using @@mod = 80233)

Answer 6

OK, got the squaring method to work for

a = Mod.new(80233788)
puts a.exponentiation(298989898980988987789898789098767978698745859720452521, 12225553456987474747474744778)

output: 59357797

I think that should be sufficient for any problem you might have in your Crypto course

Answer 7

If you really want to go to BIG modular exponentiation, here is an implementation from the wiki page.

#base expantion number to selected base 
def baseExpantion(number, base)
   q = number
   k = ""
   while q > 0 do
     a = q % base
     q = q / base
     k = a.to_s() + k
   end
     return k
end

#iterative for modular exponentiation 
def modular(n, b, m)
   x = 1
   power = baseExpantion(b, 2) #base two
   i = power.size - 1
   if power.split("")[i] == "1"
      x = x * n
      x = x % m
   end
   while i > 0 do
      n *= n
      n = n % m
      if power.split("")[i-1] == "1"
         x *= n
         x = x % m
      end
      i -= 1
   end
   return x
end

Results, where tested with wolfram alpha

Answer 8

This is inspired by right-to-left binary method example on Wikipedia:

def powmod(base, exponent, modulus)
  return modulus==1 ? 0 : begin
    result = 1 
    base = base % modulus
    while exponent > 0 
      result = result*base%modulus if exponent%2 == 1
      exponent = exponent >> 1
      base = base*base%modulus
    end 
  result
  end 
end