Prepared for key generation with CRT

4 files changed, 53 insertions, 27 deletions

diff --git a/rsa/common.py b/rsa/common.py
index 4d7698f..032f4dd 100644
--- a/rsa/common.py
+++ b/rsa/common.py
@@ -69,6 +69,18 @@ def byte_size(number):
 
     return int(math.ceil(bit_size(number) / 8.0))
 
+def gcd(p, q):
+    """Returns the greatest common divisor of p and q
+
+    >>> gcd(48, 180)
+    12
+    """
+
+    while q != 0:
+        if p < q: (p,q) = (q,p)
+        (p,q) = (q, p % q)
+    return p
+    
 
 def extended_gcd(a, b):
     """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
@@ -139,9 +151,9 @@ def crt(a_values, modulo_values):
         M_i = m // m_i
         inv = inverse(M_i, m_i)
 
-        x = (x + a_i * M_i * inv) % m
+        x += a_i * M_i * inv
 
-    return x
+    return x % m
 
 if __name__ == '__main__':
     import doctest
diff --git a/rsa/key.py b/rsa/key.py
index 479b8f0..56c47e7 100644
--- a/rsa/key.py
+++ b/rsa/key.py
@@ -430,13 +430,8 @@ def find_p_q(nbits, getprime_func=rsa.prime.getprime, accurate=True):
     '''
     
     total_bits = nbits * 2
+    pbits = qbits = nbits
 
-    # Make sure that p and q aren't too close or the factoring programs can
-    # factor n.
-    shift = nbits // 16
-    pbits = nbits + shift
-    qbits = nbits - shift
-    
     # Choose the two initial primes
     log.debug('find_p_q(%i): Finding p', nbits)
     p = getprime_func(pbits)
@@ -453,12 +448,15 @@ def find_p_q(nbits, getprime_func=rsa.prime.getprime, accurate=True):
         if p == q:
             return False
 
-        if not accurate:
-            return True
+        if accurate:
+            # Make sure we have just the right amount of bits
+            found_size = rsa.common.bit_size(p * q)
+            if total_bits != found_size:
+                return False
+
+        # Make sure that gcd(p-1, q-1) = 2, for CRT
+        return rsa.common.gcd(p-1, q-1) == 2
 
-        # Make sure we have just the right amount of bits
-        found_size = rsa.common.bit_size(p * q)
-        return total_bits == found_size
 
     # Keep choosing other primes until they match our requirements.
     change_p = False
diff --git a/rsa/prime.py b/rsa/prime.py
index 340ab94..2157647 100644
--- a/rsa/prime.py
+++ b/rsa/prime.py
@@ -23,19 +23,8 @@ Roberto Tamassia, 2002.
 __all__ = [ 'getprime', 'are_relatively_prime']
 
 import rsa.randnum
+import rsa.common
 
-def gcd(p, q):
-    """Returns the greatest common divisor of p and q
-
-    >>> gcd(48, 180)
-    12
-    """
-
-    while q != 0:
-        if p < q: (p,q) = (q,p)
-        (p,q) = (q, p % q)
-    return p
-    
 
 def jacobi(a, b):
     """Calculates the value of the Jacobi symbol (a/b) where both a and b are
@@ -137,7 +126,6 @@ def getprime(nbits):
 
         # Retry if not prime
 
-
 def are_relatively_prime(a, b):
     """Returns True if a and b are relatively prime, and False if they
     are not.
@@ -148,7 +136,7 @@ def are_relatively_prime(a, b):
     0
     """
 
-    d = gcd(a, b)
+    d = rsa.common.gcd(a, b)
     return (d == 1)
     
 if __name__ == '__main__':
diff --git a/tests/test_keygen.py b/tests/test_keygen.py
new file mode 100644
index 0000000..fdf6860
--- /dev/null
+++ b/tests/test_keygen.py
@@ -0,0 +1,28 @@
+'''Tests string operations.'''
+
+import struct
+import unittest
+
+import rsa
+from rsa.common import gcd
+
+class KeyGenTest(unittest.TestCase):
+
+    def test_exp_coef(self):
+        '''Tests the exp1, exp2 and coef values.'''
+
+        (_, priv) = rsa.newkeys(256)
+
+        self.assertEqual(gcd(priv.exp1, priv.p - 1), 1)
+        self.assertEqual(gcd(priv.exp2, priv.q - 1), 1)
+
+        self.assertEqual(priv.d    % (priv.p - 1),
+                         priv.exp1 % (priv.p - 1))
+
+        self.assertEqual(priv.d    % (priv.q - 1),
+                         priv.exp2 % (priv.q - 1))
+
+
+        self.assertEqual(priv.exp1 % 2, priv.exp2 % 2)
+
+