Lot of refactorings:

    - Added PKCS#1 module
    - Moved some functionality to common.py
    - simplified random number generation
    - improved and extended doctests
    - added changelog

7 files changed, 270 insertions, 60 deletions

diff --git a/CHANGELOG.txt b/CHANGELOG.txt
new file mode 100644
index 0000000..fd1bc73
--- /dev/null
+++ b/CHANGELOG.txt
@@ -0,0 +1,23 @@
+Python-RSA changelog
+========================================
+
+Version 2.1 - in development
+----------------------------------------
+
+- Changed the meaning of the keysize to mean the size of ``n`` rather than
+  the size of both ``p`` and ``q``. This is the common interpretation of
+  RSA keysize. To get the old behaviour, double the keysize when generating a
+  new key.
+  
+- Ensured that newkey(nbits) results in a ``n`` that can be stored in that many
+  bits (it used to overflow).
+
+- Including 'n' in the private key
+
+- Added a lot of doctests
+
+- Added random-padded encryption and decryption using PKCS#1 version 1.5
+
+
+Version 2.0
+----------------------------------------
diff --git a/rsa/common.py b/rsa/common.py
index b8f7aa6..7c852b6 100644
--- a/rsa/common.py
+++ b/rsa/common.py
@@ -14,5 +14,18 @@ def bit_size(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))
diff --git a/rsa/keygen.py b/rsa/keygen.py
index 66f2658..0ffe58d 100755
--- a/rsa/keygen.py
+++ b/rsa/keygen.py
@@ -36,10 +36,28 @@ def extended_gcd(a, b):
 
 
 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
+    ''''Returns a tuple of two different primes of nbits bits each.
+    
+    >>> (p, q) = find_p_q(128)
+    
+    The resulting p and q should be very close to 2*nbits bits, and no more
+    than 2*nbits bits:
+    >>> from rsa import common
+    >>> common.bit_size(p * q) <= 256
+    True
+    >>> common.bit_size(p * q) > 240
+    True
+    
+    '''
+    
+    # Make sure that p and q aren't too close or the factoring programs can
+    # factor n.
+    shift = nbits / 16
+    pbits = nbits + shift
+    qbits = nbits - shift
+    
     p = rsa.prime.getprime(pbits)
+    
     while True:
         q = rsa.prime.getprime(qbits)
 
@@ -64,7 +82,7 @@ def calculate_keys(p, q, nbits):
         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)
+    (d, i, _) = extended_gcd(e, phi_n)
 
     if not d == 1:
         raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
@@ -80,10 +98,13 @@ 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.
+    
+    @param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
+        ``q`` will use ``nbits/2`` bits.
     """
 
-    (p, q) = find_p_q(nbits)
-    (e, d) = calculate_keys(p, q, nbits)
+    (p, q) = find_p_q(nbits / 2)
+    (e, d) = calculate_keys(p, q, nbits / 2)
 
     return (p, q, e, d)
 
@@ -92,12 +113,31 @@ def newkeys(nbits):
     priv).
 
     The public key consists of a dict {e: ..., , n: ....). The private
-    key consists of a dict {d: ...., p: ...., q: ....).
+    key consists of a dict {d: ...., p: ...., q: ...., n: p*q).
+    
+    @param nbits: the number of bits required to store ``n = p*q``.
+    
     """
 
     # Don't let nbits go below 9 bits
     nbits = max(9, nbits)
     (p, q, e, d) = gen_keys(nbits)
+    
+    n = p * q
 
-    return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
+    return ( {'e': e, 'n': n}, {'d': d, 'p': p, 'q': q, 'n': n} )
 
