From 836b830b155c1b04fbad40ab76f0de4339d8628c Mon Sep 17 00:00:00 2001 From: Paul Kehrer Date: Sun, 18 Jan 2015 09:42:58 -0600 Subject: recover (p, q) given (n, e, d). fixes #975 --- .../hazmat/primitives/asymmetric/rsa.py | 45 ++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'src') diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py index 0cc6b22b..15aba3e4 100644 --- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py +++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py @@ -4,6 +4,8 @@ from __future__ import absolute_import, division, print_function +from fractions import gcd + import six from cryptography import utils @@ -119,6 +121,49 @@ def rsa_crt_dmq1(private_exponent, q): return private_exponent % (q - 1) +def rsa_recover_prime_factors(n, e, d): + """ + Compute factors p and q from the private exponent d. We assume that n has + no more than two factors. This function is adapted from code in PyCrypto. + """ + # See 8.2.2(i) in Handbook of Applied Cryptography. + ktot = d * e - 1 + # The quantity d*e-1 is a multiple of phi(n), even, + # and can be represented as t*2^s. + t = ktot + while t % 2 == 0: + t = t // 2 + # Cycle through all multiplicative inverses in Zn. + # The algorithm is non-deterministic, but there is a 50% chance + # any candidate a leads to successful factoring. + # See "Digitalized Signatures and Public Key Functions as Intractable + # as Factorization", M. Rabin, 1979 + spotted = 0 + a = 2 + while not spotted and a < 1000: + k = t + # Cycle through all values a^{t*2^i}=a^k + while k < ktot: + cand = pow(a, k, n) + # Check if a^k is a non-trivial root of unity (mod n) + if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1: + # We have found a number such that (cand-1)(cand+1)=0 (mod n). + # Either of the terms divides n. + p = gcd(cand + 1, n) + spotted = 1 + break + k = k * 2 + # This value was not any good... let's try another! + a = a + 2 + if not spotted: + raise ValueError("Unable to compute factors p and q from exponent d.") + # Found ! + q, r = divmod(n, p) + assert r == 0 + + return (p, q) + + class RSAPrivateNumbers(object): def __init__(self, p, q, d, dmp1, dmq1, iqmp, public_numbers): -- cgit v1.2.3 From aca05e6c7d7efff451c3f149d0e9e12d34a63a9f Mon Sep 17 00:00:00 2001 From: Paul Kehrer Date: Sun, 18 Jan 2015 10:02:53 -0600 Subject: various improvements to rsa_recover_prime_factors per review feedback --- src/cryptography/hazmat/primitives/asymmetric/rsa.py | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py index 15aba3e4..d267c387 100644 --- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py +++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py @@ -138,7 +138,7 @@ def rsa_recover_prime_factors(n, e, d): # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 - spotted = 0 + spotted = False a = 2 while not spotted and a < 1000: k = t @@ -150,11 +150,11 @@ def rsa_recover_prime_factors(n, e, d): # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. p = gcd(cand + 1, n) - spotted = 1 + spotted = True break - k = k * 2 + k *= 2 # This value was not any good... let's try another! - a = a + 2 + a += 2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! -- cgit v1.2.3 From 1f6765d9ba5df9ff2089a197a64e335e04206c37 Mon Sep 17 00:00:00 2001 From: Paul Kehrer Date: Sun, 18 Jan 2015 11:18:09 -0600 Subject: move attempts to a constant and add a comment about it --- src/cryptography/hazmat/primitives/asymmetric/rsa.py | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py index d267c387..47bdf5cb 100644 --- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py +++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py @@ -121,6 +121,12 @@ def rsa_crt_dmq1(private_exponent, q): return private_exponent % (q - 1) +# Controls the number of iterations rsa_recover_prime_factors will perform +# to obtain the prime factors. Each iteration increments by 2 so the actual +# maximum attempts is half this number. +_MAX_RECOVERY_ATTEMPTS = 1000 + + def rsa_recover_prime_factors(n, e, d): """ Compute factors p and q from the private exponent d. We assume that n has @@ -140,7 +146,7 @@ def rsa_recover_prime_factors(n, e, d): # as Factorization", M. Rabin, 1979 spotted = False a = 2 - while not spotted and a < 1000: + while not spotted and a < _MAX_RECOVERY_ATTEMPTS: k = t # Cycle through all values a^{t*2^i}=a^k while k < ktot: -- cgit v1.2.3