Merge pull request #1633 from reaperhulk/fix-975

recover (p, q) given (n, e, d)

4 files changed, 94 insertions, 0 deletions

diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 8ca02d51..5944b907 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -8,6 +8,8 @@ Changelog
 
 * :func:`~cryptography.hazmat.primitives.serialization.load_ssh_public_key` can
   now load elliptic curve public keys.
+* Added
+  :func:`~cryptography.hazmat.primitives.asymmetric.rsa.rsa_recover_prime_factors`
 
 0.7.2 - 2015-01-16
 ~~~~~~~~~~~~~~~~~~
diff --git a/docs/hazmat/primitives/asymmetric/rsa.rst b/docs/hazmat/primitives/asymmetric/rsa.rst
index fa72cced..3c095a54 100644
--- a/docs/hazmat/primitives/asymmetric/rsa.rst
+++ b/docs/hazmat/primitives/asymmetric/rsa.rst
@@ -391,6 +391,20 @@ this without having to do the math themselves.
     Computes the ``dmq1`` parameter from the RSA private exponent and prime
     ``q``.
 
+.. function:: rsa_recover_prime_factors(n, e, d)
+
+    .. versionadded:: 0.8
+
+    Computes the prime factors ``(p, q)`` given the modulus, public exponent,
+    and private exponent.
+
+    .. note::
+
+        When recovering prime factors this algorithm will always return ``p``
+        and ``q`` such that ``p < q``.
+
+    :return: A tuple ``(p, q)``
+
 
 .. _`RSA`: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
 .. _`public-key`: https://en.wikipedia.org/wiki/Public-key_cryptography
diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py
index 0cc6b22b..47bdf5cb 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,55 @@ 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
+    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 = False
+    a = 2
+    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:
+        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 = True
+                break
+            k *= 2
+        # This value was not any good... let's try another!
+        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):
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 095ed037..33e5373b 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -1698,3 +1698,30 @@ class TestRSANumbersEquality(object):
             1, 2, 3, 4, 5, 6, RSAPublicNumbers(1, 3)
         )
         assert num != object()
+
+
+class TestRSAPrimeFactorRecovery(object):
+    @pytest.mark.parametrize(
+        "vector",
+        _flatten_pkcs1_examples(load_vectors_from_file(
+            os.path.join(
+                "asymmetric", "RSA", "pkcs1v15crypt-vectors.txt"),
+            load_pkcs1_vectors
+        ))
+    )
+    def test_recover_prime_factors(self, vector):
+        private, public, example = vector
+        p, q = rsa.rsa_recover_prime_factors(
+            private["modulus"],
+            private["public_exponent"],
+            private["private_exponent"]
+        )
+        # Unfortunately there is no convention on which prime should be p
+        # and which one q. The function we use always makes p < q, but the
+        # NIST vectors are not so consistent. Accordingly we verify we've
+        # recovered the proper (p, q) by sorting them and asserting on that.
+        assert sorted([p, q]) == sorted([private["p"], private["q"]])
+
+    def test_invalid_recover_prime_factors(self):
+        with pytest.raises(ValueError):
+            rsa.rsa_recover_prime_factors(34, 3, 7)