Added basic Chinese Remainder theorem implementation, not yet used.

2 files changed, 79 insertions, 30 deletions

diff --git a/rsa/common.py b/rsa/common.py
index 5ae92f0..4d7698f 100644
--- a/rsa/common.py
+++ b/rsa/common.py
@@ -69,6 +69,80 @@ def byte_size(number):
 
     return int(math.ceil(bit_size(number) / 8.0))
 
+
+def extended_gcd(a, b):
+    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
+    """
+    # r = gcd(a,b) i = multiplicitive inverse of a mod b
+    #      or      j = multiplicitive inverse of b mod a
+    # Neg return values for i or j are made positive mod b or a respectively
+    # Iterateive Version is faster and uses much less stack space
+    x = 0
+    y = 1
+    lx = 1
+    ly = 0
+    oa = a                             #Remember original a/b to remove 
+    ob = b                             #negative values from return results
+    while b != 0:
+        q = a // b
+        (a, b)  = (b, a % b)
+        (x, lx) = ((lx - (q * x)),x)
+        (y, ly) = ((ly - (q * y)),y)
+    if (lx < 0): lx += ob              #If neg wrap modulo orignal b
+    if (ly < 0): ly += oa              #If neg wrap modulo orignal a
+    return (a, lx, ly)                 #Return only positive values
+
+def inverse(x, n):
+    '''Returns x^-1 (mod n)
+    
+    >>> inverse(7, 4)
+    3
+    >>> (inverse(143, 4) * 143) % 4
+    1
+    '''
+
+    (divider, inv, _) = extended_gcd(x, n)
+
+    if divider != 1:
+        raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n))
+
+    return inv
+
+
+def crt(a_values, modulo_values):
+    '''Chinese Remainder Theorem.
+
+    Calculates x such that x = a[i] (mod m[i]) for each i.
+
+    :param a_values: the a-values of the above equation
+    :param modulo_values: the m-values of the above equation
+    :returns: x such that x = a[i] (mod m[i]) for each i
+    
+
+    >>> crt([2, 3], [3, 5])
+    8
+
+    >>> crt([2, 3, 2], [3, 5, 7])
+    23
+
+    >>> crt([2, 3, 0], [7, 11, 15])
+    135
+    '''
+
+    m = 1
+    x = 0 
+
+    for modulo in modulo_values:
+        m *= modulo
+
+    for (m_i, a_i) in zip(modulo_values, a_values):
+        M_i = m // m_i
+        inv = inverse(M_i, m_i)
+
+        x = (x + a_i * M_i * inv) % m
+
+    return x
+
 if __name__ == '__main__':
     import doctest
     doctest.testmod()
diff --git a/rsa/key.py b/rsa/key.py
index 489500a..479b8f0 100644
--- a/rsa/key.py
+++ b/rsa/key.py
@@ -264,7 +264,7 @@ class PrivateKey(AbstractKey):
             self.exp2 = exp2
 
         if coef is None:
-            (_, self.coef, _) = extended_gcd(q, p)
+            self.coef = rsa.common.inverse(q, p)
         else:
             self.coef = coef
 
@@ -398,29 +398,6 @@ class PrivateKey(AbstractKey):
         der = self._save_pkcs1_der()
         return rsa.pem.save_pem(der, 'RSA PRIVATE KEY')
 
-
-def extended_gcd(a, b):
-    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
-    """
-    # r = gcd(a,b) i = multiplicitive inverse of a mod b
-    #      or      j = multiplicitive inverse of b mod a
-    # Neg return values for i or j are made positive mod b or a respectively
-    # Iterateive Version is faster and uses much less stack space
-    x = 0
-    y = 1
-    lx = 1
-    ly = 0
-    oa = a                             #Remember original a/b to remove 
-    ob = b                             #negative values from return results
-    while b != 0:
-        q = a // b
-        (a, b)  = (b, a % b)
-        (x, lx) = ((lx - (q * x)),x)
-        (y, ly) = ((ly - (q * y)),y)
-    if (lx < 0): lx += ob              #If neg wrap modulo orignal b
-    if (ly < 0): ly += oa              #If neg wrap modulo orignal a
-    return (a, lx, ly)                 #Return only positive values
-
 def find_p_q(nbits, getprime_func=rsa.prime.getprime, accurate=True):
     ''''Returns a tuple of two different primes of nbits bits each.
     
@@ -509,14 +486,12 @@ def calculate_keys(p, q, nbits):
     # A very common choice for e is 65537
     e = 65537
 
-    (divider, d, _) = extended_gcd(e, phi_n)
-
-    if divider != 1:
+    try:
+        d = rsa.common.inverse(e, phi_n)
+    except ValueError:
         raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
                 (e, phi_n))
-    if (d < 0):
-        raise ValueError("extended_gcd shouldn't return negative values, "
-                "please file a bug")
+
     if (e * d) % phi_n != 1:
         raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
                 "phi_n (%d)" % (e, d, phi_n))