+    
+if __name__ == '__main__':
+    print 'Running doctests 1000x or until failure'
+    import doctest
+    
+    for count in range(1000):
+        (failures, tests) = doctest.testmod()
+        if failures:
+            break
+        
+        if count and count % 100 == 0:
+            print '%i times' % count
+    
+    print 'Doctests done'
diff --git a/rsa/pkcs1.py b/rsa/pkcs1.py
new file mode 100644
index 0000000..58aa312
--- /dev/null
+++ b/rsa/pkcs1.py
@@ -0,0 +1,146 @@
+'''Functions for PKCS1 version 1.5
+
+This module implements certain functionality from PKCS1 version 1.5. For a
+very clear example, read http://www.di-mgt.com.au/rsa_alg.html#pkcs1schemes
+
+'''
+
+import os
+
+from rsa import common, transform, core
+
+def _pad_for_encryption(message, target_length):
+    r'''Pads the message for encryption, returning the padded message.
+    
+    @return: 00 02 RANDOM_DATA 00 MESSAGE
+    
+    >>> block = _pad_for_encryption('hello', 16)
+    >>> len(block)
+    16
+    >>> block[0:2]
+    '\x00\x02'
+    >>> block[-6:]
+    '\x00hello'
+
+    '''
+
+    max_msglength = target_length - 11
+    msglength = len(message)
+    
+    if msglength > max_msglength:
+        raise OverflowError('%i bytes needed for message, but there is only'
+            ' space for %i' % (msglength, max_msglength))
+    
+    # Get random padding
+    padding = ''
+    padding_length = target_length - msglength - 3
+    
+    # We remove 0-bytes, so we'll end up with less padding than we've asked for,
+    # so keep adding data until we're at the correct length.
+    while len(padding) < padding_length:
+        needed_bytes = padding_length - len(padding)
+        
+        # Always read at least 8 bytes more than we need, and trim off the rest
+        # after removing the 0-bytes. This increases the chance of getting
+        # enough bytes, especially when needed_bytes is small
+        new_padding = os.urandom(needed_bytes + 5)
+        new_padding = new_padding.replace('\x00', '')
+        padding = padding + new_padding[:needed_bytes]
+    
+    assert len(padding) == padding_length
+    
+    return ''.join(['\x00\x02',
+                    padding,
+                    '\x00',
+                    message])
+    
+    
+def encrypt(message, pub_key):
+    '''Encrypts the given message using PKCS1 v1.5
+    
+    @param message: the message to encrypt. Must be a byte string no longer than
+        ``k-11`` bytes, where ``k`` is the number of bytes needed to encode
+        the ``n`` component of the public key.
+    @param pub_key: the public key to encrypt with.
+    
+    @raise OverflowError: when the message is too large to fit in the padded
+        block.
+        
+    >>> from rsa import keygen, common
+    >>> (pub_key, priv_key) = keygen.newkeys(256)
+    >>> message = 'hello'
+    >>> crypto = encrypt(message, pub_key)
+    
+    The crypto text should be just as long as the public key 'n' component:
+    >>> len(crypto) == common.byte_size(pub_key['n'])
+    True
+    
+    '''
+    
+    keylength = common.byte_size(pub_key['n'])
+    padded = _pad_for_encryption(message, keylength)
+    
+    payload = transform.bytes2int(padded)
+    encrypted = core.encrypt_int(payload, pub_key['e'], pub_key['n'])
+    block = transform.int2bytes(encrypted, keylength)
+    
+    return block
+
+def decrypt(crypto, priv_key):
+    r'''Decrypts the given message using PKCS1 v1.5
+    
+    The decryption is considered 'failed' when the resulting cleartext doesn't
+    start with the bytes 00 02, or when the 00 byte between the padding and
+    the message cannot be found.
+    
+    @param crypto: the crypto text as returned by ``encrypt(message, pub_key)``
+    @param priv_key: the private key to decrypt with.
+    
+    @raise ValueError: when the decryption fails. No details are given as to why
+        the code thinks the decryption fails, as this would leak information
+        about the private key.
+
+    >>> from rsa import keygen, common
+    >>> (pub_key, priv_key) = keygen.newkeys(256)
+
+    It works with strings:
+    >>> decrypt(encrypt('hello', pub_key), priv_key)
+    'hello'
+    
+    And with binary data:
+    >>> decrypt(encrypt('\x00\x00\x00\x00\x01', pub_key), priv_key)
+    '\x00\x00\x00\x00\x01'
+    
+    '''
+    
+    blocksize = common.byte_size(priv_key['n']) 
+    encrypted = transform.bytes2int(crypto)
+    decrypted = core.decrypt_int(encrypted, priv_key['d'], priv_key['n'])
+    cleartext = transform.int2bytes(decrypted, blocksize)
+
+    # If we can't find the cleartext marker, decryption failed.
+    if cleartext[0:2] != '\x00\x02':
+        raise ValueError('Decryption failed')
+    
+    # Find the 00 separator between the padding and the message
+    try:
+        sep_idx = cleartext.index('\x00', 2)
+    except ValueError:
+        raise ValueError('Decryption failed')
+    
+    return cleartext[sep_idx+1:]
+    
+
+if __name__ == '__main__':
+    print 'Running doctests 1000x or until failure'
+    import doctest
+    
+    for count in range(1000):
+        (failures, tests) = doctest.testmod()
+        if failures:
+            break
+        
+        if count and count % 100 == 0:
+            print '%i times' % count
+    
+    print 'Doctests done'
diff --git a/rsa/prime.py b/rsa/prime.py
index 7cc06fb..048f830 100644
--- a/rsa/prime.py
+++ b/rsa/prime.py
@@ -58,7 +58,7 @@ def randomized_primality_testing(n, k):
     # 50% of Jacobi-witnesses can report compositness of non-prime numbers
 
     for i in range(k):
