text: #!/usr/bin/env python
  #
  # Electrum - lightweight Merge client
  # Copyright (C) 2015 Thomas Voegtlin
  #
  # Permission is hereby granted, free of charge, to any person
  # obtaining a copy of this software and associated documentation files
  # (the "Software"), to deal in the Software without restriction,
  # including without limitation the rights to use, copy, modify, merge,
  # publish, distribute, sublicense, and/or sell copies of the Software,
  # and to permit persons to whom the Software is furnished to do so,
  # subject to the following conditions:
  #
  # The above copyright notice and this permission notice shall be
  # included in all copies or substantial portions of the Software.
  #
  # 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.
  
  # This module uses functions from TLSLite (public domain)
  #
  # TLSLite Authors:
  #   Trevor Perrin
  #   Martin von Loewis - python 3 port
  #   Yngve Pettersen (ported by Paul Sokolovsky) - TLS 1.2
  #
  
  """Pure-Python RSA implementation."""
  
  import os
  import math
  import hashlib
  
  
  def SHA1(x):
      return hashlib.sha1(x).digest()
  
  
  # **************************************************************************
  # PRNG Functions
  # **************************************************************************
  
  # Check that os.urandom works
  import zlib
  length = len(zlib.compress(os.urandom(1000)))
  assert(length > 900)
  
  def getRandomBytes(howMany):
      b = bytearray(os.urandom(howMany))
      assert(len(b) == howMany)
      return b
  
  prngName = "os.urandom"
  
  
  # **************************************************************************
  # Converter Functions
  # **************************************************************************
  
  def bytesToNumber(b):
      total = 0
      multiplier = 1
      for count in range(len(b)-1, -1, -1):
          byte = b[count]
          total += multiplier * byte
          multiplier *= 256
      return total
  
  def numberToByteArray(n, howManyBytes=None):
      """Convert an integer into a bytearray, zero-pad to howManyBytes.
  
      The returned bytearray may be smaller than howManyBytes, but will
      not be larger.  The returned bytearray will contain a big-endian
      encoding of the input integer (n).
      """
      if howManyBytes == None:
          howManyBytes = numBytes(n)
      b = bytearray(howManyBytes)
      for count in range(howManyBytes-1, -1, -1):
          b[count] = int(n % 256)
          n >>= 8
      return b
  
  def mpiToNumber(mpi): #mpi is an openssl-format bignum string
      if (ord(mpi[4]) & 0x80) !=0: #Make sure this is a positive number
          raise AssertionError()
      b = bytearray(mpi[4:])
      return bytesToNumber(b)
  
  def numberToMPI(n):
      b = numberToByteArray(n)
      ext = 0
      #If the high-order bit is going to be set,
      #add an extra byte of zeros
      if (numBits(n) & 0x7)==0:
          ext = 1
      length = numBytes(n) + ext
      b = bytearray(4+ext) + b
      b[0] = (length >> 24) & 0xFF
      b[1] = (length >> 16) & 0xFF
      b[2] = (length >> 8) & 0xFF
      b[3] = length & 0xFF
      return bytes(b)
  
  
  # **************************************************************************
  # Misc. Utility Functions
  # **************************************************************************
  
  def numBits(n):
      if n==0:
          return 0
      s = "%x" % n
      return ((len(s)-1)*4) + \
      {'0':0, '1':1, '2':2, '3':2,
       '4':3, '5':3, '6':3, '7':3,
       '8':4, '9':4, 'a':4, 'b':4,
       'c':4, 'd':4, 'e':4, 'f':4,
       }[s[0]]
  
  def numBytes(n):
      if n==0:
          return 0
      bits = numBits(n)
      return int(math.ceil(bits / 8.0))
  
  # **************************************************************************
  # Big Number Math
  # **************************************************************************
  
  def getRandomNumber(low, high):
      if low >= high:
          raise AssertionError()
      howManyBits = numBits(high)
      howManyBytes = numBytes(high)
      lastBits = howManyBits % 8
      while 1:
          bytes = getRandomBytes(howManyBytes)
          if lastBits:
              bytes[0] = bytes[0] % (1 << lastBits)
          n = bytesToNumber(bytes)
          if n >= low and n < high:
              return n
  
  def gcd(a,b):
      a, b = max(a,b), min(a,b)
      while b:
          a, b = b, a % b
      return a
  
  def lcm(a, b):
      return (a * b) // gcd(a, b)
  
  #Returns inverse of a mod b, zero if none
  #Uses Extended Euclidean Algorithm
  def invMod(a, b):
      c, d = a, b
      uc, ud = 1, 0
      while c != 0:
          q = d // c
          c, d = d-(q*c), c
          uc, ud = ud - (q * uc), uc
      if d == 1:
          return ud % b
      return 0
  
  
  def powMod(base, power, modulus):
      if power < 0:
          result = pow(base, power*-1, modulus)
          result = invMod(result, modulus)
          return result
      else:
          return pow(base, power, modulus)
  
  #Pre-calculate a sieve of the ~100 primes < 1000:
  def makeSieve(n):
      sieve = list(range(n))
      for count in range(2, int(math.sqrt(n))+1):
          if sieve[count] == 0:
              continue
          x = sieve[count] * 2
          while x < len(sieve):
              sieve[x] = 0
              x += sieve[count]
      sieve = [x for x in sieve[2:] if x]
      return sieve
  
  sieve = makeSieve(1000)
  
  def isPrime(n, iterations=5, display=False):
      #Trial division with sieve
      for x in sieve:
          if x >= n: return True
          if n % x == 0: return False
      #Passed trial division, proceed to Rabin-Miller
      #Rabin-Miller implemented per Ferguson & Schneier
      #Compute s, t for Rabin-Miller
      if display: print("*", end=' ')
      s, t = n-1, 0
      while s % 2 == 0:
          s, t = s//2, t+1
      #Repeat Rabin-Miller x times
      a = 2 #Use 2 as a base for first iteration speedup, per HAC
      for count in range(iterations):
          v = powMod(a, s, n)
          if v==1:
              continue
          i = 0
          while v != n-1:
              if i == t-1:
                  return False
              else:
                  v, i = powMod(v, 2, n), i+1
          a = getRandomNumber(2, n)
      return True
  
  def getRandomPrime(bits, display=False):
      if bits < 10:
          raise AssertionError()
      #The 1.5 ensures the 2 MSBs are set
      #Thus, when used for p,q in RSA, n will have its MSB set
      #
      #Since 30 is lcm(2,3,5), we'll set our test numbers to
      #29 % 30 and keep them there
      low = ((2 ** (bits-1)) * 3) // 2
      high = 2 ** bits - 30
      p = getRandomNumber(low, high)
      p += 29 - (p % 30)
      while 1:
          if display: print(".", end=' ')
          p += 30
          if p >= high:
              p = getRandomNumber(low, high)
              p += 29 - (p % 30)
          if isPrime(p, display=display):
              return p
  
  #Unused at the moment...
  def getRandomSafePrime(bits, display=False):
      if bits < 10:
          raise AssertionError()
      #The 1.5 ensures the 2 MSBs are set
      #Thus, when used for p,q in RSA, n will have its MSB set
      #
      #Since 30 is lcm(2,3,5), we'll set our test numbers to
      #29 % 30 and keep them there
      low = (2 ** (bits-2)) * 3//2
      high = (2 ** (bits-1)) - 30
      q = getRandomNumber(low, high)
      q += 29 - (q % 30)
      while 1:
          if display: print(".", end=' ')
          q += 30
          if (q >= high):
              q = getRandomNumber(low, high)
              q += 29 - (q % 30)
          #Ideas from Tom Wu's SRP code
          #Do trial division on p and q before Rabin-Miller
          if isPrime(q, 0, display=display):
              p = (2 * q) + 1
              if isPrime(p, display=display):
                  if isPrime(q, display=display):
                      return p
  
  
  class RSAKey(object):
  
      def __init__(self, n=0, e=0, d=0, p=0, q=0, dP=0, dQ=0, qInv=0):
          if (n and not e) or (e and not n):
              raise AssertionError()
          self.n = n
          self.e = e
          self.d = d
          self.p = p
          self.q = q
          self.dP = dP
          self.dQ = dQ
          self.qInv = qInv
          self.blinder = 0
          self.unblinder = 0
  
      def __len__(self):
          """Return the length of this key in bits.
  
          @rtype: int
          """
          return numBits(self.n)
  
      def hasPrivateKey(self):
          return self.d != 0
  
      def hashAndSign(self, bytes):
          """Hash and sign the passed-in bytes.
  
          This requires the key to have a private component.  It performs
          a PKCS1-SHA1 signature on the passed-in data.
  
          @type bytes: str or L{bytearray} of unsigned bytes
          @param bytes: The value which will be hashed and signed.
  
          @rtype: L{bytearray} of unsigned bytes.
          @return: A PKCS1-SHA1 signature on the passed-in data.
          """
          hashBytes = SHA1(bytearray(bytes))
          prefixedHashBytes = self._addPKCS1SHA1Prefix(hashBytes)
          sigBytes = self.sign(prefixedHashBytes)
          return sigBytes
  
      def hashAndVerify(self, sigBytes, bytes):
          """Hash and verify the passed-in bytes with the signature.
  
          This verifies a PKCS1-SHA1 signature on the passed-in data.
  
          @type sigBytes: L{bytearray} of unsigned bytes
          @param sigBytes: A PKCS1-SHA1 signature.
  
          @type bytes: str or L{bytearray} of unsigned bytes
          @param bytes: The value which will be hashed and verified.
  
          @rtype: bool
          @return: Whether the signature matches the passed-in data.
          """
          hashBytes = SHA1(bytearray(bytes))
  
          # Try it with/without the embedded NULL
          prefixedHashBytes1 = self._addPKCS1SHA1Prefix(hashBytes, False)
          prefixedHashBytes2 = self._addPKCS1SHA1Prefix(hashBytes, True)
          result1 = self.verify(sigBytes, prefixedHashBytes1)
          result2 = self.verify(sigBytes, prefixedHashBytes2)
          return (result1 or result2)
  
      def sign(self, bytes):
          """Sign the passed-in bytes.
  
          This requires the key to have a private component.  It performs
          a PKCS1 signature on the passed-in data.
  
          @type bytes: L{bytearray} of unsigned bytes
          @param bytes: The value which will be signed.
  
          @rtype: L{bytearray} of unsigned bytes.
          @return: A PKCS1 signature on the passed-in data.
          """
          if not self.hasPrivateKey():
              raise AssertionError()
          paddedBytes = self._addPKCS1Padding(bytes, 1)
          m = bytesToNumber(paddedBytes)
          if m >= self.n:
              raise ValueError()
          c = self._rawPrivateKeyOp(m)
          sigBytes = numberToByteArray(c, numBytes(self.n))
          return sigBytes
  
      def verify(self, sigBytes, bytes):
          """Verify the passed-in bytes with the signature.
  
          This verifies a PKCS1 signature on the passed-in data.
  
          @type sigBytes: L{bytearray} of unsigned bytes
          @param sigBytes: A PKCS1 signature.
  
          @type bytes: L{bytearray} of unsigned bytes
          @param bytes: The value which will be verified.
  
          @rtype: bool
          @return: Whether the signature matches the passed-in data.
          """
          if len(sigBytes) != numBytes(self.n):
              return False
          paddedBytes = self._addPKCS1Padding(bytes, 1)
          c = bytesToNumber(sigBytes)
          if c >= self.n:
              return False
          m = self._rawPublicKeyOp(c)
          checkBytes = numberToByteArray(m, numBytes(self.n))
          return checkBytes == paddedBytes
  
      def encrypt(self, bytes):
          """Encrypt the passed-in bytes.
  
          This performs PKCS1 encryption of the passed-in data.
  
          @type bytes: L{bytearray} of unsigned bytes
          @param bytes: The value which will be encrypted.
  
          @rtype: L{bytearray} of unsigned bytes.
          @return: A PKCS1 encryption of the passed-in data.
          """
          paddedBytes = self._addPKCS1Padding(bytes, 2)
          m = bytesToNumber(paddedBytes)
          if m >= self.n:
              raise ValueError()
          c = self._rawPublicKeyOp(m)
          encBytes = numberToByteArray(c, numBytes(self.n))
          return encBytes
  
      def decrypt(self, encBytes):
          """Decrypt the passed-in bytes.
  
          This requires the key to have a private component.  It performs
          PKCS1 decryption of the passed-in data.
  
          @type encBytes: L{bytearray} of unsigned bytes
          @param encBytes: The value which will be decrypted.
  
          @rtype: L{bytearray} of unsigned bytes or None.
          @return: A PKCS1 decryption of the passed-in data or None if
          the data is not properly formatted.
          """
          if not self.hasPrivateKey():
              raise AssertionError()
          if len(encBytes) != numBytes(self.n):
              return None
          c = bytesToNumber(encBytes)
          if c >= self.n:
              return None
          m = self._rawPrivateKeyOp(c)
          decBytes = numberToByteArray(m, numBytes(self.n))
          #Check first two bytes
          if decBytes[0] != 0 or decBytes[1] != 2:
              return None
          #Scan through for zero separator
          for x in range(1, len(decBytes)-1):
              if decBytes[x]== 0:
                  break
          else:
              return None
          return decBytes[x+1:] #Return everything after the separator
  
  
  
  
      # **************************************************************************
      # Helper Functions for RSA Keys
      # **************************************************************************
  
      def _addPKCS1SHA1Prefix(self, bytes, withNULL=True):
          # There is a long history of confusion over whether the SHA1
          # algorithmIdentifier should be encoded with a NULL parameter or
          # with the parameter omitted.  While the original intention was
          # apparently to omit it, many toolkits went the other way.  TLS 1.2
          # specifies the NULL should be included, and this behavior is also
          # mandated in recent versions of PKCS #1, and is what tlslite has
          # always implemented.  Anyways, verification code should probably
          # accept both.  However, nothing uses this code yet, so this is
          # all fairly moot.
          if not withNULL:
              prefixBytes = bytearray(\
              [0x30,0x1f,0x30,0x07,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x04,0x14])
          else:
              prefixBytes = bytearray(\
              [0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14])
          prefixedBytes = prefixBytes + bytes
          return prefixedBytes
  
      def _addPKCS1Padding(self, bytes, blockType):
          padLength = (numBytes(self.n) - (len(bytes)+3))
          if blockType == 1: #Signature padding
              pad = [0xFF] * padLength
          elif blockType == 2: #Encryption padding
              pad = bytearray(0)
              while len(pad) < padLength:
                  padBytes = getRandomBytes(padLength * 2)
                  pad = [b for b in padBytes if b != 0]
                  pad = pad[:padLength]
          else:
              raise AssertionError()
  
          padding = bytearray([0,blockType] + pad + [0])
          paddedBytes = padding + bytes
          return paddedBytes
  
  
  
  
      def _rawPrivateKeyOp(self, m):
          #Create blinding values, on the first pass:
          if not self.blinder:
              self.unblinder = getRandomNumber(2, self.n)
              self.blinder = powMod(invMod(self.unblinder, self.n), self.e,
                                    self.n)
  
          #Blind the input
          m = (m * self.blinder) % self.n
  
          #Perform the RSA operation
          c = self._rawPrivateKeyOpHelper(m)
  
          #Unblind the output
          c = (c * self.unblinder) % self.n
  
          #Update blinding values
          self.blinder = (self.blinder * self.blinder) % self.n
          self.unblinder = (self.unblinder * self.unblinder) % self.n
  
          #Return the output
          return c
  
  
      def _rawPrivateKeyOpHelper(self, m):
          #Non-CRT version
          #c = powMod(m, self.d, self.n)
  
          #CRT version  (~3x faster)
          s1 = powMod(m, self.dP, self.p)
          s2 = powMod(m, self.dQ, self.q)
          h = ((s1 - s2) * self.qInv) % self.p
          c = s2 + self.q * h
          return c
  
      def _rawPublicKeyOp(self, c):
          m = powMod(c, self.e, self.n)
          return m
  
      def acceptsPassword(self):
          return False
  
      def generate(bits):
          key = RSAKey()
          p = getRandomPrime(bits//2, False)
          q = getRandomPrime(bits//2, False)
          t = lcm(p-1, q-1)
          key.n = p * q
          key.e = 65537
          key.d = invMod(key.e, t)
          key.p = p
          key.q = q
          key.dP = key.d % (p-1)
          key.dQ = key.d % (q-1)
          key.qInv = invMod(q, p)
          return key
      generate = staticmethod(generate)
  