rsa.py 7.5 KB

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