diff options
-rwxr-xr-x | rsa/__init__.py | 328 | ||||
-rw-r--r-- | rsa/prime.py | 120 | ||||
-rw-r--r-- | rsa/randnum.py | 38 | ||||
-rw-r--r-- | rsa/transform.py | 152 |
4 files changed, 336 insertions, 302 deletions
diff --git a/rsa/__init__.py b/rsa/__init__.py index adf5fc8..e132989 100755 --- a/rsa/__init__.py +++ b/rsa/__init__.py @@ -11,311 +11,19 @@ Use with care. __author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead" __date__ = "2010-02-08" -__version__ = '2.0' +__version__ = '2.1-beta0' import math -import os -import random -import sys import types +import rsa.prime +import rsa.transform + 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 @@ -339,6 +47,21 @@ def extended_gcd(a, b): if (ly < 0): ly += oa #If neg wrap modulo orignal a return (a, lx, ly) #Return only positive values +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 = rsa.prime.getprime(pbits) + while True: + q = rsa.prime.getprime(qbits) + + #Make sure p and q are different. + if q != p: break + + return (p, q) + + + # 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 @@ -350,8 +73,9 @@ def calculate_keys(p, q, nbits): 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 + e = max(65537, rsa.prime.getprime(nbits/4)) + if rsa.prime.are_relatively_prime(e, n) and rsa.prime.are_relatively_prime(e, phi_n): + break (d, i, j) = extended_gcd(e, phi_n) @@ -423,7 +147,7 @@ def encode64chops(chops): chips = [] #chips are character chops for value in chops: - chips.append(int2str64(value)) + chips.append(rsa.transform.int2str64(value)) #delimit chops with comma encoded = ','.join(chips) @@ -438,7 +162,7 @@ def decode64chops(string): chops = [] for string in chips: #make char chops (chips) into chops - chops.append(str642int(string)) + chops.append(rsa.transform.str642int(string)) return chops @@ -469,7 +193,7 @@ def chopstring(message, key, n, funcref): for bindex in range(blocks): offset = bindex * nbytes block = message[offset:offset+nbytes] - value = bytes2int(block) + value = rsa.transform.bytes2int(block) cypher.append(funcref(value, key, n)) return encode64chops(cypher) #Encode encrypted ints to base64 strings @@ -486,7 +210,7 @@ def gluechops(string, key, n, funcref): for cpart in chops: mpart = funcref(cpart, key, n) #Decrypt each chop - message += int2bytes(mpart) #Combine decrypted strings into a msg + message += rsa.transform.int2bytes(mpart) #Combine decrypted strings into a msg return message diff --git a/rsa/prime.py b/rsa/prime.py new file mode 100644 index 0000000..7cc06fb --- /dev/null +++ b/rsa/prime.py @@ -0,0 +1,120 @@ +'''Numerical functions related to primes.''' + +__all__ = [ 'getprime', 'are_relatively_prime'] + +import rsa.randnum + +def gcd(p, q): + """Returns the greatest common divisor of p and q + + >>> gcd(48, 180) + 12 + """ + + while q != 0: + if p < q: (p,q) = (q,p) + (p,q) = (q, p % q) + return p + + +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 = rsa.randnum.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 = rsa.randnum.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) diff --git a/rsa/randnum.py b/rsa/randnum.py new file mode 100644 index 0000000..9bfaded --- /dev/null +++ b/rsa/randnum.py @@ -0,0 +1,38 @@ +'''Functions for generating random numbers.''' + +import math +import os +import random + +import rsa.transform + +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 rsa.transform.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 = (rsa.transform.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 + diff --git a/rsa/transform.py b/rsa/transform.py new file mode 100644 index 0000000..5e53d06 --- /dev/null +++ b/rsa/transform.py @@ -0,0 +1,152 @@ +'''Data transformation functions. + +From bytes to a number, number to bytes, base64-like-encoding, etc. +''' + +import math +import types + +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 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 |