We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
rsa.rsa_recover_prime_factors() should return p > q
The documentation for `rsa_recover_prime_factors()` warns that it returns `p` and `q` such that `p < q`. However, things like OpenSSL and BoringSSL seem to require that `p > q`. Given this, would it be feasible to change the order around in cryptography so that it lines up with OpenSSL?

See also: http://crypto.stackexchange.com/questions/18084/in-rsa-why-does-p-have-to-be-bigger-than-q-where-n-p-times-q. @briansmith can provide more commentary if needed.


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/cryptography/hazmat/primitives/asymmetric/rsa.py`
Content:
```
1 # This file is dual licensed under the terms of the Apache License, Version
2 # 2.0, and the BSD License. See the LICENSE file in the root of this repository
3 # for complete details.
4 
5 from __future__ import absolute_import, division, print_function
6 
7 import abc
8 from fractions import gcd
9 
10 import six
11 
12 from cryptography import utils
13 from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
14 from cryptography.hazmat.backends.interfaces import RSABackend
15 
16 
17 @six.add_metaclass(abc.ABCMeta)
18 class RSAPrivateKey(object):
19     @abc.abstractmethod
20     def signer(self, padding, algorithm):
21         """
22         Returns an AsymmetricSignatureContext used for signing data.
23         """
24 
25     @abc.abstractmethod
26     def decrypt(self, ciphertext, padding):
27         """
28         Decrypts the provided ciphertext.
29         """
30 
31     @abc.abstractproperty
32     def key_size(self):
33         """
34         The bit length of the public modulus.
35         """
36 
37     @abc.abstractmethod
38     def public_key(self):
39         """
40         The RSAPublicKey associated with this private key.
41         """
42 
43     @abc.abstractmethod
44     def sign(self, data, padding, algorithm):
45         """
46         Signs the data.
47         """
48 
49 
50 @six.add_metaclass(abc.ABCMeta)
51 class RSAPrivateKeyWithSerialization(RSAPrivateKey):
52     @abc.abstractmethod
53     def private_numbers(self):
54         """
55         Returns an RSAPrivateNumbers.
56         """
57 
58     @abc.abstractmethod
59     def private_bytes(self, encoding, format, encryption_algorithm):
60         """
61         Returns the key serialized as bytes.
62         """
63 
64 
65 @six.add_metaclass(abc.ABCMeta)
66 class RSAPublicKey(object):
67     @abc.abstractmethod
68     def verifier(self, signature, padding, algorithm):
69         """
70         Returns an AsymmetricVerificationContext used for verifying signatures.
71         """
72 
73     @abc.abstractmethod
74     def encrypt(self, plaintext, padding):
75         """
76         Encrypts the given plaintext.
77         """
78 
79     @abc.abstractproperty
80     def key_size(self):
81         """
82         The bit length of the public modulus.
83         """
84 
85     @abc.abstractmethod
86     def public_numbers(self):
87         """
88         Returns an RSAPublicNumbers
89         """
90 
91     @abc.abstractmethod
92     def public_bytes(self, encoding, format):
93         """
94         Returns the key serialized as bytes.
95         """
96 
97     @abc.abstractmethod
98     def verify(self, signature, data, padding, algorithm):
99         """
100         Verifies the signature of the data.
101         """
102 
103 
104 RSAPublicKeyWithSerialization = RSAPublicKey
105 
106 
107 def generate_private_key(public_exponent, key_size, backend):
108     if not isinstance(backend, RSABackend):
109         raise UnsupportedAlgorithm(
110             "Backend object does not implement RSABackend.",
111             _Reasons.BACKEND_MISSING_INTERFACE
112         )
113 
114     _verify_rsa_parameters(public_exponent, key_size)
115     return backend.generate_rsa_private_key(public_exponent, key_size)
116 
117 
118 def _verify_rsa_parameters(public_exponent, key_size):
119     if public_exponent < 3:
120         raise ValueError("public_exponent must be >= 3.")
121 
122     if public_exponent & 1 == 0:
123         raise ValueError("public_exponent must be odd.")
124 
125     if key_size < 512:
126         raise ValueError("key_size must be at least 512-bits.")
127 
128 
129 def _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,
130                                   public_exponent, modulus):
131     if modulus < 3:
132         raise ValueError("modulus must be >= 3.")
133 
134     if p >= modulus:
135         raise ValueError("p must be < modulus.")
136 
137     if q >= modulus:
138         raise ValueError("q must be < modulus.")
139 
140     if dmp1 >= modulus:
141         raise ValueError("dmp1 must be < modulus.")
142 
143     if dmq1 >= modulus:
144         raise ValueError("dmq1 must be < modulus.")
145 
146     if iqmp >= modulus:
147         raise ValueError("iqmp must be < modulus.")
148 
149     if private_exponent >= modulus:
150         raise ValueError("private_exponent must be < modulus.")
151 
152     if public_exponent < 3 or public_exponent >= modulus:
153         raise ValueError("public_exponent must be >= 3 and < modulus.")
154 
155     if public_exponent & 1 == 0:
156         raise ValueError("public_exponent must be odd.")
157 
158     if dmp1 & 1 == 0:
159         raise ValueError("dmp1 must be odd.")
160 
161     if dmq1 & 1 == 0:
162         raise ValueError("dmq1 must be odd.")
163 
164     if p * q != modulus:
165         raise ValueError("p*q must equal modulus.")
166 
167 
168 def _check_public_key_components(e, n):
169     if n < 3:
170         raise ValueError("n must be >= 3.")
171 
172     if e < 3 or e >= n:
173         raise ValueError("e must be >= 3 and < n.")
174 
175     if e & 1 == 0:
176         raise ValueError("e must be odd.")
177 
178 
179 def _modinv(e, m):
180     """
181     Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1
182     """
183     x1, y1, x2, y2 = 1, 0, 0, 1
184     a, b = e, m
185     while b > 0:
186         q, r = divmod(a, b)
187         xn, yn = x1 - q * x2, y1 - q * y2
188         a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
189     return x1 % m
190 
191 
192 def rsa_crt_iqmp(p, q):
193     """
194     Compute the CRT (q ** -1) % p value from RSA primes p and q.
195     """
196     return _modinv(q, p)
197 
198 
199 def rsa_crt_dmp1(private_exponent, p):
200     """
201     Compute the CRT private_exponent % (p - 1) value from the RSA
202     private_exponent (d) and p.
203     """
204     return private_exponent % (p - 1)
205 
206 
207 def rsa_crt_dmq1(private_exponent, q):
208     """
209     Compute the CRT private_exponent % (q - 1) value from the RSA
210     private_exponent (d) and q.
211     """
212     return private_exponent % (q - 1)
213 
214 
215 # Controls the number of iterations rsa_recover_prime_factors will perform
216 # to obtain the prime factors. Each iteration increments by 2 so the actual
217 # maximum attempts is half this number.
218 _MAX_RECOVERY_ATTEMPTS = 1000
219 
220 
221 def rsa_recover_prime_factors(n, e, d):
222     """
223     Compute factors p and q from the private exponent d. We assume that n has
224     no more than two factors. This function is adapted from code in PyCrypto.
225     """
226     # See 8.2.2(i) in Handbook of Applied Cryptography.
227     ktot = d * e - 1
228     # The quantity d*e-1 is a multiple of phi(n), even,
229     # and can be represented as t*2^s.
230     t = ktot
231     while t % 2 == 0:
232         t = t // 2
233     # Cycle through all multiplicative inverses in Zn.
234     # The algorithm is non-deterministic, but there is a 50% chance
235     # any candidate a leads to successful factoring.
236     # See "Digitalized Signatures and Public Key Functions as Intractable
237     # as Factorization", M. Rabin, 1979
238     spotted = False
239     a = 2
240     while not spotted and a < _MAX_RECOVERY_ATTEMPTS:
241         k = t
242         # Cycle through all values a^{t*2^i}=a^k
243         while k < ktot:
244             cand = pow(a, k, n)
245             # Check if a^k is a non-trivial root of unity (mod n)
246             if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
247                 # We have found a number such that (cand-1)(cand+1)=0 (mod n).
248                 # Either of the terms divides n.
249                 p = gcd(cand + 1, n)
250                 spotted = True
251                 break
252             k *= 2
253         # This value was not any good... let's try another!
254         a += 2
255     if not spotted:
256         raise ValueError("Unable to compute factors p and q from exponent d.")
257     # Found !
258     q, r = divmod(n, p)
259     assert r == 0
260 
261     return (p, q)
262 
263 
264 class RSAPrivateNumbers(object):
265     def __init__(self, p, q, d, dmp1, dmq1, iqmp,
266                  public_numbers):
267         if (
268             not isinstance(p, six.integer_types) or
269             not isinstance(q, six.integer_types) or
270             not isinstance(d, six.integer_types) or
271             not isinstance(dmp1, six.integer_types) or
272             not isinstance(dmq1, six.integer_types) or
273             not isinstance(iqmp, six.integer_types)
274         ):
275             raise TypeError(
276                 "RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must"
277                 " all be an integers."
278             )
279 
280         if not isinstance(public_numbers, RSAPublicNumbers):
281             raise TypeError(
282                 "RSAPrivateNumbers public_numbers must be an RSAPublicNumbers"
283                 " instance."
284             )
285 
286         self._p = p
287         self._q = q
288         self._d = d
289         self._dmp1 = dmp1
290         self._dmq1 = dmq1
291         self._iqmp = iqmp
292         self._public_numbers = public_numbers
293 
294     p = utils.read_only_property("_p")
295     q = utils.read_only_property("_q")
296     d = utils.read_only_property("_d")
297     dmp1 = utils.read_only_property("_dmp1")
298     dmq1 = utils.read_only_property("_dmq1")
299     iqmp = utils.read_only_property("_iqmp")
300     public_numbers = utils.read_only_property("_public_numbers")
301 
302     def private_key(self, backend):
303         return backend.load_rsa_private_numbers(self)
304 
305     def __eq__(self, other):
306         if not isinstance(other, RSAPrivateNumbers):
307             return NotImplemented
308 
309         return (
310             self.p == other.p and
311             self.q == other.q and
312             self.d == other.d and
313             self.dmp1 == other.dmp1 and
314             self.dmq1 == other.dmq1 and
315             self.iqmp == other.iqmp and
316             self.public_numbers == other.public_numbers
317         )
318 
319     def __ne__(self, other):
320         return not self == other
321 
322     def __hash__(self):
323         return hash((
324             self.p,
325             self.q,
326             self.d,
327             self.dmp1,
328             self.dmq1,
329             self.iqmp,
330             self.public_numbers,
331         ))
332 
333 
334 class RSAPublicNumbers(object):
335     def __init__(self, e, n):
336         if (
337             not isinstance(e, six.integer_types) or
338             not isinstance(n, six.integer_types)
339         ):
340             raise TypeError("RSAPublicNumbers arguments must be integers.")
341 
342         self._e = e
343         self._n = n
344 
345     e = utils.read_only_property("_e")
346     n = utils.read_only_property("_n")
347 
348     def public_key(self, backend):
349         return backend.load_rsa_public_numbers(self)
350 
351     def __repr__(self):
352         return "<RSAPublicNumbers(e={0.e}, n={0.n})>".format(self)
353 
354     def __eq__(self, other):
355         if not isinstance(other, RSAPublicNumbers):
356             return NotImplemented
357 
358         return self.e == other.e and self.n == other.n
359 
360     def __ne__(self, other):
361         return not self == other
362 
363     def __hash__(self):
364         return hash((self.e, self.n))
365
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py
--- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py
+++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py
@@ -257,7 +257,7 @@
     # Found !
     q, r = divmod(n, p)
     assert r == 0
