440,772 Members | 935 Online Need help? Post your question and get tips & solutions from a community of 440,772 IT Pros & Developers. It's quick & easy.

# Efficient (HUGE) prime modulus

 P: n/a 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); // 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 Nov 19 '07 #1
8 Replies

 P: n/a blaine

 P: n/a On Nov 19, 2007 10:32 AM, blaine

 P: n/a 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 Nov 19 '07 #4

 P: n/a 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(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. This executed almost instantaneously for me:: >>G = 23339386457661506155112559431696940974692945387305 77330470365230748185729160097289200390738424346682 52105950168946339340518077351012670847789606222728 1603 >>P =7897383601534681724700886135766287333879367007236 99479238015195118503255091498350614840009880601088 04496843165182968305834360411017401438355970579410 64647 >>import randoma = random.getrandbits(512)pow(G, a, P) 32779593927115948792218359274606928218234929455396 27585936047598704303395627109292402670858323756252 13089904773353220710094412059911879608391277133993 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 Nov 19 '07 #5

 P: n/a On Nov 19, 10:32 am, blaine

 P: n/a 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(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603) P = long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647) 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 Nov 20 '07 #7

 P: n/a blaine 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 areusing Python (as proof of concept). I am having problems though withcrunching huge numbers required for calculations. As an alternative Ican use Java - but I'd rather have a pure python implementation. Theproblem is that Python takes a very long time (I haven't had it finishyet) And it won't. Ever. Well, actually, it will finish when it crashes. >... G =long(23339386457661506155112559431696940974692945 38730577330470365230748185729160097289200390738424 34668252105950168946339340518077351012670847789606 2227281603) P =long(78973836015346817247008861357662873338793670 07236994792380151951185032550914983506148400098806 01088044968431651829683058343604110174014383559705 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. Nov 20 '07 #8

 P: n/a blaine

### This discussion thread is closed

Replies have been disabled for this discussion. 