From c575de4f1815137a5800076ca669da911f4fd84d Mon Sep 17 00:00:00 2001 From: Lorenz Quack Date: Thu, 10 Jun 2010 21:02:07 -0400 Subject: 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 === --- pct-speedtest.py | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'pct-speedtest.py') 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) -- cgit v1.2.1