diff options
author | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-08-10 13:51:40 +0200 |
---|---|---|
committer | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-08-10 13:51:40 +0200 |
commit | 64f9e1d493d85a46956ff86677afec2692ebe49a (patch) | |
tree | 75817f9df370cfa23f88ea396749a4f626b07b41 | |
parent | 360d04285b64c981d8909c2f6393c60439370b3a (diff) | |
download | rsa-git-64f9e1d493d85a46956ff86677afec2692ebe49a.tar.gz |
Added basic Chinese Remainder theorem implementation, not yet used.
-rw-r--r-- | rsa/common.py | 74 | ||||
-rw-r--r-- | rsa/key.py | 35 |
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() @@ -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)) |