# -*- coding: utf-8 -*- # # Copyright 2011 Sybren A. Stüvel # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. '''RSA key generation code. Create new keys with the newkeys() function. It will give you a PublicKey and a PrivateKey object. Loading and saving keys requires the pyasn1 module. This module is imported as late as possible, such that other functionality will remain working in absence of pyasn1. ''' import logging from rsa._compat import b, bytes_type import rsa.prime import rsa.pem import rsa.common log = logging.getLogger(__name__) class AbstractKey(object): '''Abstract superclass for private and public keys.''' @classmethod def load_pkcs1(cls, keyfile, format='PEM'): r'''Loads a key in PKCS#1 DER or PEM format. :param keyfile: contents of a DER- or PEM-encoded file that contains the public key. :param format: the format of the file to load; 'PEM' or 'DER' :return: a PublicKey object ''' methods = { 'PEM': cls._load_pkcs1_pem, 'DER': cls._load_pkcs1_der, } if format not in methods: formats = ', '.join(sorted(methods.keys())) raise ValueError('Unsupported format: %r, try one of %s' % (format, formats)) method = methods[format] return method(keyfile) def save_pkcs1(self, format='PEM'): '''Saves the public key in PKCS#1 DER or PEM format. :param format: the format to save; 'PEM' or 'DER' :returns: the DER- or PEM-encoded public key. ''' methods = { 'PEM': self._save_pkcs1_pem, 'DER': self._save_pkcs1_der, } if format not in methods: formats = ', '.join(sorted(methods.keys())) raise ValueError('Unsupported format: %r, try one of %s' % (format, formats)) method = methods[format] return method() class PublicKey(AbstractKey): '''Represents a public RSA key. This key is also known as the 'encryption key'. It contains the 'n' and 'e' values. Supports attributes as well as dictionary-like access. Attribute accesss is faster, though. >>> PublicKey(5, 3) PublicKey(5, 3) >>> key = PublicKey(5, 3) >>> key.n 5 >>> key['n'] 5 >>> key.e 3 >>> key['e'] 3 ''' __slots__ = ('n', 'e') def __init__(self, n, e): self.n = n self.e = e def __getitem__(self, key): return getattr(self, key) def __repr__(self): return 'PublicKey(%i, %i)' % (self.n, self.e) def __eq__(self, other): if other is None: return False if not isinstance(other, PublicKey): return False return self.n == other.n and self.e == other.e def __ne__(self, other): return not (self == other) @classmethod def _load_pkcs1_der(cls, keyfile): r'''Loads a key in PKCS#1 DER format. @param keyfile: contents of a DER-encoded file that contains the public key. @return: a PublicKey object First let's construct a DER encoded key: >>> import base64 >>> b64der = 'MAwCBQCNGmYtAgMBAAE=' >>> der = base64.decodestring(b64der) This loads the file: >>> PublicKey._load_pkcs1_der(der) PublicKey(2367317549, 65537) ''' from pyasn1.codec.der import decoder from rsa.asn1 import AsnPubKey (priv, _) = decoder.decode(keyfile, asn1Spec=AsnPubKey()) return cls(n=int(priv['modulus']), e=int(priv['publicExponent'])) def _save_pkcs1_der(self): '''Saves the public key in PKCS#1 DER format. @returns: the DER-encoded public key. ''' from pyasn1.codec.der import encoder from rsa.asn1 import AsnPubKey # Create the ASN object asn_key = AsnPubKey() asn_key.setComponentByName('modulus', self.n) asn_key.setComponentByName('publicExponent', self.e) return encoder.encode(asn_key) @classmethod def _load_pkcs1_pem(cls, keyfile): '''Loads a PKCS#1 PEM-encoded public key file. The contents of the file before the "-----BEGIN RSA PUBLIC KEY-----" and after the "-----END RSA PUBLIC KEY-----" lines is ignored. @param keyfile: contents of a PEM-encoded file that contains the public key. @return: a PublicKey object ''' der = rsa.pem.load_pem(keyfile, 'RSA PUBLIC KEY') return cls._load_pkcs1_der(der) def _save_pkcs1_pem(self): '''Saves a PKCS#1 PEM-encoded public key file. @return: contents of a PEM-encoded file that contains the public key. ''' der = self._save_pkcs1_der() return rsa.pem.save_pem(der, 'RSA PUBLIC KEY') @classmethod def load_pkcs1_openssl_pem(cls, keyfile): '''Loads a PKCS#1.5 PEM-encoded public key file from OpenSSL. These files can be recognised in that they start with BEGIN PUBLIC KEY rather than BEGIN RSA PUBLIC KEY. The contents of the file before the "-----BEGIN PUBLIC KEY-----" and after the "-----END PUBLIC KEY-----" lines is ignored. @param keyfile: contents of a PEM-encoded file that contains the public key, from OpenSSL. @return: a PublicKey object ''' der = rsa.pem.load_pem(keyfile, 'PUBLIC KEY') return cls.load_pkcs1_openssl_der(der) @classmethod def load_pkcs1_openssl_der(cls, keyfile): '''Loads a PKCS#1 DER-encoded public key file from OpenSSL. @param keyfile: contents of a DER-encoded file that contains the public key, from OpenSSL. @return: a PublicKey object ''' from rsa.asn1 import OpenSSLPubKey from pyasn1.codec.der import decoder from pyasn1.type import univ (keyinfo, _) = decoder.decode(keyfile, asn1Spec=OpenSSLPubKey()) if keyinfo['header']['oid'] != univ.ObjectIdentifier('1.2.840.113549.1.1.1'): raise TypeError("This is not a DER-encoded OpenSSL-compatible public key") return cls._load_pkcs1_der(keyinfo['key'][1:]) class PrivateKey(AbstractKey): '''Represents a private RSA key. This key is also known as the 'decryption key'. It contains the 'n', 'e', 'd', 'p', 'q' and other values. Supports attributes as well as dictionary-like access. Attribute accesss is faster, though. >>> PrivateKey(3247, 65537, 833, 191, 17) PrivateKey(3247, 65537, 833, 191, 17) exp1, exp2 and coef don't have to be given, they will be calculated: >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287) >>> pk.exp1 55063 >>> pk.exp2 10095 >>> pk.coef 50797 If you give exp1, exp2 or coef, they will be used as-is: >>> pk = PrivateKey(1, 2, 3, 4, 5, 6, 7, 8) >>> pk.exp1 6 >>> pk.exp2 7 >>> pk.coef 8 ''' __slots__ = ('n', 'e', 'd', 'p', 'q', 'exp1', 'exp2', 'coef') def __init__(self, n, e, d, p, q, exp1=None, exp2=None, coef=None): self.n = n self.e = e self.d = d self.p = p self.q = q # Calculate the other values if they aren't supplied if exp1 is None: self.exp1 = int(d % (p - 1)) else: self.exp1 = exp1 if exp1 is None: self.exp2 = int(d % (q - 1)) else: self.exp2 = exp2 if coef is None: self.coef = rsa.common.inverse(q, p) else: self.coef = coef def __getitem__(self, key): return getattr(self, key) def __repr__(self): return 'PrivateKey(%(n)i, %(e)i, %(d)i, %(p)i, %(q)i)' % self def __eq__(self, other): if other is None: return False if not isinstance(other, PrivateKey): return False return (self.n == other.n and self.e == other.e and self.d == other.d and self.p == other.p and self.q == other.q and self.exp1 == other.exp1 and self.exp2 == other.exp2 and self.coef == other.coef) def __ne__(self, other): return not (self == other) @classmethod def _load_pkcs1_der(cls, keyfile): r'''Loads a key in PKCS#1 DER format. @param keyfile: contents of a DER-encoded file that contains the private key. @return: a PrivateKey object First let's construct a DER encoded key: >>> import base64 >>> b64der = 'MC4CAQACBQDeKYlRAgMBAAECBQDHn4npAgMA/icCAwDfxwIDANcXAgInbwIDAMZt' >>> der = base64.decodestring(b64der) This loads the file: >>> PrivateKey._load_pkcs1_der(der) PrivateKey(3727264081, 65537, 3349121513, 65063, 57287) ''' from pyasn1.codec.der import decoder (priv, _) = decoder.decode(keyfile) # ASN.1 contents of DER encoded private key: # # RSAPrivateKey ::= SEQUENCE { # version Version, # modulus INTEGER, -- n # publicExponent INTEGER, -- e # privateExponent INTEGER, -- d # prime1 INTEGER, -- p # prime2 INTEGER, -- q # exponent1 INTEGER, -- d mod (p-1) # exponent2 INTEGER, -- d mod (q-1) # coefficient INTEGER, -- (inverse of q) mod p # otherPrimeInfos OtherPrimeInfos OPTIONAL # } if priv[0] != 0: raise ValueError('Unable to read this file, version %s != 0' % priv[0]) as_ints = tuple(int(x) for x in priv[1:9]) return cls(*as_ints) def _save_pkcs1_der(self): '''Saves the private key in PKCS#1 DER format. @returns: the DER-encoded private key. ''' from pyasn1.type import univ, namedtype from pyasn1.codec.der import encoder class AsnPrivKey(univ.Sequence): componentType = namedtype.NamedTypes( namedtype.NamedType('version', univ.Integer()), namedtype.NamedType('modulus', univ.Integer()), namedtype.NamedType('publicExponent', univ.Integer()), namedtype.NamedType('privateExponent', univ.Integer()), namedtype.NamedType('prime1', univ.Integer()), namedtype.NamedType('prime2', univ.Integer()), namedtype.NamedType('exponent1', univ.Integer()), namedtype.NamedType('exponent2', univ.Integer()), namedtype.NamedType('coefficient', univ.Integer()), ) # Create the ASN object asn_key = AsnPrivKey() asn_key.setComponentByName('version', 0) asn_key.setComponentByName('modulus', self.n) asn_key.setComponentByName('publicExponent', self.e) asn_key.setComponentByName('privateExponent', self.d) asn_key.setComponentByName('prime1', self.p) asn_key.setComponentByName('prime2', self.q) asn_key.setComponentByName('exponent1', self.exp1) asn_key.setComponentByName('exponent2', self.exp2) asn_key.setComponentByName('coefficient', self.coef) return encoder.encode(asn_key) @classmethod def _load_pkcs1_pem(cls, keyfile): '''Loads a PKCS#1 PEM-encoded private key file. The contents of the file before the "-----BEGIN RSA PRIVATE KEY-----" and after the "-----END RSA PRIVATE KEY-----" lines is ignored. @param keyfile: contents of a PEM-encoded file that contains the private key. @return: a PrivateKey object ''' der = rsa.pem.load_pem(keyfile, b('RSA PRIVATE KEY')) return cls._load_pkcs1_der(der) def _save_pkcs1_pem(self): '''Saves a PKCS#1 PEM-encoded private key file. @return: contents of a PEM-encoded file that contains the private key. ''' der = self._save_pkcs1_der() return rsa.pem.save_pem(der, b('RSA PRIVATE KEY')) def find_p_q(nbits, getprime_func=rsa.prime.getprime, accurate=True): ''''Returns a tuple of two different primes of nbits bits each. The resulting p * q has exacty 2 * nbits bits, and the returned p and q will not be equal. :param nbits: the number of bits in each of p and q. :param getprime_func: the getprime function, defaults to :py:func:`rsa.prime.getprime`. *Introduced in Python-RSA 3.1* :param accurate: whether to enable accurate mode or not. :returns: (p, q), where p > q >>> (p, q) = find_p_q(128) >>> from rsa import common >>> common.bit_size(p * q) 256 When not in accurate mode, the number of bits can be slightly less >>> (p, q) = find_p_q(128, accurate=False) >>> from rsa import common >>> common.bit_size(p * q) <= 256 True >>> common.bit_size(p * q) > 240 True ''' total_bits = nbits * 2 # Make sure that p and q aren't too close or the factoring programs can # factor n. shift = nbits // 16 pbits = nbits + shift qbits = nbits - shift # Choose the two initial primes log.debug('find_p_q(%i): Finding p', nbits) p = getprime_func(pbits) log.debug('find_p_q(%i): Finding q', nbits) q = getprime_func(qbits) def is_acceptable(p, q): '''Returns True iff p and q are acceptable: - p and q differ - (p * q) has the right nr of bits (when accurate=True) ''' if p == q: return False if not accurate: return True # Make sure we have just the right amount of bits found_size = rsa.common.bit_size(p * q) return total_bits == found_size # Keep choosing other primes until they match our requirements. change_p = False while not is_acceptable(p, q): # Change p on one iteration and q on the other if change_p: p = getprime_func(pbits) else: q = getprime_func(qbits) change_p = not change_p # We want p > q as described on # http://www.di-mgt.com.au/rsa_alg.html#crt return (max(p, q), min(p, q)) def calculate_keys(p, q, nbits): '''Calculates an encryption and a decryption key given p and q, and returns them as a tuple (e, d) ''' phi_n = (p - 1) * (q - 1) # A very common choice for e is 65537 e = 65537 try: d = rsa.common.inverse(e, phi_n) except ValueError: raise ValueError("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n)) if (e * d) % phi_n != 1: raise ValueError("e (%d) and d (%d) are not mult. inv. modulo " "phi_n (%d)" % (e, d, phi_n)) return (e, d) def gen_keys(nbits, getprime_func, accurate=True): '''Generate RSA keys of nbits bits. Returns (p, q, e, d). Note: this can take a long time, depending on the key size. :param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and ``q`` will use ``nbits/2`` bits. :param getprime_func: either :py:func:`rsa.prime.getprime` or a function with similar signature. ''' # Regenerate p and q values, until calculate_keys doesn't raise a # ValueError. while True: (p, q) = find_p_q(nbits // 2, getprime_func, accurate) try: (e, d) = calculate_keys(p, q, nbits // 2) break except ValueError: pass return (p, q, e, d) def newkeys(nbits, accurate=True, poolsize=1): '''Generates public and private keys, and returns them as (pub, priv). The public key is also known as the 'encryption key', and is a :py:class:`rsa.PublicKey` object. The private key is also known as the 'decryption key' and is a :py:class:`rsa.PrivateKey` object. :param nbits: the number of bits required to store ``n = p*q``. :param accurate: when True, ``n`` will have exactly the number of bits you asked for. However, this makes key generation much slower. When False, `n`` may have slightly less bits. :param poolsize: the number of processes to use to generate the prime numbers. If set to a number > 1, a parallel algorithm will be used. This requires Python 2.6 or newer. :returns: a tuple (:py:class:`rsa.PublicKey`, :py:class:`rsa.PrivateKey`) The ``poolsize`` parameter was added in *Python-RSA 3.1* and requires Python 2.6 or newer. ''' if nbits < 16: raise ValueError('Key too small') if poolsize < 1: raise ValueError('Pool size (%i) should be >= 1' % poolsize) # Determine which getprime function to use if poolsize > 1: from rsa import parallel import functools getprime_func = functools.partial(parallel.getprime, poolsize=poolsize) else: getprime_func = rsa.prime.getprime # Generate the key components (p, q, e, d) = gen_keys(nbits, getprime_func, accurate=accurate) # Create the key objects n = p * q return ( PublicKey(n, e), PrivateKey(n, e, d, p, q) ) __all__ = ['PublicKey', 'PrivateKey', 'newkeys'] if __name__ == '__main__': import doctest try: for count in range(100): (failures, tests) = doctest.testmod() if failures: break if (count and count % 10 == 0) or count == 1: print('%i times' % count) except KeyboardInterrupt: print('Aborted') else: print('Doctests done')