Efficient (HUGE) prime modulus

[blaine]

Hey guys,
For my Network Security class we are designing a project that will,
among other things, implement a Diffie Hellman secret key exchange.
The rest of the class is doing Java, while myself and a classmate are
using Python (as proof of concept). I am having problems though with
crunching huge numbers required for calculations. As an alternative I
can use Java - but I'd rather have a pure python implementation. The
problem is that Python takes a very long time (I haven't had it finish
yet) - but Java does it in 3 seconds. Suggestions?
P and G are given to us. P represents a huge prime, G is the base, a
is my secret (random) long integer. I want to compute: (G^A)%P
Python Code:
G =
long(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

a = self.rand_long(1) # 512 bit long integer

A = (G ** a) % P # G^a mod P

###### END #####
The above code takes a very long time. If I make little a only 16
bits instead of 512, it takes about 12 seconds on my machine to
compute. Is this incorrect usage of **? I used math.pow and built-in
pow. The math.pow complained about converting a long to a float. The
built in pow() took a very long time as well.

The following Java code gives me a result in 2 seconds or so.

import java.math.*;

class cruncher {
// Simple class for crunching a secret key!
public static void main(String[] args) {
BigInteger p, g, a, B, out;
out = null;
a = new BigInteger(args[1]);

// To make sure the compiler doesn't complain:
if (a == null) {
System.out.println("You must specify little a");
System.exit(1);
}
g = new
BigInteger("23339386457661506155112559431696940974 69294538730577330470365230748185729160097289200390 73842434668252105950168946339340518077351012670847 7896062227281603");
p = new
BigInteger("78973836015346817247008861357662873338 79367007236994792380151951185032550914983506148400 09880601088044968431651829683058343604110174014383 5597057941064647");

// We now have a, g, and p. Now, depending on what pass we are on,
// we will compute the appropriate output
System.out.println("Generating Secret Key(A)");
out = g.modPow(a, p);

System.out.println(out);
}
}

Any suggestions? Right now my solution is to just pipe the output from
my java program since I only need to crunch the numbers one time. Is
there a python implementation of java's Modpow?

thanks,
Blaine
University of Cincinnati

[Paul Rubin]

blaine <fr*****@gmail.comwrites:

A = (G ** a) % P # G^a mod P

Think of how large the intermediate result G**a will be. That should
explain why it's taking so long. So figure out what Java's modPow
function must be doing, and write something similar. Or, see the
docs for python's built-in pow function.

[Chris Mellon]

On Nov 19, 2007 10:32 AM, blaine <fr*****@gmail.comwrote:

Hey guys,
For my Network Security class we are designing a project that will,
among other things, implement a Diffie Hellman secret key exchange.
The rest of the class is doing Java, while myself and a classmate are
using Python (as proof of concept). I am having problems though with
crunching huge numbers required for calculations. As an alternative I
can use Java - but I'd rather have a pure python implementation. The
problem is that Python takes a very long time (I haven't had it finish
yet) - but Java does it in 3 seconds. Suggestions?

Python is quite slow for pure number crunching. Most people use the
numeric/numpy modules and/or psyco to speed up math.

Python + psyco approaches Java for the simple integer operations I've tested.

[Peter Otten]

blaine wrote:

A = (G ** a) % P # G^a mod P

###### END #####
The above code takes a very long time. If I make little a only 16 bits
instead of 512, it takes about 12 seconds on my machine to compute. Is
this incorrect usage of **? I used math.pow and built-in pow. The
math.pow complained about converting a long to a float. The built in
pow() took a very long time as well.

Even in its three-argument form?

"""
pow(...)
pow(x, y[, z]) -number

With two arguments, equivalent to x**y. With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
"""

Peter

[Steven Bethard]

blaine wrote:

Hey guys,
For my Network Security class we are designing a project that will,
among other things, implement a Diffie Hellman secret key exchange.
The rest of the class is doing Java, while myself and a classmate are
using Python (as proof of concept). I am having problems though with
crunching huge numbers required for calculations. As an alternative I
can use Java - but I'd rather have a pure python implementation. The
problem is that Python takes a very long time (I haven't had it finish
yet) - but Java does it in 3 seconds. Suggestions?
P and G are given to us. P represents a huge prime, G is the base, a
is my secret (random) long integer. I want to compute: (G^A)%P
Python Code:
G =
long(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

a = self.rand_long(1) # 512 bit long integer

A = (G ** a) % P # G^a mod P

###### END #####
The above code takes a very long time.

This executed almost instantaneously for me::

>>G =

23339386457661506155112559431696940974692945387305 77330470365230748185729160097289200390738424346682 52105950168946339340518077351012670847789606222728 1603

>>P

=7897383601534681724700886135766287333879367007236 99479238015195118503255091498350614840009880601088 04496843165182968305834360411017401438355970579410 64647

>>import random
a = random.getrandbits(512)
pow(G, a, P)

32779593927115948792218359274606928218234929455396 27585936047598704303395627109292402670858323756252 13089904773353220710094412059911879608391277133993 0412L

Did I run your algorithm wrong? Note the three argument form of pow::

>>help(pow)

Help on built-in function pow in module __builtin__:

pow(...)
pow(x, y[, z]) -number

With two arguments, equivalent to x**y. With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for
longs).

STeVe

[Paul McGuire]

On Nov 19, 10:32 am, blaine <[e-mail]:

Hey guys,
For my Network Security class we are designing a project that will,
among other things, implement a Diffie Hellman secret key exchange.
The rest of the class is doing Java, while myself and a classmate are
using Python (as proof of concept). I am having problems though with
crunching huge numbers required for calculations. As an alternative I
can use Java - but I'd rather have a pure python implementation. The
problem is that Python takes a very long time (I haven't had it finish
yet) - but Java does it in 3 seconds. Suggestions?

Did you try the 3-argument version of the built-in pow?

A = pow(G,a,P)
Takes about .1 second on my machine, with your values. (I didn't
verify that the answer I got was correct, though.)

-- Paul

[Justin Kwok]

For the interested, the algorithm that is most likely being used is
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

If you scroll down, there is a ruby implementation. Combine this with
a little bit of http://en.wikipedia.org/wiki/Modular_arithmetic and I
wrote a small python function that does what the built-in is probably
doing.

G =
long(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

import random
a = random.getrandbits(512)
#A = (G ** a) % P # G^a mod P
print pow(G, a, P)
def testpower(x, n, P):
result = 1
while n:
if n % 2:
result = (result * x) % P
n = n - 1
x = (x * x) % P
n = n / 2
return result
print testpower(G, a, P)
-Justin

[Tim Roberts]

blaine <fr*****@gmail.comwrote:

>
For my Network Security class we are designing a project that will,
among other things, implement a Diffie Hellman secret key exchange.
The rest of the class is doing Java, while myself and a classmate are
using Python (as proof of concept). I am having problems though with
crunching huge numbers required for calculations. As an alternative I
can use Java - but I'd rather have a pure python implementation. The
problem is that Python takes a very long time (I haven't had it finish
yet)

And it won't. Ever. Well, actually, it will finish when it crashes.

>...
G =
long(23339386457661506155112559431696940974692945 38730577330470365230748185729160097289200390738424 34668252105950168946339340518077351012670847789606 2227281603)
P =
long(78973836015346817247008861357662873338793670 07236994792380151951185032550914983506148400098806 01088044968431651829683058343604110174014383559705 7941064647)

a = self.rand_long(1) # 512 bit long integer

A = (G ** a) % P # G^a mod P

###### END #####
The above code takes a very long time.

We all know the proper answer (use 3-arg math.pow). However, Paul Rubin's
suggested to figure out how large (G ** a) prompted me to go do just that.
That expression is not computable on any computer on Earth today. It is a
number requiring 7 x 10**156 bits. Consider that a terabyte hard disk
today only includes 9 x 10**12 bits. Also consider that, by rough
estimate, there are approximately 10**80 atoms in the known universe
today...
--
Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.

[Paul Rubin]

blaine <fr*****@gmail.comwrites:

As an alternative I
can use Java - but I'd rather have a pure python implementation.

A number of people have suggested using 3-argument pow, but if this is
supposed to be a learning exercise, I think it's worth figuring out
for yourself how 3-argument pow is implemented in terms of ordinary
arithmetic. I'll leave it as a hint: the simplest approach is
probably recursive.