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
--
http://mail.python.org/mailman/listinfo/python-list
