getStrongPrime() implementation

From http://lists.dlitz.net/pipermail/pycrypto/2009q4/000167.html, with the
following explanation included in the email:

=== snip ===
Hi there!

Here comes my monster patch.
It includes a python and C version of getStrongPrime, rabinMillerTest and isPrime.
there are also two small unit tests and some helper functions.
They all take a randfunc and propagate them (or so I hope).
The Rabin-Miller-Test uses random bases (non-deterministic).
getStrongPrime and isPrime take an optional parameter "false_positive_prob"
where one can specify the maximum probability that the prime is actually
composite. Internally the functions calculate the Rabin-Miller rounds from
this. It defaults to 1e-6 (1:1000000) which results in 10 rounds of Rabin-Miller
testing.

Please review this carefully. Even though I tried hard to get things right some
bugs always slip through.
maybe you could also review the way I acquire and release the GIL. It felt kind
of ugly the way I did it but I don't see a better way just now.

Concerning the public exponent e:
I now know why it needs to be coprime to p-1 and q-1. The private exponent d is
the inverse of e mod ((p-1)(q-1)).
If e is not coprime to ((p-1)(q-1)) then the inverse does not exist [1].

The getStrongPrime take an optional argument e. if provided the function will
make sure p-1 and e are coprime. if e is even (p-1)/2 will be coprime.
if e is even then there is a additional constraint: p =/= q mod 8.
I can't check for that in getStrongPrime of course but since we hardcoded e to
be odd in _RSA.py this should pose no problem.

The Baillie-PSW-Test is not included.

I tried hard not to use any functionality new than 2.1 but if you find anything
feel free to criticize. Also if I didn't get the coding style right either tell
me or feel free to correct it yourself.

have fun.
//Lorenz

[1] http://mathworld.wolfram.com/ModularInverse.html
=== snip ===

1 files changed, 20 insertions, 0 deletions

diff --git a/pct-speedtest.py b/pct-speedtest.py
index 911ffc2..c1633b9 100644
--- a/pct-speedtest.py
+++ b/pct-speedtest.py
@@ -27,6 +27,7 @@ import time
 import os
 import sys
 
+from Crypto.PublicKey import RSA
 from Crypto.Cipher import AES, ARC2, ARC4, Blowfish, CAST, DES3, DES, XOR
 from Crypto.Hash import MD2, MD4, MD5, SHA256, SHA
 try:
@@ -79,6 +80,17 @@ class Benchmark:
         sys.stdout.write("%.2f %s\n" % (value, units))
         sys.stdout.flush()
 
+    def test_pubkey_setup(self, pubkey_name, module, key_bytes):
+        self.announce_start("%s pubkey setup" % (pubkey_name,))
+        keys = self.random_keys(key_bytes)[:5]
+
+        t0 = time.time()
+        for k in keys:
+            module.generate(key_bytes*8)
+        t = time.time()
+        pubkey_setups_per_second = len(keys) / (t - t0)
+        self.announce_result(pubkey_setups_per_second, "Keys/sec")
+
     def test_key_setup(self, cipher_name, module, key_bytes, mode):
         self.announce_start("%s key setup" % (cipher_name,))
 
@@ -152,6 +164,11 @@ class Benchmark:
         self.announce_result(hash_speed / 10**6, "MBps")
 
     def run(self):
+        pubkey_specs = [
+            ("RSA(1024)", RSA, 1024/8),
+            ("RSA(2048)", RSA, 2048/8),
+            ("RSA(4096)", RSA, 4096/8),
+            ]
         block_specs = [
             ("DES", DES, 8),
             ("DES3", DES3, 24),
@@ -179,6 +196,9 @@ class Benchmark:
         if RIPEMD is not None:
             hash_specs += [("RIPEMD", RIPEMD)]
 
+        for pubkey_name, module, key_bytes in pubkey_specs:
+            self.test_pubkey_setup(pubkey_name, module, key_bytes)
+
         for cipher_name, module, key_bytes in block_specs:
             self.test_key_setup(cipher_name, module, key_bytes, module.MODE_CBC)
             self.test_encryption("%s-CBC" % (cipher_name,), module, key_bytes, module.MODE_CBC)