added accurate bit size for key generation

2 files changed, 92 insertions, 12 deletions

diff --git a/load_private.py b/load_private.py
new file mode 100755
index 0000000..d6dd7bd
--- /dev/null
+++ b/load_private.py
@@ -0,0 +1,55 @@
+#!/usr/bin/env python
+
+from rsa import pkcs1, key
+
+# pick q, pick p
+# [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 6, 7, 10, 14, 23, 46]
+# Median:  2
+# Average: 6.8
+
+# pick p, pick q
+# [1, 1, 2, 3, 3, 3, 4, 5, 5, 7, 7, 9, 10, 13, 14, 15, 16, 16, 23, 49]
+# Median:  7
+# Average: 10.3
+
+# pick both
+# [1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 7, 8, 10, 13, 14, 21]
+# Median:  5
+# Average: 6.1
+
+
+
+tries = [key.find_p_q(512) for _ in range(20)]
+tries = sorted(tries)
+print tries
+print 'Median: ', tries[len(tries) // 2]
+print 'Average:', sum(tries) / float(len(tries))
+
+#(pub_key, priv_key) = key.newkeys(1024)
+#
+#print priv_key
+#
+#with open('mykey.pem', 'w') as mykey:
+#    mykey.write(priv_key.save_pkcs1_pem())
+
+#with open('mykey.der', 'w') as mykey:
+#    mykey.write(priv_key.save_pkcs1_der())
+
+
+
+# Write the message file
+#message = 'je moeder\n'
+#with open('message.txt', 'w') as out:
+#    out.write(message)
+
+# Encrypt the message
+#msg = pkcs1.encrypt(message, pub_key)
+#with open('message.rsa', 'w') as out:
+#    out.write(msg)
+
+# Sign the message
+#signature = pkcs1.sign(message, priv_key, 'SHA-256')
+#with open('message.sig', 'w') as out:
+#    out.write(signature)
+
+
diff --git a/rsa/key.py b/rsa/key.py
index 01168db..233bb30 100644
--- a/rsa/key.py
+++ b/rsa/key.py
@@ -11,6 +11,7 @@ of pyasn1.
 
 import rsa.prime
 import rsa.pem
+import rsa.common
 
 
 class PublicKey(object):
@@ -266,31 +267,55 @@ def find_p_q(nbits):
     
     >>> (p, q) = find_p_q(128)
     
-    The resulting p and q should be very close to 2*nbits bits, and no more
-    than 2*nbits bits:
+    The resulting p * q has exacty 2 * nbits bits
     >>> from rsa import common
-    >>> common.bit_size(p * q) <= 256
-    True
-    >>> common.bit_size(p * q) > 240
-    True
+    >>> common.bit_size(p * q)
+    256
     
     '''
     
+    total_bits = nbits * 2
+
     # Make sure that p and q aren't too close or the factoring programs can
     # factor n.
-    shift = nbits // 16
+    shift = nbits // 8
     pbits = nbits + shift
     qbits = nbits - shift
     
+    # Choose the two initial primes
     p = rsa.prime.getprime(pbits)
-    
+    q = rsa.prime.getprime(qbits)
+
+    # Keep choosing other primes until they match our requirements.
+    #   - p and q differ
+    #   - p * q has exactly total_bits bits.
+
+    tries = 0
     while True:
-        q = rsa.prime.getprime(qbits)
+        tries += 1
 
         # Make sure p and q are different.
-        if q != p: break
-        
-    return (p, q)
+        # Make sure we have just the right amount of bits
+        found_size = rsa.common.bit_size(p * q)
+        diff = (total_bits - found_size)
+
+        if p != q and not diff:
+            break
+            
+        # Change p on one iteration and q on the other
+        if tries & 1:
+            print 'Try %i, change q' % tries
+            qbits += diff
+            q = rsa.prime.getprime(qbits)
+        else:
+            print 'Try %i, change p' % tries
+            pbits += diff
+            p = rsa.prime.getprime(pbits)
+
+    # In the end we want p > q as described on
+    # http://www.di-mgt.com.au/rsa_alg.html#crt
+    #return (max(p, q), min(p, q))
+    return tries
 
 def calculate_keys(p, q, nbits):
     """Calculates an encryption and a decryption key given p and q, and