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(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

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("2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603");
p = new
BigInteger("7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647");

// 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]

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]

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]

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

 

[Hrvoje Niksic]

Python Code:
G =
long(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

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

A = (G ** a) % P # G^a mod P [...]
I used math.pow and built-in pow. [...] Is there a python
implementation of java's Modpow?

Have you read the documentation of the built-in pow? It has exactly
the functionality you need:
.... executes in several milliseconda ...

 

[Steven Bethard]

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(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

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::
3277959392711594879221835927460692821823492945539627585936047598704303395627109292402670858323756252130899047733532207100944120599118796083912771339930412L

Did I run your algorithm wrong? Note the three argument form of 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]

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(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

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]

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(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

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...

 

[Paul Rubin]

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.