Merge pull request #935 from public/rsa-crt

Utility methods for RSA CRT params

3 files changed, 75 insertions, 17 deletions

diff --git a/cryptography/hazmat/primitives/asymmetric/rsa.py b/cryptography/hazmat/primitives/asymmetric/rsa.py
index 94cc4645..5b15350a 100644
--- a/cryptography/hazmat/primitives/asymmetric/rsa.py
+++ b/cryptography/hazmat/primitives/asymmetric/rsa.py
@@ -73,6 +73,42 @@ class RSAPublicKey(object):
         return self.modulus
 
 
+def _modinv(e, m):
+    """
+    Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1
+    """
+    x1, y1, x2, y2 = 1, 0, 0, 1
+    a, b = e, m
+    while b > 0:
+        q, r = divmod(a, b)
+        xn, yn = x1 - q * x2, y1 - q * y2
+        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
+    return x1 % m
+
+
+def rsa_crt_iqmp(p, q):
+    """
+    Compute the CRT (q ** -1) % p value from RSA primes p and q.
+    """
+    return _modinv(q, p)
+
+
+def rsa_crt_dmp1(private_exponent, p):
+    """
+    Compute the CRT private_exponent % (p - 1) value from the RSA
+    private_exponent and p.
+    """
+    return private_exponent % (p - 1)
+
+
+def rsa_crt_dmq1(private_exponent, q):
+    """
+    Compute the CRT private_exponent % (q - 1) value from the RSA
+    private_exponent and q.
+    """
+    return private_exponent % (q - 1)
+
+
 @utils.register_interface(interfaces.RSAPrivateKey)
 class RSAPrivateKey(object):
     def __init__(self, p, q, private_exponent, dmp1, dmq1, iqmp,
diff --git a/docs/hazmat/primitives/asymmetric/rsa.rst b/docs/hazmat/primitives/asymmetric/rsa.rst
index 5074f1c5..c9de2831 100644
--- a/docs/hazmat/primitives/asymmetric/rsa.rst
+++ b/docs/hazmat/primitives/asymmetric/rsa.rst
@@ -214,7 +214,42 @@ RSA
             too large for the key size.
 
 
+Handling partial RSA private keys
+---------------------------------
+
+If you are trying to load RSA private keys yourself you may find that not all
+parameters required by ``RSAPrivateKey`` are available. In particular the
+`Chinese Remainder Theorem`_ (CRT) values ``dmp1``, ``dmq1``, ``iqmp`` may be
+missing or present in a different form. For example `OpenPGP`_ does not include
+the ``iqmp``, ``dmp1`` or ``dmq1`` parameters. 
+
+The following functions are provided for users who want to work with keys like
+this without having to do the math themselves.
+
+.. function:: rsa_crt_iqmp(p, q)
+
+    .. versionadded:: 0.4
+
+    Generates the ``iqmp`` (also known as ``qInv``) parameter from the RSA
+    primes ``p`` and ``q``.
+
+.. function:: rsa_crt_dmp1(private_exponent, p)
+
+    .. versionadded:: 0.4
+
+    Generates the ``dmp1`` parameter from the RSA private exponent and prime
+    ``p``.
+
+.. function:: rsa_crt_dmq1(private_exponent, q)
+    
+    .. versionadded:: 0.4
+
+    Generates the ``dmq1`` parameter from the RSA private exponent and prime
+    ``q``.
+
 .. _`RSA`: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
 .. _`public-key`: https://en.wikipedia.org/wiki/Public-key_cryptography
 .. _`use 65537`: http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html
 .. _`at least 2048`: http://www.ecrypt.eu.org/documents/D.SPA.20.pdf
+.. _`OpenPGP`: https://en.wikipedia.org/wiki/Pretty_Good_Privacy
+.. _`Chinese Remainder Theorem`: http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Using_the_Chinese_remainder_algorithm
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 1cbd1636..84d0f805 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -42,19 +42,6 @@ class DummyMGF(object):
     _salt_length = 0
 
 
-def _modinv(e, m):
-    """
-    Modular Multiplicative Inverse.  Returns x such that: (x*e) mod m == 1
-    """
-    x1, y1, x2, y2 = 1, 0, 0, 1
-    a, b = e, m
-    while b > 0:
-        q, r = divmod(a, b)
-        xn, yn = x1 - q * x2, y1 - q * y2
-        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
-    return x1 % m
-
-
 def _check_rsa_private_key(skey):
     assert skey
     assert skey.modulus
@@ -62,9 +49,9 @@ def _check_rsa_private_key(skey):
     assert skey.private_exponent
     assert skey.p * skey.q == skey.modulus
     assert skey.key_size
-    assert skey.dmp1 == skey.d % (skey.p - 1)
-    assert skey.dmq1 == skey.d % (skey.q - 1)
-    assert skey.iqmp == _modinv(skey.q, skey.p)
+    assert skey.dmp1 == rsa.rsa_crt_dmp1(skey.d, skey.p)
+    assert skey.dmq1 == rsa.rsa_crt_dmq1(skey.d, skey.q)
+    assert skey.iqmp == rsa.rsa_crt_iqmp(skey.p, skey.q)
 
     pkey = skey.public_key()
     assert pkey
@@ -97,7 +84,7 @@ def test_modular_inverse():
         "b2347cfcd669133088d1c159518531025297c2d67c9da856a12e80222cd03b4c6ec0f"
         "86c957cb7bb8de7a127b645ec9e820aa94581e4762e209f01", 16
     )
-    assert _modinv(q, p) == int(
+    assert rsa._modinv(q, p) == int(
         "0275e06afa722999315f8f322275483e15e2fb46d827b17800f99110b269a6732748f"
         "624a382fa2ed1ec68c99f7fc56fb60e76eea51614881f497ba7034c17dde955f92f15"
         "772f8b2b41f3e56d88b1e096cdd293eba4eae1e82db815e0fadea0c4ec971bc6fd875"