Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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.
5from __future__ import annotations
7import abc
8import typing
9from math import gcd
11from cryptography.hazmat.bindings._rust import openssl as rust_openssl
12from cryptography.hazmat.primitives import _serialization, hashes
13from cryptography.hazmat.primitives._asymmetric import AsymmetricPadding
14from cryptography.hazmat.primitives.asymmetric import utils as asym_utils
17class RSAPrivateKey(metaclass=abc.ABCMeta):
18 @abc.abstractmethod
19 def decrypt(self, ciphertext: bytes, padding: AsymmetricPadding) -> bytes:
20 """
21 Decrypts the provided ciphertext.
22 """
24 @property
25 @abc.abstractmethod
26 def key_size(self) -> int:
27 """
28 The bit length of the public modulus.
29 """
31 @abc.abstractmethod
32 def public_key(self) -> RSAPublicKey:
33 """
34 The RSAPublicKey associated with this private key.
35 """
37 @abc.abstractmethod
38 def sign(
39 self,
40 data: bytes,
41 padding: AsymmetricPadding,
42 algorithm: asym_utils.Prehashed | hashes.HashAlgorithm,
43 ) -> bytes:
44 """
45 Signs the data.
46 """
48 @abc.abstractmethod
49 def private_numbers(self) -> RSAPrivateNumbers:
50 """
51 Returns an RSAPrivateNumbers.
52 """
54 @abc.abstractmethod
55 def private_bytes(
56 self,
57 encoding: _serialization.Encoding,
58 format: _serialization.PrivateFormat,
59 encryption_algorithm: _serialization.KeySerializationEncryption,
60 ) -> bytes:
61 """
62 Returns the key serialized as bytes.
63 """
66RSAPrivateKeyWithSerialization = RSAPrivateKey
67RSAPrivateKey.register(rust_openssl.rsa.RSAPrivateKey)
70class RSAPublicKey(metaclass=abc.ABCMeta):
71 @abc.abstractmethod
72 def encrypt(self, plaintext: bytes, padding: AsymmetricPadding) -> bytes:
73 """
74 Encrypts the given plaintext.
75 """
77 @property
78 @abc.abstractmethod
79 def key_size(self) -> int:
80 """
81 The bit length of the public modulus.
82 """
84 @abc.abstractmethod
85 def public_numbers(self) -> RSAPublicNumbers:
86 """
87 Returns an RSAPublicNumbers
88 """
90 @abc.abstractmethod
91 def public_bytes(
92 self,
93 encoding: _serialization.Encoding,
94 format: _serialization.PublicFormat,
95 ) -> bytes:
96 """
97 Returns the key serialized as bytes.
98 """
100 @abc.abstractmethod
101 def verify(
102 self,
103 signature: bytes,
104 data: bytes,
105 padding: AsymmetricPadding,
106 algorithm: asym_utils.Prehashed | hashes.HashAlgorithm,
107 ) -> None:
108 """
109 Verifies the signature of the data.
110 """
112 @abc.abstractmethod
113 def recover_data_from_signature(
114 self,
115 signature: bytes,
116 padding: AsymmetricPadding,
117 algorithm: hashes.HashAlgorithm | None,
118 ) -> bytes:
119 """
120 Recovers the original data from the signature.
121 """
123 @abc.abstractmethod
124 def __eq__(self, other: object) -> bool:
125 """
126 Checks equality.
127 """
130RSAPublicKeyWithSerialization = RSAPublicKey
131RSAPublicKey.register(rust_openssl.rsa.RSAPublicKey)
133RSAPrivateNumbers = rust_openssl.rsa.RSAPrivateNumbers
134RSAPublicNumbers = rust_openssl.rsa.RSAPublicNumbers
137def generate_private_key(
138 public_exponent: int,
139 key_size: int,
140 backend: typing.Any = None,
141) -> RSAPrivateKey:
142 _verify_rsa_parameters(public_exponent, key_size)
143 return rust_openssl.rsa.generate_private_key(public_exponent, key_size)
146def _verify_rsa_parameters(public_exponent: int, key_size: int) -> None:
147 if public_exponent not in (3, 65537):
148 raise ValueError(
149 "public_exponent must be either 3 (for legacy compatibility) or "
150 "65537. Almost everyone should choose 65537 here!"
151 )
153 if key_size < 1024:
154 raise ValueError("key_size must be at least 1024-bits.")
157def _modinv(e: int, m: int) -> int:
158 """
159 Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1
160 """
161 x1, x2 = 1, 0
162 a, b = e, m
163 while b > 0:
164 q, r = divmod(a, b)
165 xn = x1 - q * x2
166 a, b, x1, x2 = b, r, x2, xn
167 return x1 % m
170def rsa_crt_iqmp(p: int, q: int) -> int:
171 """
172 Compute the CRT (q ** -1) % p value from RSA primes p and q.
173 """
174 return _modinv(q, p)
177def rsa_crt_dmp1(private_exponent: int, p: int) -> int:
178 """
179 Compute the CRT private_exponent % (p - 1) value from the RSA
180 private_exponent (d) and p.
181 """
182 return private_exponent % (p - 1)
185def rsa_crt_dmq1(private_exponent: int, q: int) -> int:
186 """
187 Compute the CRT private_exponent % (q - 1) value from the RSA
188 private_exponent (d) and q.
189 """
190 return private_exponent % (q - 1)
193def rsa_recover_private_exponent(e: int, p: int, q: int) -> int:
194 """
195 Compute the RSA private_exponent (d) given the public exponent (e)
196 and the RSA primes p and q.
198 This uses the Carmichael totient function to generate the
199 smallest possible working value of the private exponent.
200 """
201 # This lambda_n is the Carmichael totient function.
202 # The original RSA paper uses the Euler totient function
203 # here: phi_n = (p - 1) * (q - 1)
204 # Either version of the private exponent will work, but the
205 # one generated by the older formulation may be larger
206 # than necessary. (lambda_n always divides phi_n)
207 #
208 # TODO: Replace with lcm(p - 1, q - 1) once the minimum
209 # supported Python version is >= 3.9.
210 lambda_n = (p - 1) * (q - 1) // gcd(p - 1, q - 1)
211 return _modinv(e, lambda_n)
214# Controls the number of iterations rsa_recover_prime_factors will perform
215# to obtain the prime factors. Each iteration increments by 2 so the actual
216# maximum attempts is half this number.
217_MAX_RECOVERY_ATTEMPTS = 1000
220def rsa_recover_prime_factors(n: int, e: int, d: int) -> tuple[int, int]:
221 """
222 Compute factors p and q from the private exponent d. We assume that n has
223 no more than two factors. This function is adapted from code in PyCrypto.
224 """
225 # See 8.2.2(i) in Handbook of Applied Cryptography.
226 ktot = d * e - 1
227 # The quantity d*e-1 is a multiple of phi(n), even,
228 # and can be represented as t*2^s.
229 t = ktot
230 while t % 2 == 0:
231 t = t // 2
232 # Cycle through all multiplicative inverses in Zn.
233 # The algorithm is non-deterministic, but there is a 50% chance
234 # any candidate a leads to successful factoring.
235 # See "Digitalized Signatures and Public Key Functions as Intractable
236 # as Factorization", M. Rabin, 1979
237 spotted = False
238 a = 2
239 while not spotted and a < _MAX_RECOVERY_ATTEMPTS:
240 k = t
241 # Cycle through all values a^{t*2^i}=a^k
242 while k < ktot:
243 cand = pow(a, k, n)
244 # Check if a^k is a non-trivial root of unity (mod n)
245 if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
246 # We have found a number such that (cand-1)(cand+1)=0 (mod n).
247 # Either of the terms divides n.
248 p = gcd(cand + 1, n)
249 spotted = True
250 break
251 k *= 2
252 # This value was not any good... let's try another!
253 a += 2
254 if not spotted:
255 raise ValueError("Unable to compute factors p and q from exponent d.")
256 # Found !
257 q, r = divmod(n, p)
258 assert r == 0
259 p, q = sorted((p, q), reverse=True)
260 return (p, q)