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(2333938645 766150615511255 943169694097469 294538730577330 470365230748185 729160097289200 390738424346682 521059501689463 393405180773510 126708477896062 227281603)
P =
long(7897383601 534681724700886 135766287333879 367007236994792 380151951185032 550914983506148 400098806010880 449684316518296 830583436041101 740143835597057 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.prin tln("You must specify little a");
System.exit(1);
}
g = new
BigInteger("233 393864576615061 551125594316969 409746929453873 057733047036523 074818572916009 728920039073842 434668252105950 168946339340518 077351012670847 789606222728160 3");
p = new
BigInteger("789 738360153468172 470088613576628 733387936700723 699479238015195 118503255091498 350614840009880 601088044968431 651829683058343 604110174014383 559705794106464 7");

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

System.out.prin tln(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(2333938645 766150615511255 943169694097469 294538730577330 470365230748185 729160097289200 390738424346682 521059501689463 393405180773510 126708477896062 227281603)
P =
long(7897383601 534681724700886 135766287333879 367007236994792 380151951185032 550914983506148 400098806010880 449684316518296 830583436041101 740143835597057 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 =

233393864576615 061551125594316 969409746929453 873057733047036 523074818572916 009728920039073 842434668252105 950168946339340 518077351012670 847789606222728 1603

>>P

=78973836015346 817247008861357 662873338793670 072369947923801 519511850325509 149835061484000 988060108804496 843165182968305 834360411017401 438355970579410 64647

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

327795939271159 487922183592746 069282182349294 553962758593604 759870430339562 710929240267085 832375625213089 904773353220710 094412059911879 608391277133993 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 <frik...@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?

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(2333938645 766150615511255 943169694097469 294538730577330 470365230748185 729160097289200 390738424346682 521059501689463 393405180773510 126708477896062 227281603)
P =
long(7897383601 534681724700886 135766287333879 367007236994792 380151951185032 550914983506148 400098806010880 449684316518296 830583436041101 740143835597057 941064647)

import random
a = random.getrandb its(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(233393864 576615061551125 594316969409746 929453873057733 047036523074818 572916009728920 039073842434668 252105950168946 339340518077351 012670847789606 2227281603)
P =
long(789738360 153468172470088 613576628733387 936700723699479 238015195118503 255091498350614 840009880601088 044968431651829 683058343604110 174014383559705 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.