recover (p, q) given (n, e, d). fixes #975
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 8ca02d5..5944b90 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -8,6 +8,8 @@
* :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 fa72cce..7a22c20 100644
--- a/docs/hazmat/primitives/asymmetric/rsa.rst
+++ b/docs/hazmat/primitives/asymmetric/rsa.rst
@@ -391,6 +391,21 @@
Computes the ``dmq1`` parameter from the RSA private exponent and prime
``q``.
+.. function:: rsa_recover_prime_factors(n, e, d)
+
+ .. versionadded:: 0.8
+
+ .. note::
+
+ When recovering prime factors this algorithm will always return ``p``
+ and ``q`` such that ``p < q``.
+
+
+ Computes ``(p, q)`` given the modulus, public exponent, and private
+ exponent.
+
+ :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 0cc6b22..15aba3e 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 @@
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):
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 095ed03..3de228b 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -1698,3 +1698,36 @@
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 being willing to match against either
+ # one and then altering the asserts accordingly.
+ if p == private["p"]:
+ assert p == private["p"]
+ assert q == private["q"]
+ else:
+ assert p == private["q"]
+ assert q == private["p"]
+
+ def test_invalid_recover_prime_factors(self):
+ with pytest.raises(ValueError):
+ rsa.rsa_recover_prime_factors(34, 3, 7)