diff options
-rwxr-xr-x | rsa/__init__.py | 133 | ||||
-rw-r--r-- | rsa/common.py | 9 | ||||
-rw-r--r-- | rsa/core.py | 39 | ||||
-rw-r--r-- | rsa/keygen.py | 93 |
4 files changed, 147 insertions, 127 deletions
diff --git a/rsa/__init__.py b/rsa/__init__.py index 3aef6d8..5fc5768 100755 --- a/rsa/__init__.py +++ b/rsa/__init__.py @@ -1,7 +1,7 @@ """RSA module -Module for calculating large primes, and RSA encryption, decryption, -signing and verification. Includes generating public and private keys. +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. @@ -13,133 +13,12 @@ __author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead" __date__ = "2010-02-08" __version__ = '2.1-beta0' -import math -import types - import rsa.prime import rsa.transform +import rsa.common -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 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 - -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 - 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, 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) - - 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 +from rsa.keygen import newkeys +from rsa.core import encrypt_int, decrypt_int def encode64chops(chops): """base64encodes chops and combines them into a ',' delimited string""" @@ -186,7 +65,7 @@ def chopstring(message, key, n, int_op): 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 + nbits = rsa.common.bit_size(n) - 2 # leave room for safebit nbytes = nbits / 8 blocks = msglen / nbytes diff --git a/rsa/common.py b/rsa/common.py new file mode 100644 index 0000000..d00a44d --- /dev/null +++ b/rsa/common.py @@ -0,0 +1,9 @@ +'''Common functionality shared by several modules.''' + +import math + +def bit_size(number): + """Returns the number of bits required to hold a specific long number""" + + return int(math.ceil(math.log(number,2))) + diff --git a/rsa/core.py b/rsa/core.py new file mode 100644 index 0000000..f42801c --- /dev/null +++ b/rsa/core.py @@ -0,0 +1,39 @@ +'''Core mathematical operations. + +This is the actual core RSA implementation, which is only defined +mathematically on integers. +''' + +import types + +import rsa.common + +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 = rsa.common.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 = rsa.common.bit_size(n) - 2 #compute safe bit (MSB - 1) + message -= (1 << safebit) #remove safebit before decode + + return message + diff --git a/rsa/keygen.py b/rsa/keygen.py new file mode 100644 index 0000000..7a7cdb6 --- /dev/null +++ b/rsa/keygen.py @@ -0,0 +1,93 @@ +'''RSA key generation code.''' + +import rsa.prime + +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 + + + +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) + +def calculate_keys(p, q, nbits): + """Calculates an encryption and a decryption key given 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, 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) + + 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} ) + |