1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#
# RSA.py : RSA encryption/decryption
#
# Part of the Python Cryptography Toolkit
#
# Written by Andrew Kuchling, Paul Swartz, and others
#
# ===================================================================
# The contents of this file are dedicated to the public domain. To
# the extent that dedication to the public domain is not available,
# everyone is granted a worldwide, perpetual, royalty-free,
# non-exclusive license to exercise all rights associated with the
# contents of this file for any purpose whatsoever.
# No rights are reserved.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# ===================================================================
#
__revision__ = "$Id$"
from Crypto.PublicKey import pubkey
from Crypto.Util import number
def generate_py(bits, randfunc, progress_func=None):
"""generate(bits:int, randfunc:callable, progress_func:callable)
Generate an RSA key of length 'bits', using 'randfunc' to get
random data and 'progress_func', if present, to display
the progress of the key generation.
"""
obj=RSAobj()
obj.e = 65537L
# Generate the prime factors of n
if progress_func:
progress_func('p,q\n')
p = q = 1L
while number.size(p*q) < bits:
# Note that q might be one bit longer than p if somebody specifies an odd
# number of bits for the key. (Why would anyone do that? You don't get
# more security.)
#
# Note also that we ensure that e is coprime to (p-1) and (q-1).
# This is needed for encryption to work properly, according to the 1997
# paper by Robert D. Silverman of RSA Labs, "Fast generation of random,
# strong RSA primes", available at
# http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2713&rep=rep1&type=pdf
# Since e=65537 is prime, it is sufficient to check that e divides
# neither (p-1) nor (q-1).
p = 1L
while (p - 1) % obj.e == 0:
if progress_func:
progress_func('p\n')
p = pubkey.getPrime(bits/2, randfunc)
q = 1L
while (q - 1) % obj.e == 0:
if progress_func:
progress_func('q\n')
q = pubkey.getPrime(bits - (bits/2), randfunc)
# p shall be smaller than q (for calc of u)
if p > q:
(p, q)=(q, p)
obj.p = p
obj.q = q
if progress_func:
progress_func('u\n')
obj.u = pubkey.inverse(obj.p, obj.q)
obj.n = obj.p*obj.q
if progress_func:
progress_func('d\n')
obj.d=pubkey.inverse(obj.e, (obj.p-1)*(obj.q-1))
assert bits <= 1+obj.size(), "Generated key is too small"
return obj
class RSAobj(pubkey.pubkey):
def size(self):
"""size() : int
Return the maximum number of bits that can be handled by this key.
"""
return number.size(self.n) - 1
|
