1
2
3
4
5
6
7 """cryptomath module
8
9 This module has basic math/crypto code."""
10 from __future__ import print_function
11 import os
12 import math
13 import base64
14 import binascii
15
16 from .compat import *
17
18
19
20
21
22
23
24 try:
25 from M2Crypto import m2
26 m2cryptoLoaded = True
27
28 except ImportError:
29 m2cryptoLoaded = False
30
31
32 try:
33 import gmpy
34 gmpyLoaded = True
35 except ImportError:
36 gmpyLoaded = False
37
38
39 try:
40 import Crypto.Cipher.AES
41 pycryptoLoaded = True
42 except ImportError:
43 pycryptoLoaded = False
44
45
46
47
48
49
50
51 import zlib
52 length = len(zlib.compress(os.urandom(1000)))
53 assert(length > 900)
54
56 b = bytearray(os.urandom(howMany))
57 assert(len(b) == howMany)
58 return b
59
60 prngName = "os.urandom"
61
62
63
64
65
66 import hmac
67 import hashlib
68
71
74
79
84
85
86
87
88
89
91 total = 0
92 multiplier = 1
93 for count in range(len(b)-1, -1, -1):
94 byte = b[count]
95 total += multiplier * byte
96 multiplier *= 256
97 return total
98
100 """Convert an integer into a bytearray, zero-pad to howManyBytes.
101
102 The returned bytearray may be smaller than howManyBytes, but will
103 not be larger. The returned bytearray will contain a big-endian
104 encoding of the input integer (n).
105 """
106 if howManyBytes == None:
107 howManyBytes = numBytes(n)
108 b = bytearray(howManyBytes)
109 for count in range(howManyBytes-1, -1, -1):
110 b[count] = int(n % 256)
111 n >>= 8
112 return b
113
115 if (ord(mpi[4]) & 0x80) !=0:
116 raise AssertionError()
117 b = bytearray(mpi[4:])
118 return bytesToNumber(b)
119
134
135
136
137
138
139
141 if n==0:
142 return 0
143 s = "%x" % n
144 return ((len(s)-1)*4) + \
145 {'0':0, '1':1, '2':2, '3':2,
146 '4':3, '5':3, '6':3, '7':3,
147 '8':4, '9':4, 'a':4, 'b':4,
148 'c':4, 'd':4, 'e':4, 'f':4,
149 }[s[0]]
150 return int(math.floor(math.log(n, 2))+1)
151
153 if n==0:
154 return 0
155 bits = numBits(n)
156 return int(math.ceil(bits / 8.0))
157
158
159
160
161
163 if low >= high:
164 raise AssertionError()
165 howManyBits = numBits(high)
166 howManyBytes = numBytes(high)
167 lastBits = howManyBits % 8
168 while 1:
169 bytes = getRandomBytes(howManyBytes)
170 if lastBits:
171 bytes[0] = bytes[0] % (1 << lastBits)
172 n = bytesToNumber(bytes)
173 if n >= low and n < high:
174 return n
175
177 a, b = max(a,b), min(a,b)
178 while b:
179 a, b = b, a % b
180 return a
181
183 return (a * b) // gcd(a, b)
184
185
186
188 c, d = a, b
189 uc, ud = 1, 0
190 while c != 0:
191 q = d // c
192 c, d = d-(q*c), c
193 uc, ud = ud - (q * uc), uc
194 if d == 1:
195 return ud % b
196 return 0
197
198
199 if gmpyLoaded:
200 - def powMod(base, power, modulus):
201 base = gmpy.mpz(base)
202 power = gmpy.mpz(power)
203 modulus = gmpy.mpz(modulus)
204 result = pow(base, power, modulus)
205 return long(result)
206
207 else:
208 - def powMod(base, power, modulus):
209 if power < 0:
210 result = pow(base, power*-1, modulus)
211 result = invMod(result, modulus)
212 return result
213 else:
214 return pow(base, power, modulus)
215
216
218 sieve = list(range(n))
219 for count in range(2, int(math.sqrt(n))):
220 if sieve[count] == 0:
221 continue
222 x = sieve[count] * 2
223 while x < len(sieve):
224 sieve[x] = 0
225 x += sieve[count]
226 sieve = [x for x in sieve[2:] if x]
227 return sieve
228
229 sieve = makeSieve(1000)
230
231 -def isPrime(n, iterations=5, display=False):
232
233 for x in sieve:
234 if x >= n: return True
235 if n % x == 0: return False
236
237
238
239 if display: print("*", end=' ')
240 s, t = n-1, 0
241 while s % 2 == 0:
242 s, t = s//2, t+1
243
244 a = 2
245 for count in range(iterations):
246 v = powMod(a, s, n)
247 if v==1:
248 continue
249 i = 0
250 while v != n-1:
251 if i == t-1:
252 return False
253 else:
254 v, i = powMod(v, 2, n), i+1
255 a = getRandomNumber(2, n)
256 return True
257
259 if bits < 10:
260 raise AssertionError()
261
262
263
264
265
266 low = ((2 ** (bits-1)) * 3) // 2
267 high = 2 ** bits - 30
268 p = getRandomNumber(low, high)
269 p += 29 - (p % 30)
270 while 1:
271 if display: print(".", end=' ')
272 p += 30
273 if p >= high:
274 p = getRandomNumber(low, high)
275 p += 29 - (p % 30)
276 if isPrime(p, display=display):
277 return p
278
279
281 if bits < 10:
282 raise AssertionError()
283
284
285
286
287
288 low = (2 ** (bits-2)) * 3//2
289 high = (2 ** (bits-1)) - 30
290 q = getRandomNumber(low, high)
291 q += 29 - (q % 30)
292 while 1:
293 if display: print(".", end=' ')
294 q += 30
295 if (q >= high):
296 q = getRandomNumber(low, high)
297 q += 29 - (q % 30)
298
299
300 if isPrime(q, 0, display=display):
301 p = (2 * q) + 1
302 if isPrime(p, display=display):
303 if isPrime(q, display=display):
304 return p
305