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