Large Exponents in Ruby?
I'm just doing some University related Diffie-Hellman 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 around it? (e.g. a special math class or something along that line?)
p.s. here is the code in question:
generator = 7789
prime = 1开发者_Go百科017473
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
You need to do what is called, modular exponentiation.
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)
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
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 p
ing at every exponentiation - I would guess that the language isn't working this out on its own and therefore must be helped.
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)
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
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
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
精彩评论