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