-
+    p, q = sorted((p, q), reverse=True)
     return (p, q)

{"golden_diff": "diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n--- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n+++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n@@ -257,7 +257,7 @@\n     # Found !\n     q, r = divmod(n, p)\n     assert r == 0\n-\n+    p, q = sorted((p, q), reverse=True)\n     return (p, q)\n", "issue": "rsa.rsa_recover_prime_factors() should return p > q\nThe documentation for `rsa_recover_prime_factors()` warns that it returns `p` and `q` such that `p < q`. However, things like OpenSSL and BoringSSL seem to require that `p > q`. Given this, would it be feasible to change the order around in cryptography so that it lines up with OpenSSL?\n\nSee also: http://crypto.stackexchange.com/questions/18084/in-rsa-why-does-p-have-to-be-bigger-than-q-where-n-p-times-q. @briansmith can provide more commentary if needed.\n\n", "before_files": [{"content": "# This file is dual licensed under the terms of the Apache License, Version\n# 2.0, and the BSD License. See the LICENSE file in the root of this repository\n# for complete details.\n\nfrom __future__ import absolute_import, division, print_function\n\nimport abc\nfrom fractions import gcd\n\nimport six\n\nfrom cryptography import utils\nfrom cryptography.exceptions import UnsupportedAlgorithm, _Reasons\nfrom cryptography.hazmat.backends.interfaces import RSABackend\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPrivateKey(object):\n    @abc.abstractmethod\n    def signer(self, padding, algorithm):\n        \"\"\"\n        Returns an AsymmetricSignatureContext used for signing data.\n        \"\"\"\n\n    @abc.abstractmethod\n    def decrypt(self, ciphertext, padding):\n        \"\"\"\n        Decrypts the provided ciphertext.\n        \"\"\"\n\n    @abc.abstractproperty\n    def key_size(self):\n        \"\"\"\n        The bit length of the public modulus.\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_key(self):\n        \"\"\"\n        The RSAPublicKey associated with this private key.\n        \"\"\"\n\n    @abc.abstractmethod\n    def sign(self, data, padding, algorithm):\n        \"\"\"\n        Signs the data.\n        \"\"\"\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPrivateKeyWithSerialization(RSAPrivateKey):\n    @abc.abstractmethod\n    def private_numbers(self):\n        \"\"\"\n        Returns an RSAPrivateNumbers.\n        \"\"\"\n\n    @abc.abstractmethod\n    def private_bytes(self, encoding, format, encryption_algorithm):\n        \"\"\"\n        Returns the key serialized as bytes.\n        \"\"\"\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPublicKey(object):\n    @abc.abstractmethod\n    def verifier(self, signature, padding, algorithm):\n        \"\"\"\n        Returns an AsymmetricVerificationContext used for verifying signatures.\n        \"\"\"\n\n    @abc.abstractmethod\n    def encrypt(self, plaintext, padding):\n        \"\"\"\n        Encrypts the given plaintext.\n        \"\"\"\n\n    @abc.abstractproperty\n    def key_size(self):\n        \"\"\"\n        The bit length of the public modulus.\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_numbers(self):\n        \"\"\"\n        Returns an RSAPublicNumbers\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_bytes(self, encoding, format):\n        \"\"\"\n        Returns the key serialized as bytes.\n        \"\"\"\n\n    @abc.abstractmethod\n    def verify(self, signature, data, padding, algorithm):\n        \"\"\"\n        Verifies the signature of the data.\n        \"\"\"\n\n\nRSAPublicKeyWithSerialization = RSAPublicKey\n\n\ndef generate_private_key(public_exponent, key_size, backend):\n    if not isinstance(backend, RSABackend):\n        raise UnsupportedAlgorithm(\n            \"Backend object does not implement RSABackend.\",\n            _Reasons.BACKEND_MISSING_INTERFACE\n        )\n\n    _verify_rsa_parameters(public_exponent, key_size)\n    return backend.generate_rsa_private_key(public_exponent, key_size)\n\n\ndef _verify_rsa_parameters(public_exponent, key_size):\n    if public_exponent < 3:\n        raise ValueError(\"public_exponent must be >= 3.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if key_size < 512:\n        raise ValueError(\"key_size must be at least 512-bits.\")\n\n\ndef _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,\n                                  public_exponent, modulus):\n    if modulus < 3:\n        raise ValueError(\"modulus must be >= 3.\")\n\n    if p >= modulus:\n        raise ValueError(\"p must be < modulus.\")\n\n    if q >= modulus:\n        raise ValueError(\"q must be < modulus.\")\n\n    if dmp1 >= modulus:\n        raise ValueError(\"dmp1 must be < modulus.\")\n\n    if dmq1 >= modulus:\n        raise ValueError(\"dmq1 must be < modulus.\")\n\n    if iqmp >= modulus:\n        raise ValueError(\"iqmp must be < modulus.\")\n\n    if private_exponent >= modulus:\n        raise ValueError(\"private_exponent must be < modulus.\")\n\n    if public_exponent < 3 or public_exponent >= modulus:\n        raise ValueError(\"public_exponent must be >= 3 and < modulus.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if dmp1 & 1 == 0:\n        raise ValueError(\"dmp1 must be odd.\")\n\n    if dmq1 & 1 == 0:\n        raise ValueError(\"dmq1 must be odd.\")\n\n    if p * q != modulus:\n        raise ValueError(\"p*q must equal modulus.\")\n\n\ndef _check_public_key_components(e, n):\n    if n < 3:\n        raise ValueError(\"n must be >= 3.\")\n\n    if e < 3 or e >= n:\n        raise ValueError(\"e must be >= 3 and < n.\")\n\n    if e & 1 == 0:\n        raise ValueError(\"e must be odd.\")\n\n\ndef _modinv(e, m):\n    \"\"\"\n    Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1\n    \"\"\"\n    x1, y1, x2, y2 = 1, 0, 0, 1\n    a, b = e, m\n    while b > 0:\n        q, r = divmod(a, b)\n        xn, yn = x1 - q * x2, y1 - q * y2\n        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn\n    return x1 % m\n\n\ndef rsa_crt_iqmp(p, q):\n    \"\"\"\n    Compute the CRT (q ** -1) % p value from RSA primes p and q.\n    \"\"\"\n    return _modinv(q, p)\n\n\ndef rsa_crt_dmp1(private_exponent, p):\n    \"\"\"\n    Compute the CRT private_exponent % (p - 1) value from the RSA\n    private_exponent (d) and p.\n    \"\"\"\n    return private_exponent % (p - 1)\n\n\ndef rsa_crt_dmq1(private_exponent, q):\n    \"\"\"\n    Compute the CRT private_exponent % (q - 1) value from the RSA\n    private_exponent (d) and q.\n    \"\"\"\n    return private_exponent % (q - 1)\n\n\n# Controls the number of iterations rsa_recover_prime_factors will perform\n# to obtain the prime factors. Each iteration increments by 2 so the actual\n# maximum attempts is half this number.\n_MAX_RECOVERY_ATTEMPTS = 1000\n\n\ndef rsa_recover_prime_factors(n, e, d):\n    \"\"\"\n    Compute factors p and q from the private exponent d. We assume that n has\n    no more than two factors. This function is adapted from code in PyCrypto.\n    \"\"\"\n    # See 8.2.2(i) in Handbook of Applied Cryptography.\n    ktot = d * e - 1\n    # The quantity d*e-1 is a multiple of phi(n), even,\n    # and can be represented as t*2^s.\n    t = ktot\n    while t % 2 == 0:\n        t = t // 2\n    # Cycle through all multiplicative inverses in Zn.\n    # The algorithm is non-deterministic, but there is a 50% chance\n    # any candidate a leads to successful factoring.\n    # See \"Digitalized Signatures and Public Key Functions as Intractable\n    # as Factorization\", M. Rabin, 1979\n    spotted = False\n    a = 2\n    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:\n        k = t\n        # Cycle through all values a^{t*2^i}=a^k\n        while k < ktot:\n            cand = pow(a, k, n)\n            # Check if a^k is a non-trivial root of unity (mod n)\n            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:\n                # We have found a number such that (cand-1)(cand+1)=0 (mod n).\n                # Either of the terms divides n.\n                p = gcd(cand + 1, n)\n                spotted = True\n                break\n            k *= 2\n        # This value was not any good... let's try another!\n        a += 2\n    if not spotted:\n        raise ValueError(\"Unable to compute factors p and q from exponent d.\")\n    # Found !\n    q, r = divmod(n, p)\n    assert r == 0\n\n    return (p, q)\n\n\nclass RSAPrivateNumbers(object):\n    def __init__(self, p, q, d, dmp1, dmq1, iqmp,\n                 public_numbers):\n        if (\n            not isinstance(p, six.integer_types) or\n            not isinstance(q, six.integer_types) or\n            not isinstance(d, six.integer_types) or\n            not isinstance(dmp1, six.integer_types) or\n            not isinstance(dmq1, six.integer_types) or\n            not isinstance(iqmp, six.integer_types)\n        ):\n            raise TypeError(\n                \"RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must\"\n                \" all be an integers.\"\n            )\n\n        if not isinstance(public_numbers, RSAPublicNumbers):\n            raise TypeError(\n                \"RSAPrivateNumbers public_numbers must be an RSAPublicNumbers\"\n                \" instance.\"\n            )\n\n        self._p = p\n        self._q = q\n        self._d = d\n        self._dmp1 = dmp1\n        self._dmq1 = dmq1\n        self._iqmp = iqmp\n        self._public_numbers = public_numbers\n\n    p = utils.read_only_property(\"_p\")\n    q = utils.read_only_property(\"_q\")\n    d = utils.read_only_property(\"_d\")\n    dmp1 = utils.read_only_property(\"_dmp1\")\n    dmq1 = utils.read_only_property(\"_dmq1\")\n    iqmp = utils.read_only_property(\"_iqmp\")\n    public_numbers = utils.read_only_property(\"_public_numbers\")\n\n    def private_key(self, backend):\n        return backend.load_rsa_private_numbers(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPrivateNumbers):\n            return NotImplemented\n\n        return (\n            self.p == other.p and\n            self.q == other.q and\n            self.d == other.d and\n            self.dmp1 == other.dmp1 and\n            self.dmq1 == other.dmq1 and\n            self.iqmp == other.iqmp and\n            self.public_numbers == other.public_numbers\n        )\n\n    def __ne__(self, other):\n        return not self == other\n\n    def __hash__(self):\n        return hash((\n            self.p,\n            self.q,\n            self.d,\n            self.dmp1,\n            self.dmq1,\n            self.iqmp,\n            self.public_numbers,\n        ))\n\n\nclass RSAPublicNumbers(object):\n    def __init__(self, e, n):\n        if (\n            not isinstance(e, six.integer_types) or\n            not isinstance(n, six.integer_types)\n        ):\n            raise TypeError(\"RSAPublicNumbers arguments must be integers.\")\n\n        self._e = e\n        self._n = n\n\n    e = utils.read_only_property(\"_e\")\n    n = utils.read_only_property(\"_n\")\n\n    def public_key(self, backend):\n        return backend.load_rsa_public_numbers(self)\n\n    def __repr__(self):\n        return \"<RSAPublicNumbers(e={0.e}, n={0.n})>\".format(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPublicNumbers):\n            return NotImplemented\n\n        return self.e == other.e and self.n == other.n\n\n    def __ne__(self, other):\n        return not self == other\n\n    def __hash__(self):\n        return hash((self.e, self.n))\n", "path": "src/cryptography/hazmat/primitives/asymmetric/rsa.py"}], "after_files": [{"content": "# This file is dual licensed under the terms of the Apache License, Version\n# 2.0, and the BSD License. See the LICENSE file in the root of this repository\n# for complete details.\n\nfrom __future__ import absolute_import, division, print_function\n\nimport abc\nfrom fractions import gcd\n\nimport six\n\nfrom cryptography import utils\nfrom cryptography.exceptions import UnsupportedAlgorithm, _Reasons\nfrom cryptography.hazmat.backends.interfaces import RSABackend\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPrivateKey(object):\n    @abc.abstractmethod\n    def signer(self, padding, algorithm):\n        \"\"\"\n        Returns an AsymmetricSignatureContext used for signing data.\n        \"\"\"\n\n    @abc.abstractmethod\n    def decrypt(self, ciphertext, padding):\n        \"\"\"\n        Decrypts the provided ciphertext.\n        \"\"\"\n\n    @abc.abstractproperty\n    def key_size(self):\n        \"\"\"\n        The bit length of the public modulus.\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_key(self):\n        \"\"\"\n        The RSAPublicKey associated with this private key.\n        \"\"\"\n\n    @abc.abstractmethod\n    def sign(self, data, padding, algorithm):\n        \"\"\"\n        Signs the data.\n        \"\"\"\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPrivateKeyWithSerialization(RSAPrivateKey):\n    @abc.abstractmethod\n    def private_numbers(self):\n        \"\"\"\n        Returns an RSAPrivateNumbers.\n        \"\"\"\n\n    @abc.abstractmethod\n    def private_bytes(self, encoding, format, encryption_algorithm):\n        \"\"\"\n        Returns the key serialized as bytes.\n        \"\"\"\n\n\n@six.add_metaclass(abc.ABCMeta)\nclass RSAPublicKey(object):\n    @abc.abstractmethod\n    def verifier(self, signature, padding, algorithm):\n        \"\"\"\n        Returns an AsymmetricVerificationContext used for verifying signatures.\n        \"\"\"\n\n    @abc.abstractmethod\n    def encrypt(self, plaintext, padding):\n        \"\"\"\n        Encrypts the given plaintext.\n        \"\"\"\n\n    @abc.abstractproperty\n    def key_size(self):\n        \"\"\"\n        The bit length of the public modulus.\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_numbers(self):\n        \"\"\"\n        Returns an RSAPublicNumbers\n        \"\"\"\n\n    @abc.abstractmethod\n    def public_bytes(self, encoding, format):\n        \"\"\"\n        Returns the key serialized as bytes.\n        \"\"\"\n\n    @abc.abstractmethod\n    def verify(self, signature, data, padding, algorithm):\n        \"\"\"\n        Verifies the signature of the data.\n        \"\"\"\n\n\nRSAPublicKeyWithSerialization = RSAPublicKey\n\n\ndef generate_private_key(public_exponent, key_size, backend):\n    if not isinstance(backend, RSABackend):\n        raise UnsupportedAlgorithm(\n            \"Backend object does not implement RSABackend.\",\n            _Reasons.BACKEND_MISSING_INTERFACE\n        )\n\n    _verify_rsa_parameters(public_exponent, key_size)\n    return backend.generate_rsa_private_key(public_exponent, key_size)\n\n\ndef _verify_rsa_parameters(public_exponent, key_size):\n    if public_exponent < 3:\n        raise ValueError(\"public_exponent must be >= 3.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if key_size < 512:\n        raise ValueError(\"key_size must be at least 512-bits.\")\n\n\ndef _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,\n                                  public_exponent, modulus):\n    if modulus < 3:\n        raise ValueError(\"modulus must be >= 3.\")\n\n    if p >= modulus:\n        raise ValueError(\"p must be < modulus.\")\n\n    if q >= modulus:\n        raise ValueError(\"q must be < modulus.\")\n\n    if dmp1 >= modulus:\n        raise ValueError(\"dmp1 must be < modulus.\")\n\n    if dmq1 >= modulus:\n        raise ValueError(\"dmq1 must be < modulus.\")\n\n    if iqmp >= modulus:\n        raise ValueError(\"iqmp must be < modulus.\")\n\n    if private_exponent >= modulus:\n        raise ValueError(\"private_exponent must be < modulus.\")\n\n    if public_exponent < 3 or public_exponent >= modulus:\n        raise ValueError(\"public_exponent must be >= 3 and < modulus.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if dmp1 & 1 == 0:\n        raise ValueError(\"dmp1 must be odd.\")\n\n    if dmq1 & 1 == 0:\n        raise ValueError(\"dmq1 must be odd.\")\n\n    if p * q != modulus:\n        raise ValueError(\"p*q must equal modulus.\")\n\n\ndef _check_public_key_components(e, n):\n    if n < 3:\n        raise ValueError(\"n must be >= 3.\")\n\n    if e < 3 or e >= n:\n        raise ValueError(\"e must be >= 3 and < n.\")\n\n    if e & 1 == 0:\n        raise ValueError(\"e must be odd.\")\n\n\ndef _modinv(e, m):\n    \"\"\"\n    Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1\n    \"\"\"\n    x1, y1, x2, y2 = 1, 0, 0, 1\n    a, b = e, m\n    while b > 0:\n        q, r = divmod(a, b)\n        xn, yn = x1 - q * x2, y1 - q * y2\n        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn\n    return x1 % m\n\n\ndef rsa_crt_iqmp(p, q):\n    \"\"\"\n    Compute the CRT (q ** -1) % p value from RSA primes p and q.\n    \"\"\"\n    return _modinv(q, p)\n\n\ndef rsa_crt_dmp1(private_exponent, p):\n    \"\"\"\n    Compute the CRT private_exponent % (p - 1) value from the RSA\n    private_exponent (d) and p.\n    \"\"\"\n    return private_exponent % (p - 1)\n\n\ndef rsa_crt_dmq1(private_exponent, q):\n    \"\"\"\n    Compute the CRT private_exponent % (q - 1) value from the RSA\n    private_exponent (d) and q.\n    \"\"\"\n    return private_exponent % (q - 1)\n\n\n# Controls the number of iterations rsa_recover_prime_factors will perform\n# to obtain the prime factors. Each iteration increments by 2 so the actual\n# maximum attempts is half this number.\n_MAX_RECOVERY_ATTEMPTS = 1000\n\n\ndef rsa_recover_prime_factors(n, e, d):\n    \"\"\"\n    Compute factors p and q from the private exponent d. We assume that n has\n    no more than two factors. This function is adapted from code in PyCrypto.\n    \"\"\"\n    # See 8.2.2(i) in Handbook of Applied Cryptography.\n    ktot = d * e - 1\n    # The quantity d*e-1 is a multiple of phi(n), even,\n    # and can be represented as t*2^s.\n    t = ktot\n    while t % 2 == 0:\n        t = t // 2\n    # Cycle through all multiplicative inverses in Zn.\n    # The algorithm is non-deterministic, but there is a 50% chance\n    # any candidate a leads to successful factoring.\n    # See \"Digitalized Signatures and Public Key Functions as Intractable\n    # as Factorization\", M. Rabin, 1979\n    spotted = False\n    a = 2\n    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:\n        k = t\n        # Cycle through all values a^{t*2^i}=a^k\n        while k < ktot:\n            cand = pow(a, k, n)\n            # Check if a^k is a non-trivial root of unity (mod n)\n            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:\n                # We have found a number such that (cand-1)(cand+1)=0 (mod n).\n                # Either of the terms divides n.\n                p = gcd(cand + 1, n)\n                spotted = True\n                break\n            k *= 2\n        # This value was not any good... let's try another!\n        a += 2\n    if not spotted:\n        raise ValueError(\"Unable to compute factors p and q from exponent d.\")\n    # Found !\n    q, r = divmod(n, p)\n    assert r == 0\n    p, q = sorted((p, q), reverse=True)\n    return (p, q)\n\n\nclass RSAPrivateNumbers(object):\n    def __init__(self, p, q, d, dmp1, dmq1, iqmp,\n                 public_numbers):\n        if (\n            not isinstance(p, six.integer_types) or\n            not isinstance(q, six.integer_types) or\n            not isinstance(d, six.integer_types) or\n            not isinstance(dmp1, six.integer_types) or\n            not isinstance(dmq1, six.integer_types) or\n            not isinstance(iqmp, six.integer_types)\n        ):\n            raise TypeError(\n                \"RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must\"\n                \" all be an integers.\"\n            )\n\n        if not isinstance(public_numbers, RSAPublicNumbers):\n            raise TypeError(\n                \"RSAPrivateNumbers public_numbers must be an RSAPublicNumbers\"\n                \" instance.\"\n            )\n\n        self._p = p\n        self._q = q\n        self._d = d\n        self._dmp1 = dmp1\n        self._dmq1 = dmq1\n        self._iqmp = iqmp\n        self._public_numbers = public_numbers\n\n    p = utils.read_only_property(\"_p\")\n    q = utils.read_only_property(\"_q\")\n    d = utils.read_only_property(\"_d\")\n    dmp1 = utils.read_only_property(\"_dmp1\")\n    dmq1 = utils.read_only_property(\"_dmq1\")\n    iqmp = utils.read_only_property(\"_iqmp\")\n    public_numbers = utils.read_only_property(\"_public_numbers\")\n\n    def private_key(self, backend):\n        return backend.load_rsa_private_numbers(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPrivateNumbers):\n            return NotImplemented\n\n        return (\n            self.p == other.p and\n            self.q == other.q and\n            self.d == other.d and\n            self.dmp1 == other.dmp1 and\n            self.dmq1 == other.dmq1 and\n            self.iqmp == other.iqmp and\n            self.public_numbers == other.public_numbers\n        )\n\n    def __ne__(self, other):\n        return not self == other\n\n    def __hash__(self):\n        return hash((\n            self.p,\n            self.q,\n            self.d,\n            self.dmp1,\n            self.dmq1,\n            self.iqmp,\n            self.public_numbers,\n        ))\n\n\nclass RSAPublicNumbers(object):\n    def __init__(self, e, n):\n        if (\n            not isinstance(e, six.integer_types) or\n            not isinstance(n, six.integer_types)\n        ):\n            raise TypeError(\"RSAPublicNumbers arguments must be integers.\")\n\n        self._e = e\n        self._n = n\n\n    e = utils.read_only_property(\"_e\")\n    n = utils.read_only_property(\"_n\")\n\n    def public_key(self, backend):\n        return backend.load_rsa_public_numbers(self)\n\n    def __repr__(self):\n        return \"<RSAPublicNumbers(e={0.e}, n={0.n})>\".format(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPublicNumbers):\n            return NotImplemented\n\n        return self.e == other.e and self.n == other.n\n\n    def __ne__(self, other):\n        return not self == other\n\n    def __hash__(self):\n        return hash((self.e, self.n))\n", "path": "src/cryptography/hazmat/primitives/asymmetric/rsa.py"}]}