--- /dev/null
+"""RSA module
+
+Module for calculating large primes, and RSA encryption, decryption,
+signing and verification. Includes generating public and private keys.
+
+WARNING: this implementation does not use random padding, compression of the
+cleartext input to prevent repetitions, or other common security improvements.
+Use with care.
+
+"""
+
+__author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead"
+__date__ = "2010-02-08"
+__version__ = '2.0'
+
+import math
+import os
+import random
+import sys
+import types
+
+# Display a warning that this insecure version is imported.
+import warnings
+warnings.warn('Insecure version of the RSA module is imported as %s' % __name__)
+
+
+def bit_size(number):
+ """Returns the number of bits required to hold a specific long number"""
+
+ return int(math.ceil(math.log(number,2)))
+
+def gcd(p, q):
+ """Returns the greatest common divisor of p and q
+ >>> gcd(48, 180)
+ 12
+ """
+ # Iterateive Version is faster and uses much less stack space
+ while q != 0:
+ if p < q: (p,q) = (q,p)
+ (p,q) = (q, p % q)
+ return p
+
+
+def bytes2int(bytes):
+ """Converts a list of bytes or a string to an integer
+
+ >>> (((128 * 256) + 64) * 256) + 15
+ 8405007
+ >>> l = [128, 64, 15]
+ >>> bytes2int(l) #same as bytes2int('\x80@\x0f')
+ 8405007
+ """
+
+ if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
+ raise TypeError("You must pass a string or a list")
+
+ # Convert byte stream to integer
+ integer = 0
+ for byte in bytes:
+ integer *= 256
+ if type(byte) is types.StringType: byte = ord(byte)
+ integer += byte
+
+ return integer
+
+def int2bytes(number):
+ """Converts a number to a string of bytes
+
+ >>>int2bytes(123456789)
+ '\x07[\xcd\x15'
+ >>> bytes2int(int2bytes(123456789))
+ 123456789
+ """
+
+ if not (type(number) is types.LongType or type(number) is types.IntType):
+ raise TypeError("You must pass a long or an int")
+
+ string = ""
+
+ while number > 0:
+ string = "%s%s" % (chr(number & 0xFF), string)
+ number /= 256
+
+ return string
+
+def to64(number):
+ """Converts a number in the range of 0 to 63 into base 64 digit
+ character in the range of '0'-'9', 'A'-'Z', 'a'-'z','-','_'.
+
+ >>> to64(10)
+ 'A'
+ """
+
+ if not (type(number) is types.LongType or type(number) is types.IntType):
+ raise TypeError("You must pass a long or an int")
+
+ if 0 <= number <= 9: #00-09 translates to '0' - '9'
+ return chr(number + 48)
+
+ if 10 <= number <= 35:
+ return chr(number + 55) #10-35 translates to 'A' - 'Z'
+
+ if 36 <= number <= 61:
+ return chr(number + 61) #36-61 translates to 'a' - 'z'
+
+ if number == 62: # 62 translates to '-' (minus)
+ return chr(45)
+
+ if number == 63: # 63 translates to '_' (underscore)
+ return chr(95)
+
+ raise ValueError(u'Invalid Base64 value: %i' % number)
+
+
+def from64(number):
+ """Converts an ordinal character value in the range of
+ 0-9,A-Z,a-z,-,_ to a number in the range of 0-63.
+
+ >>> from64(49)
+ 1
+ """
+
+ if not (type(number) is types.LongType or type(number) is types.IntType):
+ raise TypeError("You must pass a long or an int")
+
+ if 48 <= number <= 57: #ord('0') - ord('9') translates to 0-9
+ return(number - 48)
+
+ if 65 <= number <= 90: #ord('A') - ord('Z') translates to 10-35
+ return(number - 55)
+
+ if 97 <= number <= 122: #ord('a') - ord('z') translates to 36-61
+ return(number - 61)
+
+ if number == 45: #ord('-') translates to 62
+ return(62)
+
+ if number == 95: #ord('_') translates to 63
+ return(63)
+
+ raise ValueError(u'Invalid Base64 value: %i' % number)
+
+
+def int2str64(number):
+ """Converts a number to a string of base64 encoded characters in
+ the range of '0'-'9','A'-'Z,'a'-'z','-','_'.
+
+ >>> int2str64(123456789)
+ '7MyqL'
+ """
+
+ if not (type(number) is types.LongType or type(number) is types.IntType):
+ raise TypeError("You must pass a long or an int")
+
+ string = ""
+
+ while number > 0:
+ string = "%s%s" % (to64(number & 0x3F), string)
+ number /= 64
+
+ return string
+
+
+def str642int(string):
+ """Converts a base64 encoded string into an integer.
+ The chars of this string in in the range '0'-'9','A'-'Z','a'-'z','-','_'
+
+ >>> str642int('7MyqL')
+ 123456789
+ """
+
+ if not (type(string) is types.ListType or type(string) is types.StringType):
+ raise TypeError("You must pass a string or a list")
+
+ integer = 0
+ for byte in string:
+ integer *= 64
+ if type(byte) is types.StringType: byte = ord(byte)
+ integer += from64(byte)
+
+ return integer
+
+def read_random_int(nbits):
+ """Reads a random integer of approximately nbits bits rounded up
+ to whole bytes"""
+
+ nbytes = int(math.ceil(nbits/8.))
+ randomdata = os.urandom(nbytes)
+ return bytes2int(randomdata)
+
+def randint(minvalue, maxvalue):
+ """Returns a random integer x with minvalue <= x <= maxvalue"""
+
+ # Safety - get a lot of random data even if the range is fairly
+ # small
+ min_nbits = 32
+
+ # The range of the random numbers we need to generate
+ range = (maxvalue - minvalue) + 1
+
+ # Which is this number of bytes
+ rangebytes = ((bit_size(range) + 7) / 8)
+
+ # Convert to bits, but make sure it's always at least min_nbits*2
+ rangebits = max(rangebytes * 8, min_nbits * 2)
+
+ # Take a random number of bits between min_nbits and rangebits
+ nbits = random.randint(min_nbits, rangebits)
+
+ return (read_random_int(nbits) % range) + minvalue
+
+def jacobi(a, b):
+ """Calculates the value of the Jacobi symbol (a/b)
+ where both a and b are positive integers, and b is odd
+ """
+
+ if a == 0: return 0
+ result = 1
+ while a > 1:
+ if a & 1:
+ if ((a-1)*(b-1) >> 2) & 1:
+ result = -result
+ a, b = b % a, a
+ else:
+ if (((b * b) - 1) >> 3) & 1:
+ result = -result
+ a >>= 1
+ if a == 0: return 0
+ return result
+
+def jacobi_witness(x, n):
+ """Returns False if n is an Euler pseudo-prime with base x, and
+ True otherwise.
+ """
+
+ j = jacobi(x, n) % n
+ f = pow(x, (n-1)/2, n)
+
+ if j == f: return False
+ return True
+
+def randomized_primality_testing(n, k):
+ """Calculates whether n is composite (which is always correct) or
+ prime (which is incorrect with error probability 2**-k)
+
+ Returns False if the number is composite, and True if it's
+ probably prime.
+ """
+
+ # 50% of Jacobi-witnesses can report compositness of non-prime numbers
+
+ for i in range(k):
+ x = randint(1, n-1)
+ if jacobi_witness(x, n): return False
+
+ return True
+
+def is_prime(number):
+ """Returns True if the number is prime, and False otherwise.
+
+ >>> is_prime(42)
+ 0
+ >>> is_prime(41)
+ 1
+ """
+
+ if randomized_primality_testing(number, 6):
+ # Prime, according to Jacobi
+ return True
+
+ # Not prime
+ return False
+
+
+def getprime(nbits):
+ """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
+ other words: nbits is rounded up to whole bytes.
+
+ >>> p = getprime(8)
+ >>> is_prime(p-1)
+ 0
+ >>> is_prime(p)
+ 1
+ >>> is_prime(p+1)
+ 0
+ """
+
+ while True:
+ integer = read_random_int(nbits)
+
+ # Make sure it's odd
+ integer |= 1
+
+ # Test for primeness
+ if is_prime(integer): break
+
+ # Retry if not prime
+
+ return integer
+
+def are_relatively_prime(a, b):
+ """Returns True if a and b are relatively prime, and False if they
+ are not.
+
+ >>> are_relatively_prime(2, 3)
+ 1
+ >>> are_relatively_prime(2, 4)
+ 0
+ """
+
+ d = gcd(a, b)
+ return (d == 1)
+
+def find_p_q(nbits):
+ """Returns a tuple of two different primes of nbits bits"""
+ pbits = nbits + (nbits/16) #Make sure that p and q aren't too close
+ qbits = nbits - (nbits/16) #or the factoring programs can factor n
+ p = getprime(pbits)
+ while True:
+ q = getprime(qbits)
+ #Make sure p and q are different.
+ if not q == p: break
+ return (p, q)
+
+def extended_gcd(a, b):
+ """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
+ """
+ # r = gcd(a,b) i = multiplicitive inverse of a mod b
+ # or j = multiplicitive inverse of b mod a
+ # Neg return values for i or j are made positive mod b or a respectively
+ # Iterateive Version is faster and uses much less stack space
+ x = 0
+ y = 1
+ lx = 1
+ ly = 0
+ oa = a #Remember original a/b to remove
+ ob = b #negative values from return results
+ while b != 0:
+ q = long(a/b)
+ (a, b) = (b, a % b)
+ (x, lx) = ((lx - (q * x)),x)
+ (y, ly) = ((ly - (q * y)),y)
+ if (lx < 0): lx += ob #If neg wrap modulo orignal b
+ if (ly < 0): ly += oa #If neg wrap modulo orignal a
+ return (a, lx, ly) #Return only positive values
+
+# Main function: calculate encryption and decryption keys
+def calculate_keys(p, q, nbits):
+ """Calculates an encryption and a decryption key for p and q, and
+ returns them as a tuple (e, d)"""
+
+ n = p * q
+ phi_n = (p-1) * (q-1)
+
+ while True:
+ # Make sure e has enough bits so we ensure "wrapping" through
+ # modulo n
+ e = max(65537,getprime(nbits/4))
+ if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break
+
+ (d, i, j) = extended_gcd(e, phi_n)
+
+ if not d == 1:
+ raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
+ if (i < 0):
+ raise Exception("New extended_gcd shouldn't return negative values")
+ if not (e * i) % phi_n == 1:
+ raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))
+
+ return (e, i)
+
+
+def gen_keys(nbits):
+ """Generate RSA keys of nbits bits. Returns (p, q, e, d).
+
+ Note: this can take a long time, depending on the key size.
+ """
+
+ (p, q) = find_p_q(nbits)
+ (e, d) = calculate_keys(p, q, nbits)
+
+ return (p, q, e, d)
+
+def newkeys(nbits):
+ """Generates public and private keys, and returns them as (pub,
+ priv).
+
+ The public key consists of a dict {e: ..., , n: ....). The private
+ key consists of a dict {d: ...., p: ...., q: ....).
+ """
+ nbits = max(9,nbits) # Don't let nbits go below 9 bits
+ (p, q, e, d) = gen_keys(nbits)
+
+ return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
+
+def encrypt_int(message, ekey, n):
+ """Encrypts a message using encryption key 'ekey', working modulo n"""
+
+ if type(message) is types.IntType:
+ message = long(message)
+
+ if not type(message) is types.LongType:
+ raise TypeError("You must pass a long or int")
+
+ if message < 0 or message > n:
+ raise OverflowError("The message is too long")
+
+ #Note: Bit exponents start at zero (bit counts start at 1) this is correct
+ safebit = bit_size(n) - 2 #compute safe bit (MSB - 1)
+ message += (1 << safebit) #add safebit to ensure folding
+
+ return pow(message, ekey, n)
+
+def decrypt_int(cyphertext, dkey, n):
+ """Decrypts a cypher text using the decryption key 'dkey', working
+ modulo n"""
+
+ message = pow(cyphertext, dkey, n)
+
+ safebit = bit_size(n) - 2 #compute safe bit (MSB - 1)
+ message -= (1 << safebit) #remove safebit before decode
+
+ return message
+
+def encode64chops(chops):
+ """base64encodes chops and combines them into a ',' delimited string"""
+
+ chips = [] #chips are character chops
+
+ for value in chops:
+ chips.append(int2str64(value))
+
+ #delimit chops with comma
+ encoded = ','.join(chips)
+
+ return encoded
+
+def decode64chops(string):
+ """base64decodes and makes a ',' delimited string into chops"""
+
+ chips = string.split(',') #split chops at commas
+
+ chops = []
+
+ for string in chips: #make char chops (chips) into chops
+ chops.append(str642int(string))
+
+ return chops
+
+def chopstring(message, key, n, funcref):
+ """Chops the 'message' into integers that fit into n,
+ leaving room for a safebit to be added to ensure that all
+ messages fold during exponentiation. The MSB of the number n
+ is not independant modulo n (setting it could cause overflow), so
+ use the next lower bit for the safebit. Therefore reserve 2-bits
+ in the number n for non-data bits. Calls specified encryption
+ function for each chop.
+
+ Used by 'encrypt' and 'sign'.
+ """
+
+ msglen = len(message)
+ mbits = msglen * 8
+ #Set aside 2-bits so setting of safebit won't overflow modulo n.
+ nbits = bit_size(n) - 2 # leave room for safebit
+ nbytes = nbits / 8
+ blocks = msglen / nbytes
+
+ if msglen % nbytes > 0:
+ blocks += 1
+
+ cypher = []
+
+ for bindex in range(blocks):
+ offset = bindex * nbytes
+ block = message[offset:offset+nbytes]
+ value = bytes2int(block)
+ cypher.append(funcref(value, key, n))
+
+ return encode64chops(cypher) #Encode encrypted ints to base64 strings
+
+def gluechops(string, key, n, funcref):
+ """Glues chops back together into a string. calls
+ funcref(integer, key, n) for each chop.
+
+ Used by 'decrypt' and 'verify'.
+ """
+ message = ""
+
+ chops = decode64chops(string) #Decode base64 strings into integer chops
+
+ for cpart in chops:
+ mpart = funcref(cpart, key, n) #Decrypt each chop
+ message += int2bytes(mpart) #Combine decrypted strings into a msg
+
+ return message
+
+def encrypt(message, key):
+ """Encrypts a string 'message' with the public key 'key'"""
+ if 'n' not in key:
+ raise Exception("You must use the public key with encrypt")
+
+ return chopstring(message, key['e'], key['n'], encrypt_int)
+
+def sign(message, key):
+ """Signs a string 'message' with the private key 'key'"""
+ if 'p' not in key:
+ raise Exception("You must use the private key with sign")
+
+ return chopstring(message, key['d'], key['p']*key['q'], encrypt_int)
+
+def decrypt(cypher, key):
+ """Decrypts a string 'cypher' with the private key 'key'"""
+ if 'p' not in key:
+ raise Exception("You must use the private key with decrypt")
+
+ return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)
+
+def verify(cypher, key):
+ """Verifies a string 'cypher' with the public key 'key'"""
+ if 'n' not in key:
+ raise Exception("You must use the public key with verify")
+
+ return gluechops(cypher, key['e'], key['n'], decrypt_int)
+
+# Do doctest if we're not imported
+if __name__ == "__main__":
+ import doctest
+ doctest.testmod()
+
+__all__ = ["newkeys", "encrypt", "decrypt", "sign", "verify"]
+
projects / NK2015_Client_Python_Alpha.git / blobdiff