-        x = rsa.randnum.randint(1, n-1)
+        x = rsa.randnum.randint(n-1)
         if jacobi_witness(x, n): return False
     
     return True
@@ -81,16 +81,20 @@ def is_prime(number):
 
     
 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.
+    """Returns a prime number that can be stored in 'nbits' bits.
 
-    >>> p = getprime(8)
+    >>> p = getprime(128)
     >>> is_prime(p-1)
     0
     >>> is_prime(p)
     1
     >>> is_prime(p+1)
     0
+    
+    >>> from rsa import common
+    >>> common.bit_size(p) <= 128
+    True
+    
     """
 
     while True:
@@ -100,11 +104,11 @@ def getprime(nbits):
         integer |= 1
 
         # Test for primeness
-        if is_prime(integer): break
+        if is_prime(integer):
+            return integer
 
         # 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
@@ -118,3 +122,17 @@ def are_relatively_prime(a, b):
 
     d = gcd(a, b)
     return (d == 1)
+    
+if __name__ == '__main__':
+    print 'Running doctests 1000x or until failure'
+    import doctest
+    
+    for count in range(1000):
+        (failures, tests) = doctest.testmod()
+        if failures:
+            break
+        
+        if count and count % 100 == 0:
+            print '%i times' % count
+    
+    print 'Doctests done'
diff --git a/rsa/randnum.py b/rsa/randnum.py
index 9bfaded..1129a9b 100644
--- a/rsa/randnum.py
+++ b/rsa/randnum.py
@@ -1,38 +1,26 @@
 '''Functions for generating random numbers.'''
 
-import math
 import os
-import random
 
-import rsa.transform
+from rsa import common, transform
 
 def read_random_int(nbits):
-    """Reads a random integer of approximately nbits bits rounded up to whole
-    bytes
+    """Reads a random integer of approximately nbits bits.
+    
+    The number of bits is rounded down to whole bytes to ensure that the
+    resulting number can be stored in ``nbits`` bits.
     """
 
-    nbytes = int(math.ceil(nbits/8.))
-    randomdata = os.urandom(nbytes)
-    return rsa.transform.bytes2int(randomdata)
+    randomdata = os.urandom(nbits / 8)
+    return transform.bytes2int(randomdata)
+
+def randint(maxvalue):
+    """Returns a random integer x with 1 <= x <= maxvalue"""
 
-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
+    readbits = max(common.bit_size(maxvalue), 32)
 
-    # 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
+    return (read_random_int(readbits) % maxvalue) + 1
 
diff --git a/rsa/transform.py b/rsa/transform.py
index 076c385..3f151ad 100755
--- a/rsa/transform.py
+++ b/rsa/transform.py
@@ -3,27 +3,9 @@
 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"""
-
-    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))
+from rsa import common
 
 def bytes2int(bytes):
     """Converts a list of bytes or an 8-bit string to an integer.
@@ -86,7 +68,7 @@ def int2bytes(number, block_size=None):
 
     # Do some bounds checking
     if block_size is not None:
-        needed_bytes = byte_size(number)
+        needed_bytes = common.byte_size(number)
         if needed_bytes > block_size:
             raise OverflowError('Needed %i bytes for number, but block size '
                 'is %i' % (needed_bytes, block_size))
@@ -125,9 +107,9 @@ def block_op(block_provider, block_size, operation):
 
     for block in block_provider:
         number = bytes2int(block)
-        print 'In : %i (%i bytes)' % (number, byte_size(number))
+        print 'In : %i (%i bytes)' % (number, common.byte_size(number))
         after_op = operation(number)
-        print 'Out: %i (%i bytes)' % (after_op, byte_size(after_op))
+        print 'Out: %i (%i bytes)' % (after_op, common.byte_size(after_op))
         yield int2bytes(after_op, block_size)