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

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 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%5Fexponentiation#Right-to-left%5Fbinary%5Fmethod

Answer 4

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 5

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 6

i am a new user to python i am not getting how this is working,what libraries???, import parameters do i need to mention in my code to make it run.

can it handle exponentiation of 256 bit number as my both numbers are 256 bit, i am doing: g**x where g and x are both 256 bit.

how can i make it work using the code below:

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

can any one explain?