diff options
author | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-07-10 09:57:25 +0200 |
---|---|---|
committer | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-07-10 09:57:25 +0200 |
commit | 2cc58a8604facfb130579958466c2b71a5146cbd (patch) | |
tree | ba292e21a71935a328cd80d8044abc8b87228b62 | |
parent | 105f430bb8af76990c4c393d0e8b0a7d11429195 (diff) | |
download | rsa-git-2cc58a8604facfb130579958466c2b71a5146cbd.tar.gz |
Backed out changeset 812d745b6bef
-rwxr-xr-x | rsa-test.py | 5 | ||||
-rwxr-xr-x | rsa/__init__.py | 125 | ||||
-rwxr-xr-x | rsa/core.py | 17 | ||||
-rwxr-xr-x | rsa/transform.py | 132 |
4 files changed, 208 insertions, 71 deletions
diff --git a/rsa-test.py b/rsa-test.py index f48a234..94ea685 100755 --- a/rsa-test.py +++ b/rsa-test.py @@ -2,8 +2,7 @@ import rsa -keysize = 64 # bits -(pub, priv) = rsa.newkeys(keysize) +(pub, priv) = rsa.newkeys(64) print "Testing integer operations:" @@ -28,7 +27,7 @@ print "Testing string operations:" message = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" print "\tMessage: %s" % message -encrypted = rsa.encrypt(message, pub, 17) +encrypted = rsa.encrypt(message, pub) print "\tEncrypted: %s" % encrypted decrypted = rsa.decrypt(encrypted, priv) diff --git a/rsa/__init__.py b/rsa/__init__.py index 6c4981f..7fda4e1 100755 --- a/rsa/__init__.py +++ b/rsa/__init__.py @@ -13,62 +13,141 @@ __author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead" __date__ = "2010-02-08" __version__ = '2.1-beta0' -import functools - -from rsa import transform -from rsa import common +import rsa.prime +import rsa.transform +import rsa.common from rsa.keygen import newkeys from rsa.core import encrypt_int, decrypt_int -def get_blocks(message, block_size): - '''Generator, yields the blocks of the message.''' +def encode64chops(chops): + """base64encodes chops and combines them into a ',' delimited string""" + + # chips are character chops + chips = [rsa.transform.int2str64(chop) for chop in chops] + + # delimit chops with comma + encoded = ','.join(chips) + + return encoded + +def decode64chops(string): + """base64decodes and makes a ',' delimited string into chops""" + + # split chops at commas + chips = string.split(',') + + # make character chips into numeric chops + chops = [rsa.transform.str642int(chip) for chip in chips] + + return chops + +def block_size(n): + '''Returns the block size in bytes, given the public key. + + The block size is determined by the 'n=p*q' component of the key. + ''' + + # Set aside 2 bits so setting of safebit won't overflow modulo n. + nbits = rsa.common.bit_size(n) - 2 + nbytes = nbits / 8 + + return nbytes + + +def chopstring(message, key, n, int_op): + """Chops the 'message' into integers that fit into n. + Leaves room for a safebit to be added to ensure that all messages fold + during exponentiation. The MSB of the number n is not independent modulo n + (setting it could cause overflow), so use the next lower bit for the + safebit. Therefore this function reserves 2 bits in the number n for + non-data bits. + + Calls specified encryption function 'int_op' for each chop before storing. + + Used by 'encrypt' and 'sign'. + """ + + + nbytes = block_size(n) + msglen = len(message) - blocks = msglen / block_size + blocks = msglen / nbytes - if msglen % block_size > 0: + if msglen % nbytes > 0: blocks += 1 + cypher = [] + for bindex in range(blocks): - offset = bindex * block_size - yield message[offset:offset + block_size] + offset = bindex * nbytes + block = message[offset:offset + nbytes] -def encrypt(message, key, block_size): - """Encrypts a string 'message' with the public key 'key'""" - if 'n' not in key: - raise Exception("You must use the public key with encrypt") + value = rsa.transform.bytes2int(block) + to_store = int_op(value, key, n) + + cypher.append(to_store) + + 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. - op = functools.partial(encrypt_int, ekey=key['e'], n=key['n']) + Used by 'decrypt' and 'verify'. + """ - print 'E : %i (%i bytes)' % (key['e'], transform.byte_size(key['e'])) - print 'N : %i (%i bytes)' % (key['n'], transform.byte_size(key['n'])) + messageparts = [] + chops = decode64chops(string) #Decode base64 strings into integer chops - blocks = get_blocks(message, block_size) - crypto = list(transform.block_op(blocks, block_size, op)) + nbytes = block_size(n) + + for chop in chops: + value = funcref(chop, key, n) #Decrypt each chop + block = rsa.transform.int2bytes(value) + + # Pad block with 0-bytes until we have reached the block size + blocksize = len(block) + padsize = nbytes - blocksize + if padsize < 0: + raise ValueError('Block larger than block size (%i > %i)!' % + (blocksize, nbytes)) + elif padsize > 0: + block = '\x00' * padsize + block + + messageparts.append(block) + + # Combine decrypted strings into a msg + return ''.join(messageparts) + +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 ''.join(crypto) + 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) + 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) + 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) + return gluechops(cypher, key['e'], key['n'], decrypt_int) # Do doctest if we're not imported if __name__ == "__main__": diff --git a/rsa/core.py b/rsa/core.py index 639cba9..8f989df 100755 --- a/rsa/core.py +++ b/rsa/core.py @@ -17,16 +17,12 @@ def encrypt_int(message, ekey, n): if not type(message) is types.LongType: raise TypeError("You must pass a long or int") - if message < 0: - raise ValueError('Only non-negative numbers are supported') - - if message > n: - raise OverflowError("The message %i is too long for n=%i" % (message, n)) + if message < 0 or message > n: + raise OverflowError("The message is too long") - # TODO: reinstate safebit #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 + 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) @@ -36,9 +32,8 @@ def decrypt_int(cyphertext, dkey, n): message = pow(cyphertext, dkey, n) - # TODO: reinstate safebit - #safebit = rsa.common.bit_size(n) - 2 # compute safe bit (MSB - 1) - #message -= (1 << safebit) # remove safebit before decode + 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/transform.py b/rsa/transform.py index 4e0bb29..35b7461 100755 --- a/rsa/transform.py +++ b/rsa/transform.py @@ -9,22 +9,8 @@ import types def bit_size(number): """Returns the number of bits required to hold a specific long number""" - if number < 0: - raise ValueError('Only nonnegative numbers possible: %s' % number) - - if number == 0: - return 1 - return int(math.ceil(math.log(number, 2))) -def byte_size(number): - """Returns the number of bytes required to hold a specific long number. - - The number of bytes is rounded up. - """ - - return int(math.ceil(bit_size(number) / 8.0)) - def bytes2int(bytes): """Converts a list of bytes or an 8-bit string to an integer. @@ -41,7 +27,6 @@ def bytes2int(bytes): 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: @@ -87,7 +72,7 @@ def int2bytes(number, block_size=None): # Do some bounds checking if block_size is not None: - needed_bytes = byte_size(number) + needed_bytes = int(math.ceil(bit_size(number) / 8.0)) if needed_bytes > block_size: raise OverflowError('Needed %i bytes for number, but block size ' 'is %i' % (needed_bytes, block_size)) @@ -106,29 +91,108 @@ def int2bytes(number, block_size=None): return padding + ''.join(bytes) -def block_op(block_provider, block_size, operation): - r'''Generator, applies the operation on each block and yields the result + +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','-','_'. - Each block is converted to a number, the given operation is applied and then - the resulting number is converted back to a block of data. The resulting - block is yielded. + >>> 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. - @param block_provider: an iterable that iterates over the data blocks. - @param block_size: the used block size - @param operation: a function that accepts an integer and returns an integer + >>> 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','-','_'. - >>> blocks = ['\x00\x01\x02', '\x03\x04\x05'] - >>> list(block_op(blocks, 3, lambda x: (x + 6))) - ['\x00\x01\x08', '\x03\x04\x0b'] + >>> 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 - for block in block_provider: - number = bytes2int(block) - print 'In : %i (%i bytes)' % (number, byte_size(number)) - after_op = operation(number) - print 'Out: %i (%i bytes)' % (after_op, byte_size(after_op)) - yield int2bytes(after_op, block_size) if __name__ == '__main__': import doctest |