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