More separation of the code
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 @@
__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 @@
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} )
+
