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