]>
gitweb.pimeys.fr Git - NK2015_Client_Python_Alpha.git/blob - rsa_source/rsa/key.py
1 # -*- coding: utf-8 -*-
3 # Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 '''RSA key generation code.
19 Create new keys with the newkeys() function. It will give you a PublicKey and a
22 Loading and saving keys requires the pyasn1 module. This module is imported as
23 late as possible, such that other functionality will remain working in absence
34 log
= logging
.getLogger(__name__
)
36 class AbstractKey(object):
37 '''Abstract superclass for private and public keys.'''
40 def load_pkcs1(cls
, keyfile
, format
='PEM'):
41 r
'''Loads a key in PKCS#1 DER or PEM format.
43 :param keyfile: contents of a DER- or PEM-encoded file that contains
45 :param format: the format of the file to load; 'PEM' or 'DER'
47 :return: a PublicKey object
52 'PEM': cls
._load
_pkcs
1_pem
,
53 'DER': cls
._load
_pkcs
1_der
,
56 if format
not in methods
:
57 formats
= ', '.join(sorted(methods
.keys()))
58 raise ValueError('Unsupported format: %r, try one of %s' % (format
,
61 method
= methods
[format
]
62 return method(keyfile
)
64 def save_pkcs1(self
, format
='PEM'):
65 '''Saves the public key in PKCS#1 DER or PEM format.
67 :param format: the format to save; 'PEM' or 'DER'
68 :returns: the DER- or PEM-encoded public key.
73 'PEM': self
._save
_pkcs
1_pem
,
74 'DER': self
._save
_pkcs
1_der
,
77 if format
not in methods
:
78 formats
= ', '.join(sorted(methods
.keys()))
79 raise ValueError('Unsupported format: %r, try one of %s' % (format
,
82 method
= methods
[format
]
85 class PublicKey(AbstractKey
):
86 '''Represents a public RSA key.
88 This key is also known as the 'encryption key'. It contains the 'n' and 'e'
91 Supports attributes as well as dictionary-like access. Attribute accesss is
97 >>> key = PublicKey(5, 3)
109 __slots__
= ('n', 'e')
111 def __init__(self
, n
, e
):
115 def __getitem__(self
, key
):
116 return getattr(self
, key
)
119 return u
'PublicKey(%i, %i)' % (self
.n
, self
.e
)
121 def __eq__(self
, other
):
125 if not isinstance(other
, PublicKey
):
128 return self
.n
== other
.n
and self
.e
== other
.e
130 def __ne__(self
, other
):
131 return not (self
== other
)
134 def _load_pkcs1_der(cls
, keyfile
):
135 r
'''Loads a key in PKCS#1 DER format.
137 @param keyfile: contents of a DER-encoded file that contains the public
139 @return: a PublicKey object
141 First let's construct a DER encoded key:
144 >>> b64der = 'MAwCBQCNGmYtAgMBAAE='
145 >>> der = base64.decodestring(b64der)
149 >>> PublicKey._load_pkcs1_der(der)
150 PublicKey(2367317549, 65537)
154 from pyasn1
.codec
.der
import decoder
155 (priv
, _
) = decoder
.decode(keyfile
)
157 # ASN.1 contents of DER encoded public key:
159 # RSAPublicKey ::= SEQUENCE {
160 # modulus INTEGER, -- n
161 # publicExponent INTEGER, -- e
163 as_ints
= tuple(int(x
) for x
in priv
)
166 def _save_pkcs1_der(self
):
167 '''Saves the public key in PKCS#1 DER format.
169 @returns: the DER-encoded public key.
172 from pyasn1
.type import univ
, namedtype
173 from pyasn1
.codec
.der
import encoder
175 class AsnPubKey(univ
.Sequence
):
176 componentType
= namedtype
.NamedTypes(
177 namedtype
.NamedType('modulus', univ
.Integer()),
178 namedtype
.NamedType('publicExponent', univ
.Integer()),
181 # Create the ASN object
182 asn_key
= AsnPubKey()
183 asn_key
.setComponentByName('modulus', self
.n
)
184 asn_key
.setComponentByName('publicExponent', self
.e
)
186 return encoder
.encode(asn_key
)
189 def _load_pkcs1_pem(cls
, keyfile
):
190 '''Loads a PKCS#1 PEM-encoded public key file.
192 The contents of the file before the "-----BEGIN RSA PUBLIC KEY-----" and
193 after the "-----END RSA PUBLIC KEY-----" lines is ignored.
195 @param keyfile: contents of a PEM-encoded file that contains the public
197 @return: a PublicKey object
200 der
= rsa
.pem
.load_pem(keyfile
, 'RSA PUBLIC KEY')
201 return cls
._load
_pkcs
1_der
(der
)
203 def _save_pkcs1_pem(self
):
204 '''Saves a PKCS#1 PEM-encoded public key file.
206 @return: contents of a PEM-encoded file that contains the public key.
209 der
= self
._save
_pkcs
1_der
()
210 return rsa
.pem
.save_pem(der
, 'RSA PUBLIC KEY')
212 class PrivateKey(AbstractKey
):
213 '''Represents a private RSA key.
215 This key is also known as the 'decryption key'. It contains the 'n', 'e',
216 'd', 'p', 'q' and other values.
218 Supports attributes as well as dictionary-like access. Attribute accesss is
221 >>> PrivateKey(3247, 65537, 833, 191, 17)
222 PrivateKey(3247, 65537, 833, 191, 17)
224 exp1, exp2 and coef don't have to be given, they will be calculated:
226 >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
234 If you give exp1, exp2 or coef, they will be used as-is:
236 >>> pk = PrivateKey(1, 2, 3, 4, 5, 6, 7, 8)
246 __slots__
= ('n', 'e', 'd', 'p', 'q', 'exp1', 'exp2', 'coef')
248 def __init__(self
, n
, e
, d
, p
, q
, exp1
=None, exp2
=None, coef
=None):
255 # Calculate the other values if they aren't supplied
257 self
.exp1
= int(d
% (p
- 1))
262 self
.exp2
= int(d
% (q
- 1))
267 (_
, self
.coef
, _
) = extended_gcd(q
, p
)
271 def __getitem__(self
, key
):
272 return getattr(self
, key
)
275 return u
'PrivateKey(%(n)i, %(e)i, %(d)i, %(p)i, %(q)i)' % self
277 def __eq__(self
, other
):
281 if not isinstance(other
, PrivateKey
):
284 return (self
.n
== other
.n
and
285 self
.e
== other
.e
and
286 self
.d
== other
.d
and
287 self
.p
== other
.p
and
288 self
.q
== other
.q
and
289 self
.exp1
== other
.exp1
and
290 self
.exp2
== other
.exp2
and
291 self
.coef
== other
.coef
)
293 def __ne__(self
, other
):
294 return not (self
== other
)
297 def _load_pkcs1_der(cls
, keyfile
):
298 r
'''Loads a key in PKCS#1 DER format.
300 @param keyfile: contents of a DER-encoded file that contains the private
302 @return: a PrivateKey object
304 First let's construct a DER encoded key:
307 >>> b64der = 'MC4CAQACBQDeKYlRAgMBAAECBQDHn4npAgMA/icCAwDfxwIDANcXAgInbwIDAMZt'
308 >>> der = base64.decodestring(b64der)
312 >>> PrivateKey._load_pkcs1_der(der)
313 PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
317 from pyasn1
.codec
.der
import decoder
318 (priv
, _
) = decoder
.decode(keyfile
)
320 # ASN.1 contents of DER encoded private key:
322 # RSAPrivateKey ::= SEQUENCE {
324 # modulus INTEGER, -- n
325 # publicExponent INTEGER, -- e
326 # privateExponent INTEGER, -- d
327 # prime1 INTEGER, -- p
328 # prime2 INTEGER, -- q
329 # exponent1 INTEGER, -- d mod (p-1)
330 # exponent2 INTEGER, -- d mod (q-1)
331 # coefficient INTEGER, -- (inverse of q) mod p
332 # otherPrimeInfos OtherPrimeInfos OPTIONAL
336 raise ValueError('Unable to read this file, version %s != 0' % priv
[0])
338 as_ints
= tuple(int(x
) for x
in priv
[1:9])
341 def _save_pkcs1_der(self
):
342 '''Saves the private key in PKCS#1 DER format.
344 @returns: the DER-encoded private key.
347 from pyasn1
.type import univ
, namedtype
348 from pyasn1
.codec
.der
import encoder
350 class AsnPrivKey(univ
.Sequence
):
351 componentType
= namedtype
.NamedTypes(
352 namedtype
.NamedType('version', univ
.Integer()),
353 namedtype
.NamedType('modulus', univ
.Integer()),
354 namedtype
.NamedType('publicExponent', univ
.Integer()),
355 namedtype
.NamedType('privateExponent', univ
.Integer()),
356 namedtype
.NamedType('prime1', univ
.Integer()),
357 namedtype
.NamedType('prime2', univ
.Integer()),
358 namedtype
.NamedType('exponent1', univ
.Integer()),
359 namedtype
.NamedType('exponent2', univ
.Integer()),
360 namedtype
.NamedType('coefficient', univ
.Integer()),
363 # Create the ASN object
364 asn_key
= AsnPrivKey()
365 asn_key
.setComponentByName('version', 0)
366 asn_key
.setComponentByName('modulus', self
.n
)
367 asn_key
.setComponentByName('publicExponent', self
.e
)
368 asn_key
.setComponentByName('privateExponent', self
.d
)
369 asn_key
.setComponentByName('prime1', self
.p
)
370 asn_key
.setComponentByName('prime2', self
.q
)
371 asn_key
.setComponentByName('exponent1', self
.exp1
)
372 asn_key
.setComponentByName('exponent2', self
.exp2
)
373 asn_key
.setComponentByName('coefficient', self
.coef
)
375 return encoder
.encode(asn_key
)
378 def _load_pkcs1_pem(cls
, keyfile
):
379 '''Loads a PKCS#1 PEM-encoded private key file.
381 The contents of the file before the "-----BEGIN RSA PRIVATE KEY-----" and
382 after the "-----END RSA PRIVATE KEY-----" lines is ignored.
384 @param keyfile: contents of a PEM-encoded file that contains the private
386 @return: a PrivateKey object
389 der
= rsa
.pem
.load_pem(keyfile
, 'RSA PRIVATE KEY')
390 return cls
._load
_pkcs
1_der
(der
)
392 def _save_pkcs1_pem(self
):
393 '''Saves a PKCS#1 PEM-encoded private key file.
395 @return: contents of a PEM-encoded file that contains the private key.
398 der
= self
._save
_pkcs
1_der
()
399 return rsa
.pem
.save_pem(der
, 'RSA PRIVATE KEY')
402 def extended_gcd(a
, b
):
403 """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
405 # r = gcd(a,b) i = multiplicitive inverse of a mod b
406 # or j = multiplicitive inverse of b mod a
407 # Neg return values for i or j are made positive mod b or a respectively
408 # Iterateive Version is faster and uses much less stack space
413 oa
= a
#Remember original a/b to remove
414 ob
= b
#negative values from return results
418 (x
, lx
) = ((lx
- (q
* x
)),x
)
419 (y
, ly
) = ((ly
- (q
* y
)),y
)
420 if (lx
< 0): lx
+= ob
#If neg wrap modulo orignal b
421 if (ly
< 0): ly
+= oa
#If neg wrap modulo orignal a
422 return (a
, lx
, ly
) #Return only positive values
424 def find_p_q(nbits
, accurate
=True):
425 ''''Returns a tuple of two different primes of nbits bits each.
427 The resulting p * q has exacty 2 * nbits bits, and the returned p and q
430 @param nbits: the number of bits in each of p and q.
431 @param accurate: whether to enable accurate mode or not.
432 @returns (p, q), where p > q
434 >>> (p, q) = find_p_q(128)
435 >>> from rsa import common
436 >>> common.bit_size(p * q)
439 When not in accurate mode, the number of bits can be slightly less
441 >>> (p, q) = find_p_q(128, accurate=False)
442 >>> from rsa import common
443 >>> common.bit_size(p * q) <= 256
445 >>> common.bit_size(p * q) > 240
450 total_bits
= nbits
* 2
452 # Make sure that p and q aren't too close or the factoring programs can
455 pbits
= nbits
+ shift
456 qbits
= nbits
- shift
458 # Choose the two initial primes
459 log
.debug('find_p_q(%i): Finding p', nbits
)
460 p
= rsa
.prime
.getprime(pbits
)
461 log
.debug('find_p_q(%i): Finding q', nbits
)
462 q
= rsa
.prime
.getprime(qbits
)
464 def is_acceptable(p
, q
):
465 '''Returns True iff p and q are acceptable:
468 - (p * q) has the right nr of bits (when accurate=True)
477 # Make sure we have just the right amount of bits
478 found_size
= rsa
.common
.bit_size(p
* q
)
479 return total_bits
== found_size
481 # Keep choosing other primes until they match our requirements.
484 while not is_acceptable(p
, q
):
486 # Change p on one iteration and q on the other
488 log
.debug(' find another p')
489 p
= rsa
.prime
.getprime(pbits
)
491 log
.debug(' find another q')
492 q
= rsa
.prime
.getprime(qbits
)
494 change_p
= not change_p
496 # We want p > q as described on
497 # http://www.di-mgt.com.au/rsa_alg.html#crt
498 return (max(p
, q
), min(p
, q
))
500 def calculate_keys(p
, q
, nbits
):
501 """Calculates an encryption and a decryption key given p and q, and
502 returns them as a tuple (e, d)
506 phi_n
= (p
- 1) * (q
- 1)
508 # A very common choice for e is 65537
511 (divider
, d
, _
) = extended_gcd(e
, phi_n
)
514 raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
517 raise ValueError("extended_gcd shouldn't return negative values, "
519 if (e
* d
) % phi_n
!= 1:
520 raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
521 "phi_n (%d)" % (e
, d
, phi_n
))
525 def gen_keys(nbits
, accurate
=True):
526 """Generate RSA keys of nbits bits. Returns (p, q, e, d).
528 Note: this can take a long time, depending on the key size.
530 @param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
531 ``q`` will use ``nbits/2`` bits.
534 (p
, q
) = find_p_q(nbits
// 2, accurate
)
535 (e
, d
) = calculate_keys(p
, q
, nbits
// 2)
539 def newkeys(nbits
, accurate
=True):
540 """Generates public and private keys, and returns them as (pub, priv).
542 The public key is also known as the 'encryption key', and is a
543 :py:class:`PublicKey` object. The private key is also known as the
544 'decryption key' and is a :py:class:`PrivateKey` object.
546 :param nbits: the number of bits required to store ``n = p*q``.
547 :param accurate: when True, ``n`` will have exactly the number of bits you
548 asked for. However, this makes key generation much slower. When False,
549 `n`` may have slightly less bits.
551 :returns: a tuple (:py:class:`rsa.PublicKey`, :py:class:`rsa.PrivateKey`)
556 raise ValueError('Key too small')
558 (p
, q
, e
, d
) = gen_keys(nbits
)
564 PrivateKey(n
, e
, d
, p
, q
)
567 __all__
= ['PublicKey', 'PrivateKey', 'newkeys']
569 if __name__
== '__main__':
573 for count
in range(100):
574 (failures
, tests
) = doctest
.testmod()
578 if (count
and count
% 10 == 0) or count
== 1:
579 print '%i times' % count
580 except KeyboardInterrupt:
583 print 'Doctests done'