Package tlslite :: Package utils :: Module cryptomath
[hide private]
[frames] | no frames]

Source Code for Module tlslite.utils.cryptomath

  1  # Authors:  
  2  #   Trevor Perrin 
  3  #   Martin von Loewis - python 3 port 
  4  # 
  5  # See the LICENSE file for legal information regarding use of this file. 
  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  # Load Optional Modules 
 21  # ************************************************************************** 
 22   
 23  # Try to load M2Crypto/OpenSSL 
 24  try: 
 25      from M2Crypto import m2 
 26      m2cryptoLoaded = True 
 27   
 28  except ImportError: 
 29      m2cryptoLoaded = False 
 30   
 31  #Try to load GMPY 
 32  try: 
 33      import gmpy 
 34      gmpyLoaded = True 
 35  except ImportError: 
 36      gmpyLoaded = False 
 37   
 38  #Try to load pycrypto 
 39  try: 
 40      import Crypto.Cipher.AES 
 41      pycryptoLoaded = True 
 42  except ImportError: 
 43      pycryptoLoaded = False 
 44   
 45   
 46  # ************************************************************************** 
 47  # PRNG Functions 
 48  # ************************************************************************** 
 49   
 50  # Check that os.urandom works 
 51  import zlib 
 52  length = len(zlib.compress(os.urandom(1000))) 
 53  assert(length > 900) 
 54   
55 -def getRandomBytes(howMany):
56 b = bytearray(os.urandom(howMany)) 57 assert(len(b) == howMany) 58 return b
59 60 prngName = "os.urandom" 61 62 # ************************************************************************** 63 # Simple hash functions 64 # ************************************************************************** 65 66 import hmac 67 import hashlib 68
69 -def MD5(b):
70 return bytearray(hashlib.md5(compat26Str(b)).digest())
71
72 -def SHA1(b):
73 return bytearray(hashlib.sha1(compat26Str(b)).digest())
74
75 -def HMAC_MD5(k, b):
76 k = compatHMAC(k) 77 b = compatHMAC(b) 78 return bytearray(hmac.new(k, b, hashlib.md5).digest())
79
80 -def HMAC_SHA1(k, b):
81 k = compatHMAC(k) 82 b = compatHMAC(b) 83 return bytearray(hmac.new(k, b, hashlib.sha1).digest())
84 85 86 # ************************************************************************** 87 # Converter Functions 88 # ************************************************************************** 89
90 -def bytesToNumber(b):
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
99 -def numberToByteArray(n, howManyBytes=None):
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
114 -def mpiToNumber(mpi): #mpi is an openssl-format bignum string
115 if (ord(mpi[4]) & 0x80) !=0: #Make sure this is a positive number 116 raise AssertionError() 117 b = bytearray(mpi[4:]) 118 return bytesToNumber(b) 119
120 -def numberToMPI(n):
121 b = numberToByteArray(n) 122 ext = 0 123 #If the high-order bit is going to be set, 124 #add an extra byte of zeros 125 if (numBits(n) & 0x7)==0: 126 ext = 1 127 length = numBytes(n) + ext 128 b = bytearray(4+ext) + b 129 b[0] = (length >> 24) & 0xFF 130 b[1] = (length >> 16) & 0xFF 131 b[2] = (length >> 8) & 0xFF 132 b[3] = length & 0xFF 133 return bytes(b)
134 135 136 # ************************************************************************** 137 # Misc. Utility Functions 138 # ************************************************************************** 139
140 -def numBits(n):
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
152 -def numBytes(n):
153 if n==0: 154 return 0 155 bits = numBits(n) 156 return int(math.ceil(bits / 8.0))
157 158 # ************************************************************************** 159 # Big Number Math 160 # ************************************************************************** 161
162 -def getRandomNumber(low, high):
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
176 -def gcd(a,b):
177 a, b = max(a,b), min(a,b) 178 while b: 179 a, b = b, a % b 180 return a
181
182 -def lcm(a, b):
183 return (a * b) // gcd(a, b)
184 185 #Returns inverse of a mod b, zero if none 186 #Uses Extended Euclidean Algorithm
187 -def invMod(a, b):
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 #Pre-calculate a sieve of the ~100 primes < 1000:
217 -def makeSieve(n):
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 #Trial division with sieve 233 for x in sieve: 234 if x >= n: return True 235 if n % x == 0: return False 236 #Passed trial division, proceed to Rabin-Miller 237 #Rabin-Miller implemented per Ferguson & Schneier 238 #Compute s, t for Rabin-Miller 239 if display: print("*", end=' ') 240 s, t = n-1, 0 241 while s % 2 == 0: 242 s, t = s//2, t+1 243 #Repeat Rabin-Miller x times 244 a = 2 #Use 2 as a base for first iteration speedup, per HAC 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
258 -def getRandomPrime(bits, display=False):
259 if bits < 10: 260 raise AssertionError() 261 #The 1.5 ensures the 2 MSBs are set 262 #Thus, when used for p,q in RSA, n will have its MSB set 263 # 264 #Since 30 is lcm(2,3,5), we'll set our test numbers to 265 #29 % 30 and keep them there 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 #Unused at the moment...
280 -def getRandomSafePrime(bits, display=False):
281 if bits < 10: 282 raise AssertionError() 283 #The 1.5 ensures the 2 MSBs are set 284 #Thus, when used for p,q in RSA, n will have its MSB set 285 # 286 #Since 30 is lcm(2,3,5), we'll set our test numbers to 287 #29 % 30 and keep them there 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 #Ideas from Tom Wu's SRP code 299 #Do trial division on p and q before Rabin-Miller 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