RSA.py 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864
  1. # -*- coding: utf-8 -*-
  2. # ===================================================================
  3. #
  4. # Copyright (c) 2016, Legrandin <helderijs@gmail.com>
  5. # All rights reserved.
  6. #
  7. # Redistribution and use in source and binary forms, with or without
  8. # modification, are permitted provided that the following conditions
  9. # are met:
  10. #
  11. # 1. Redistributions of source code must retain the above copyright
  12. # notice, this list of conditions and the following disclaimer.
  13. # 2. Redistributions in binary form must reproduce the above copyright
  14. # notice, this list of conditions and the following disclaimer in
  15. # the documentation and/or other materials provided with the
  16. # distribution.
  17. #
  18. # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  21. # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  22. # COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  23. # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  24. # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  25. # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26. # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27. # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  28. # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29. # POSSIBILITY OF SUCH DAMAGE.
  30. # ===================================================================
  31. __all__ = ['generate', 'construct', 'import_key',
  32. 'RsaKey', 'oid']
  33. import binascii
  34. import struct
  35. from Crypto import Random
  36. from Crypto.Util.py3compat import tobytes, bord, tostr
  37. from Crypto.Util.asn1 import DerSequence, DerNull
  38. from Crypto.Util.number import bytes_to_long
  39. from Crypto.Math.Numbers import Integer
  40. from Crypto.Math.Primality import (test_probable_prime,
  41. generate_probable_prime, COMPOSITE)
  42. from Crypto.PublicKey import (_expand_subject_public_key_info,
  43. _create_subject_public_key_info,
  44. _extract_subject_public_key_info)
  45. class RsaKey(object):
  46. r"""Class defining an RSA key, private or public.
  47. Do not instantiate directly.
  48. Use :func:`generate`, :func:`construct` or :func:`import_key` instead.
  49. :ivar n: RSA modulus
  50. :vartype n: integer
  51. :ivar e: RSA public exponent
  52. :vartype e: integer
  53. :ivar d: RSA private exponent
  54. :vartype d: integer
  55. :ivar p: First factor of the RSA modulus
  56. :vartype p: integer
  57. :ivar q: Second factor of the RSA modulus
  58. :vartype q: integer
  59. :ivar invp: Chinese remainder component (:math:`p^{-1} \text{mod } q`)
  60. :vartype invp: integer
  61. :ivar invq: Chinese remainder component (:math:`q^{-1} \text{mod } p`)
  62. :vartype invq: integer
  63. :ivar u: Same as ``invp``
  64. :vartype u: integer
  65. """
  66. def __init__(self, **kwargs):
  67. """Build an RSA key.
  68. :Keywords:
  69. n : integer
  70. The modulus.
  71. e : integer
  72. The public exponent.
  73. d : integer
  74. The private exponent. Only required for private keys.
  75. p : integer
  76. The first factor of the modulus. Only required for private keys.
  77. q : integer
  78. The second factor of the modulus. Only required for private keys.
  79. u : integer
  80. The CRT coefficient (inverse of p modulo q). Only required for
  81. private keys.
  82. """
  83. input_set = set(kwargs.keys())
  84. public_set = set(('n', 'e'))
  85. private_set = public_set | set(('p', 'q', 'd', 'u'))
  86. if input_set not in (private_set, public_set):
  87. raise ValueError("Some RSA components are missing")
  88. for component, value in kwargs.items():
  89. setattr(self, "_" + component, value)
  90. if input_set == private_set:
  91. self._dp = self._d % (self._p - 1) # = (e⁻¹) mod (p-1)
  92. self._dq = self._d % (self._q - 1) # = (e⁻¹) mod (q-1)
  93. self._invq = None # will be computed on demand
  94. @property
  95. def n(self):
  96. return int(self._n)
  97. @property
  98. def e(self):
  99. return int(self._e)
  100. @property
  101. def d(self):
  102. if not self.has_private():
  103. raise AttributeError("No private exponent available for public keys")
  104. return int(self._d)
  105. @property
  106. def p(self):
  107. if not self.has_private():
  108. raise AttributeError("No CRT component 'p' available for public keys")
  109. return int(self._p)
  110. @property
  111. def q(self):
  112. if not self.has_private():
  113. raise AttributeError("No CRT component 'q' available for public keys")
  114. return int(self._q)
  115. @property
  116. def dp(self):
  117. if not self.has_private():
  118. raise AttributeError("No CRT component 'dp' available for public keys")
  119. return int(self._dp)
  120. @property
  121. def dq(self):
  122. if not self.has_private():
  123. raise AttributeError("No CRT component 'dq' available for public keys")
  124. return int(self._dq)
  125. @property
  126. def invq(self):
  127. if not self.has_private():
  128. raise AttributeError("No CRT component 'invq' available for public keys")
  129. if self._invq is None:
  130. self._invq = self._q.inverse(self._p)
  131. return int(self._invq)
  132. @property
  133. def invp(self):
  134. return self.u
  135. @property
  136. def u(self):
  137. if not self.has_private():
  138. raise AttributeError("No CRT component 'u' available for public keys")
  139. return int(self._u)
  140. def size_in_bits(self):
  141. """Size of the RSA modulus in bits"""
  142. return self._n.size_in_bits()
  143. def size_in_bytes(self):
  144. """The minimal amount of bytes that can hold the RSA modulus"""
  145. return (self._n.size_in_bits() - 1) // 8 + 1
  146. def _encrypt(self, plaintext):
  147. if not 0 <= plaintext < self._n:
  148. raise ValueError("Plaintext too large")
  149. return int(pow(Integer(plaintext), self._e, self._n))
  150. def _decrypt_to_bytes(self, ciphertext):
  151. if not 0 <= ciphertext < self._n:
  152. raise ValueError("Ciphertext too large")
  153. if not self.has_private():
  154. raise TypeError("This is not a private key")
  155. # Blinded RSA decryption (to prevent timing attacks):
  156. # Step 1: Generate random secret blinding factor r,
  157. # such that 0 < r < n-1
  158. r = Integer.random_range(min_inclusive=1, max_exclusive=self._n)
  159. # Step 2: Compute c' = c * r**e mod n
  160. cp = Integer(ciphertext) * pow(r, self._e, self._n) % self._n
  161. # Step 3: Compute m' = c'**d mod n (normal RSA decryption)
  162. m1 = pow(cp, self._dp, self._p)
  163. m2 = pow(cp, self._dq, self._q)
  164. h = ((m2 - m1) * self._u) % self._q
  165. mp = h * self._p + m1
  166. # Step 4: Compute m = m' * (r**(-1)) mod n
  167. # then encode into a big endian byte string
  168. result = Integer._mult_modulo_bytes(
  169. r.inverse(self._n),
  170. mp,
  171. self._n)
  172. return result
  173. def _decrypt(self, ciphertext):
  174. """Legacy private method"""
  175. return bytes_to_long(self._decrypt_to_bytes(ciphertext))
  176. def has_private(self):
  177. """Whether this is an RSA private key"""
  178. return hasattr(self, "_d")
  179. def can_encrypt(self): # legacy
  180. return True
  181. def can_sign(self): # legacy
  182. return True
  183. def public_key(self):
  184. """A matching RSA public key.
  185. Returns:
  186. a new :class:`RsaKey` object
  187. """
  188. return RsaKey(n=self._n, e=self._e)
  189. def __eq__(self, other):
  190. if self.has_private() != other.has_private():
  191. return False
  192. if self.n != other.n or self.e != other.e:
  193. return False
  194. if not self.has_private():
  195. return True
  196. return (self.d == other.d)
  197. def __ne__(self, other):
  198. return not (self == other)
  199. def __getstate__(self):
  200. # RSA key is not pickable
  201. from pickle import PicklingError
  202. raise PicklingError
  203. def __repr__(self):
  204. if self.has_private():
  205. extra = ", d=%d, p=%d, q=%d, u=%d" % (int(self._d), int(self._p),
  206. int(self._q), int(self._u))
  207. else:
  208. extra = ""
  209. return "RsaKey(n=%d, e=%d%s)" % (int(self._n), int(self._e), extra)
  210. def __str__(self):
  211. if self.has_private():
  212. key_type = "Private"
  213. else:
  214. key_type = "Public"
  215. return "%s RSA key at 0x%X" % (key_type, id(self))
  216. def export_key(self, format='PEM', passphrase=None, pkcs=1,
  217. protection=None, randfunc=None, prot_params=None):
  218. """Export this RSA key.
  219. Keyword Args:
  220. format (string):
  221. The desired output format:
  222. - ``'PEM'``. (default) Text output, according to `RFC1421`_/`RFC1423`_.
  223. - ``'DER'``. Binary output.
  224. - ``'OpenSSH'``. Text output, according to the OpenSSH specification.
  225. Only suitable for public keys (not private keys).
  226. Note that PEM contains a DER structure.
  227. passphrase (bytes or string):
  228. (*Private keys only*) The passphrase to protect the
  229. private key.
  230. pkcs (integer):
  231. (*Private keys only*) The standard to use for
  232. serializing the key: PKCS#1 or PKCS#8.
  233. With ``pkcs=1`` (*default*), the private key is encoded with a
  234. simple `PKCS#1`_ structure (``RSAPrivateKey``). The key cannot be
  235. securely encrypted.
  236. With ``pkcs=8``, the private key is encoded with a `PKCS#8`_ structure
  237. (``PrivateKeyInfo``). PKCS#8 offers the best ways to securely
  238. encrypt the key.
  239. .. note::
  240. This parameter is ignored for a public key.
  241. For DER and PEM, the output is always an
  242. ASN.1 DER ``SubjectPublicKeyInfo`` structure.
  243. protection (string):
  244. (*For private keys only*)
  245. The encryption scheme to use for protecting the private key
  246. using the passphrase.
  247. You can only specify a value if ``pkcs=8``.
  248. For all possible protection schemes,
  249. refer to :ref:`the encryption parameters of PKCS#8<enc_params>`.
  250. The recommended value is
  251. ``'PBKDF2WithHMAC-SHA512AndAES256-CBC'``.
  252. If ``None`` (default), the behavior depends on :attr:`format`:
  253. - if ``format='PEM'``, the obsolete PEM encryption scheme is used.
  254. It is based on MD5 for key derivation, and 3DES for encryption.
  255. - if ``format='DER'``, the ``'PBKDF2WithHMAC-SHA1AndDES-EDE3-CBC'``
  256. scheme is used.
  257. prot_params (dict):
  258. (*For private keys only*)
  259. The parameters to use to derive the encryption key
  260. from the passphrase. ``'protection'`` must be also specified.
  261. For all possible values,
  262. refer to :ref:`the encryption parameters of PKCS#8<enc_params>`.
  263. The recommendation is to use ``{'iteration_count':21000}`` for PBKDF2,
  264. and ``{'iteration_count':131072}`` for scrypt.
  265. randfunc (callable):
  266. A function that provides random bytes. Only used for PEM encoding.
  267. The default is :func:`Crypto.Random.get_random_bytes`.
  268. Returns:
  269. bytes: the encoded key
  270. Raises:
  271. ValueError:when the format is unknown or when you try to encrypt a private
  272. key with *DER* format and PKCS#1.
  273. .. warning::
  274. If you don't provide a pass phrase, the private key will be
  275. exported in the clear!
  276. .. _RFC1421: http://www.ietf.org/rfc/rfc1421.txt
  277. .. _RFC1423: http://www.ietf.org/rfc/rfc1423.txt
  278. .. _`PKCS#1`: http://www.ietf.org/rfc/rfc3447.txt
  279. .. _`PKCS#8`: http://www.ietf.org/rfc/rfc5208.txt
  280. """
  281. if passphrase is not None:
  282. passphrase = tobytes(passphrase)
  283. if randfunc is None:
  284. randfunc = Random.get_random_bytes
  285. if format == 'OpenSSH':
  286. e_bytes, n_bytes = [x.to_bytes() for x in (self._e, self._n)]
  287. if bord(e_bytes[0]) & 0x80:
  288. e_bytes = b'\x00' + e_bytes
  289. if bord(n_bytes[0]) & 0x80:
  290. n_bytes = b'\x00' + n_bytes
  291. keyparts = [b'ssh-rsa', e_bytes, n_bytes]
  292. keystring = b''.join([struct.pack(">I", len(kp)) + kp for kp in keyparts])
  293. return b'ssh-rsa ' + binascii.b2a_base64(keystring)[:-1]
  294. # DER format is always used, even in case of PEM, which simply
  295. # encodes it into BASE64.
  296. if self.has_private():
  297. binary_key = DerSequence([0,
  298. self.n,
  299. self.e,
  300. self.d,
  301. self.p,
  302. self.q,
  303. self.d % (self.p-1),
  304. self.d % (self.q-1),
  305. Integer(self.q).inverse(self.p)
  306. ]).encode()
  307. if pkcs == 1:
  308. key_type = 'RSA PRIVATE KEY'
  309. if format == 'DER' and passphrase:
  310. raise ValueError("PKCS#1 private key cannot be encrypted")
  311. else: # PKCS#8
  312. from Crypto.IO import PKCS8
  313. if format == 'PEM' and protection is None:
  314. key_type = 'PRIVATE KEY'
  315. binary_key = PKCS8.wrap(binary_key, oid, None,
  316. key_params=DerNull())
  317. else:
  318. key_type = 'ENCRYPTED PRIVATE KEY'
  319. if not protection:
  320. if prot_params:
  321. raise ValueError("'protection' parameter must be set")
  322. protection = 'PBKDF2WithHMAC-SHA1AndDES-EDE3-CBC'
  323. binary_key = PKCS8.wrap(binary_key, oid,
  324. passphrase, protection,
  325. prot_params=prot_params,
  326. key_params=DerNull())
  327. passphrase = None
  328. else:
  329. key_type = "PUBLIC KEY"
  330. binary_key = _create_subject_public_key_info(oid,
  331. DerSequence([self.n,
  332. self.e]),
  333. DerNull()
  334. )
  335. if format == 'DER':
  336. return binary_key
  337. if format == 'PEM':
  338. from Crypto.IO import PEM
  339. pem_str = PEM.encode(binary_key, key_type, passphrase, randfunc)
  340. return tobytes(pem_str)
  341. raise ValueError("Unknown key format '%s'. Cannot export the RSA key." % format)
  342. # Backward compatibility
  343. def exportKey(self, *args, **kwargs):
  344. """:meta private:"""
  345. return self.export_key(*args, **kwargs)
  346. def publickey(self):
  347. """:meta private:"""
  348. return self.public_key()
  349. # Methods defined in PyCrypto that we don't support anymore
  350. def sign(self, M, K):
  351. """:meta private:"""
  352. raise NotImplementedError("Use module Crypto.Signature.pkcs1_15 instead")
  353. def verify(self, M, signature):
  354. """:meta private:"""
  355. raise NotImplementedError("Use module Crypto.Signature.pkcs1_15 instead")
  356. def encrypt(self, plaintext, K):
  357. """:meta private:"""
  358. raise NotImplementedError("Use module Crypto.Cipher.PKCS1_OAEP instead")
  359. def decrypt(self, ciphertext):
  360. """:meta private:"""
  361. raise NotImplementedError("Use module Crypto.Cipher.PKCS1_OAEP instead")
  362. def blind(self, M, B):
  363. """:meta private:"""
  364. raise NotImplementedError
  365. def unblind(self, M, B):
  366. """:meta private:"""
  367. raise NotImplementedError
  368. def size(self):
  369. """:meta private:"""
  370. raise NotImplementedError
  371. def generate(bits, randfunc=None, e=65537):
  372. """Create a new RSA key pair.
  373. The algorithm closely follows NIST `FIPS 186-4`_ in its
  374. sections B.3.1 and B.3.3. The modulus is the product of
  375. two non-strong probable primes.
  376. Each prime passes a suitable number of Miller-Rabin tests
  377. with random bases and a single Lucas test.
  378. Args:
  379. bits (integer):
  380. Key length, or size (in bits) of the RSA modulus.
  381. It must be at least 1024, but **2048 is recommended.**
  382. The FIPS standard only defines 1024, 2048 and 3072.
  383. Keyword Args:
  384. randfunc (callable):
  385. Function that returns random bytes.
  386. The default is :func:`Crypto.Random.get_random_bytes`.
  387. e (integer):
  388. Public RSA exponent. It must be an odd positive integer.
  389. It is typically a small number with very few ones in its
  390. binary representation.
  391. The FIPS standard requires the public exponent to be
  392. at least 65537 (the default).
  393. Returns: an RSA key object (:class:`RsaKey`, with private key).
  394. .. _FIPS 186-4: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
  395. """
  396. if bits < 1024:
  397. raise ValueError("RSA modulus length must be >= 1024")
  398. if e % 2 == 0 or e < 3:
  399. raise ValueError("RSA public exponent must be a positive, odd integer larger than 2.")
  400. if randfunc is None:
  401. randfunc = Random.get_random_bytes
  402. d = n = Integer(1)
  403. e = Integer(e)
  404. while n.size_in_bits() != bits and d < (1 << (bits // 2)):
  405. # Generate the prime factors of n: p and q.
  406. # By construciton, their product is always
  407. # 2^{bits-1} < p*q < 2^bits.
  408. size_q = bits // 2
  409. size_p = bits - size_q
  410. min_p = min_q = (Integer(1) << (2 * size_q - 1)).sqrt()
  411. if size_q != size_p:
  412. min_p = (Integer(1) << (2 * size_p - 1)).sqrt()
  413. def filter_p(candidate):
  414. return candidate > min_p and (candidate - 1).gcd(e) == 1
  415. p = generate_probable_prime(exact_bits=size_p,
  416. randfunc=randfunc,
  417. prime_filter=filter_p)
  418. min_distance = Integer(1) << (bits // 2 - 100)
  419. def filter_q(candidate):
  420. return (candidate > min_q and
  421. (candidate - 1).gcd(e) == 1 and
  422. abs(candidate - p) > min_distance)
  423. q = generate_probable_prime(exact_bits=size_q,
  424. randfunc=randfunc,
  425. prime_filter=filter_q)
  426. n = p * q
  427. lcm = (p - 1).lcm(q - 1)
  428. d = e.inverse(lcm)
  429. if p > q:
  430. p, q = q, p
  431. u = p.inverse(q)
  432. return RsaKey(n=n, e=e, d=d, p=p, q=q, u=u)
  433. def construct(rsa_components, consistency_check=True):
  434. r"""Construct an RSA key from a tuple of valid RSA components.
  435. The modulus **n** must be the product of two primes.
  436. The public exponent **e** must be odd and larger than 1.
  437. In case of a private key, the following equations must apply:
  438. .. math::
  439. \begin{align}
  440. p*q &= n \\
  441. e*d &\equiv 1 ( \text{mod lcm} [(p-1)(q-1)]) \\
  442. p*u &\equiv 1 ( \text{mod } q)
  443. \end{align}
  444. Args:
  445. rsa_components (tuple):
  446. A tuple of integers, with at least 2 and no
  447. more than 6 items. The items come in the following order:
  448. 1. RSA modulus *n*.
  449. 2. Public exponent *e*.
  450. 3. Private exponent *d*.
  451. Only required if the key is private.
  452. 4. First factor of *n* (*p*).
  453. Optional, but the other factor *q* must also be present.
  454. 5. Second factor of *n* (*q*). Optional.
  455. 6. CRT coefficient *q*, that is :math:`p^{-1} \text{mod }q`. Optional.
  456. Keyword Args:
  457. consistency_check (boolean):
  458. If ``True``, the library will verify that the provided components
  459. fulfil the main RSA properties.
  460. Raises:
  461. ValueError: when the key being imported fails the most basic RSA validity checks.
  462. Returns: An RSA key object (:class:`RsaKey`).
  463. """
  464. class InputComps(object):
  465. pass
  466. input_comps = InputComps()
  467. for (comp, value) in zip(('n', 'e', 'd', 'p', 'q', 'u'), rsa_components):
  468. setattr(input_comps, comp, Integer(value))
  469. n = input_comps.n
  470. e = input_comps.e
  471. if not hasattr(input_comps, 'd'):
  472. key = RsaKey(n=n, e=e)
  473. else:
  474. d = input_comps.d
  475. if hasattr(input_comps, 'q'):
  476. p = input_comps.p
  477. q = input_comps.q
  478. else:
  479. # Compute factors p and q from the private exponent d.
  480. # We assume that n has no more than two factors.
  481. # See 8.2.2(i) in Handbook of Applied Cryptography.
  482. ktot = d * e - 1
  483. # The quantity d*e-1 is a multiple of phi(n), even,
  484. # and can be represented as t*2^s.
  485. t = ktot
  486. while t % 2 == 0:
  487. t //= 2
  488. # Cycle through all multiplicative inverses in Zn.
  489. # The algorithm is non-deterministic, but there is a 50% chance
  490. # any candidate a leads to successful factoring.
  491. # See "Digitalized Signatures and Public Key Functions as Intractable
  492. # as Factorization", M. Rabin, 1979
  493. spotted = False
  494. a = Integer(2)
  495. while not spotted and a < 100:
  496. k = Integer(t)
  497. # Cycle through all values a^{t*2^i}=a^k
  498. while k < ktot:
  499. cand = pow(a, k, n)
  500. # Check if a^k is a non-trivial root of unity (mod n)
  501. if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
  502. # We have found a number such that (cand-1)(cand+1)=0 (mod n).
  503. # Either of the terms divides n.
  504. p = Integer(n).gcd(cand + 1)
  505. spotted = True
  506. break
  507. k *= 2
  508. # This value was not any good... let's try another!
  509. a += 2
  510. if not spotted:
  511. raise ValueError("Unable to compute factors p and q from exponent d.")
  512. # Found !
  513. assert ((n % p) == 0)
  514. q = n // p
  515. if hasattr(input_comps, 'u'):
  516. u = input_comps.u
  517. else:
  518. u = p.inverse(q)
  519. # Build key object
  520. key = RsaKey(n=n, e=e, d=d, p=p, q=q, u=u)
  521. # Verify consistency of the key
  522. if consistency_check:
  523. # Modulus and public exponent must be coprime
  524. if e <= 1 or e >= n:
  525. raise ValueError("Invalid RSA public exponent")
  526. if Integer(n).gcd(e) != 1:
  527. raise ValueError("RSA public exponent is not coprime to modulus")
  528. # For RSA, modulus must be odd
  529. if not n & 1:
  530. raise ValueError("RSA modulus is not odd")
  531. if key.has_private():
  532. # Modulus and private exponent must be coprime
  533. if d <= 1 or d >= n:
  534. raise ValueError("Invalid RSA private exponent")
  535. if Integer(n).gcd(d) != 1:
  536. raise ValueError("RSA private exponent is not coprime to modulus")
  537. # Modulus must be product of 2 primes
  538. if p * q != n:
  539. raise ValueError("RSA factors do not match modulus")
  540. if test_probable_prime(p) == COMPOSITE:
  541. raise ValueError("RSA factor p is composite")
  542. if test_probable_prime(q) == COMPOSITE:
  543. raise ValueError("RSA factor q is composite")
  544. # See Carmichael theorem
  545. phi = (p - 1) * (q - 1)
  546. lcm = phi // (p - 1).gcd(q - 1)
  547. if (e * d % int(lcm)) != 1:
  548. raise ValueError("Invalid RSA condition")
  549. if hasattr(key, 'u'):
  550. # CRT coefficient
  551. if u <= 1 or u >= q:
  552. raise ValueError("Invalid RSA component u")
  553. if (p * u % q) != 1:
  554. raise ValueError("Invalid RSA component u with p")
  555. return key
  556. def _import_pkcs1_private(encoded, *kwargs):
  557. # RSAPrivateKey ::= SEQUENCE {
  558. # version Version,
  559. # modulus INTEGER, -- n
  560. # publicExponent INTEGER, -- e
  561. # privateExponent INTEGER, -- d
  562. # prime1 INTEGER, -- p
  563. # prime2 INTEGER, -- q
  564. # exponent1 INTEGER, -- d mod (p-1)
  565. # exponent2 INTEGER, -- d mod (q-1)
  566. # coefficient INTEGER -- (inverse of q) mod p
  567. # }
  568. #
  569. # Version ::= INTEGER
  570. der = DerSequence().decode(encoded, nr_elements=9, only_ints_expected=True)
  571. if der[0] != 0:
  572. raise ValueError("No PKCS#1 encoding of an RSA private key")
  573. return construct(der[1:6] + [Integer(der[4]).inverse(der[5])])
  574. def _import_pkcs1_public(encoded, *kwargs):
  575. # RSAPublicKey ::= SEQUENCE {
  576. # modulus INTEGER, -- n
  577. # publicExponent INTEGER -- e
  578. # }
  579. der = DerSequence().decode(encoded, nr_elements=2, only_ints_expected=True)
  580. return construct(der)
  581. def _import_subjectPublicKeyInfo(encoded, *kwargs):
  582. algoid, encoded_key, params = _expand_subject_public_key_info(encoded)
  583. if algoid != oid or params is not None:
  584. raise ValueError("No RSA subjectPublicKeyInfo")
  585. return _import_pkcs1_public(encoded_key)
  586. def _import_x509_cert(encoded, *kwargs):
  587. sp_info = _extract_subject_public_key_info(encoded)
  588. return _import_subjectPublicKeyInfo(sp_info)
  589. def _import_pkcs8(encoded, passphrase):
  590. from Crypto.IO import PKCS8
  591. k = PKCS8.unwrap(encoded, passphrase)
  592. if k[0] != oid:
  593. raise ValueError("No PKCS#8 encoded RSA key")
  594. return _import_keyDER(k[1], passphrase)
  595. def _import_keyDER(extern_key, passphrase):
  596. """Import an RSA key (public or private half), encoded in DER form."""
  597. decodings = (_import_pkcs1_private,
  598. _import_pkcs1_public,
  599. _import_subjectPublicKeyInfo,
  600. _import_x509_cert,
  601. _import_pkcs8)
  602. for decoding in decodings:
  603. try:
  604. return decoding(extern_key, passphrase)
  605. except ValueError:
  606. pass
  607. raise ValueError("RSA key format is not supported")
  608. def _import_openssh_private_rsa(data, password):
  609. from ._openssh import (import_openssh_private_generic,
  610. read_bytes, read_string, check_padding)
  611. ssh_name, decrypted = import_openssh_private_generic(data, password)
  612. if ssh_name != "ssh-rsa":
  613. raise ValueError("This SSH key is not RSA")
  614. n, decrypted = read_bytes(decrypted)
  615. e, decrypted = read_bytes(decrypted)
  616. d, decrypted = read_bytes(decrypted)
  617. iqmp, decrypted = read_bytes(decrypted)
  618. p, decrypted = read_bytes(decrypted)
  619. q, decrypted = read_bytes(decrypted)
  620. _, padded = read_string(decrypted) # Comment
  621. check_padding(padded)
  622. build = [Integer.from_bytes(x) for x in (n, e, d, q, p, iqmp)]
  623. return construct(build)
  624. def import_key(extern_key, passphrase=None):
  625. """Import an RSA key (public or private).
  626. Args:
  627. extern_key (string or byte string):
  628. The RSA key to import.
  629. The following formats are supported for an RSA **public key**:
  630. - X.509 certificate (binary or PEM format)
  631. - X.509 ``subjectPublicKeyInfo`` DER SEQUENCE (binary or PEM
  632. encoding)
  633. - `PKCS#1`_ ``RSAPublicKey`` DER SEQUENCE (binary or PEM encoding)
  634. - An OpenSSH line (e.g. the content of ``~/.ssh/id_ecdsa``, ASCII)
  635. The following formats are supported for an RSA **private key**:
  636. - PKCS#1 ``RSAPrivateKey`` DER SEQUENCE (binary or PEM encoding)
  637. - `PKCS#8`_ ``PrivateKeyInfo`` or ``EncryptedPrivateKeyInfo``
  638. DER SEQUENCE (binary or PEM encoding)
  639. - OpenSSH (text format, introduced in `OpenSSH 6.5`_)
  640. For details about the PEM encoding, see `RFC1421`_/`RFC1423`_.
  641. passphrase (string or byte string):
  642. For private keys only, the pass phrase that encrypts the key.
  643. Returns: An RSA key object (:class:`RsaKey`).
  644. Raises:
  645. ValueError/IndexError/TypeError:
  646. When the given key cannot be parsed (possibly because the pass
  647. phrase is wrong).
  648. .. _RFC1421: http://www.ietf.org/rfc/rfc1421.txt
  649. .. _RFC1423: http://www.ietf.org/rfc/rfc1423.txt
  650. .. _`PKCS#1`: http://www.ietf.org/rfc/rfc3447.txt
  651. .. _`PKCS#8`: http://www.ietf.org/rfc/rfc5208.txt
  652. .. _`OpenSSH 6.5`: https://flak.tedunangst.com/post/new-openssh-key-format-and-bcrypt-pbkdf
  653. """
  654. from Crypto.IO import PEM
  655. extern_key = tobytes(extern_key)
  656. if passphrase is not None:
  657. passphrase = tobytes(passphrase)
  658. if extern_key.startswith(b'-----BEGIN OPENSSH PRIVATE KEY'):
  659. text_encoded = tostr(extern_key)
  660. openssh_encoded, marker, enc_flag = PEM.decode(text_encoded, passphrase)
  661. result = _import_openssh_private_rsa(openssh_encoded, passphrase)
  662. return result
  663. if extern_key.startswith(b'-----'):
  664. # This is probably a PEM encoded key.
  665. (der, marker, enc_flag) = PEM.decode(tostr(extern_key), passphrase)
  666. if enc_flag:
  667. passphrase = None
  668. return _import_keyDER(der, passphrase)
  669. if extern_key.startswith(b'ssh-rsa '):
  670. # This is probably an OpenSSH key
  671. keystring = binascii.a2b_base64(extern_key.split(b' ')[1])
  672. keyparts = []
  673. while len(keystring) > 4:
  674. length = struct.unpack(">I", keystring[:4])[0]
  675. keyparts.append(keystring[4:4 + length])
  676. keystring = keystring[4 + length:]
  677. e = Integer.from_bytes(keyparts[1])
  678. n = Integer.from_bytes(keyparts[2])
  679. return construct([n, e])
  680. if len(extern_key) > 0 and bord(extern_key[0]) == 0x30:
  681. # This is probably a DER encoded key
  682. return _import_keyDER(extern_key, passphrase)
  683. raise ValueError("RSA key format is not supported")
  684. # Backward compatibility
  685. importKey = import_key
  686. #: `Object ID`_ for the RSA encryption algorithm. This OID often indicates
  687. #: a generic RSA key, even when such key will be actually used for digital
  688. #: signatures.
  689. #:
  690. #: .. _`Object ID`: http://www.alvestrand.no/objectid/1.2.840.113549.1.1.1.html
  691. oid = "1.2.840.113549.1.1.1"