Builtin pow function already performs efficient fast exponentiation modulo n

2 files changed, 10 insertions, 46 deletions

diff --git a/rsa/__init__.py b/rsa/__init__.py
index 6b66506..eef217f 100644
--- a/rsa/__init__.py
+++ b/rsa/__init__.py
@@ -166,24 +166,6 @@ def str642int(string):
 
     return integer
 
-
-def fast_exponentiation(a, e, n):
-    """Calculates r = a^e mod n
-    """
-    #Single loop version is faster and uses less memory
-    #MSB is always 1 so skip testing it and, start with next exponent bit.
-    msbe = bit_size(e) - 2      #Find MSB-1 of exponent
-    test = long(1 << msbe)      #Isolate each expoent bit with test value
-    a %= n                      #Throw away any overflow modulo n
-    result = a                  #Start with result = a (skip MSB test)
-    while test != 0:            #Repeat til all exponent bits have been tested
-        if e & test != 0:       #If exponent bit is 1, square and mult by a
-            result = (result * result * a) % n  #Then reduce modulo n
-        else:                   #If exponent bit is 0, just square
-            result = (result * result) % n      #Then reduce modulo n 
-        test >>= 1              #Move to next exponent bit
-    return result
-
 def read_random_int(nbits):
     """Reads a random integer of approximately nbits bits rounded up
     to whole bytes"""
@@ -238,7 +220,7 @@ def jacobi_witness(x, n):
     """
 
     j = jacobi(x, n) % n
-    f = fast_exponentiation(x, (n-1)/2, n)
+    f = pow(x, (n-1)/2, n)
 
     if j == f: return False
     return True
@@ -410,13 +392,13 @@ def encrypt_int(message, ekey, n):
     safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
     message += (1 << safebit)                   #add safebit to ensure folding
 
-    return fast_exponentiation(message, ekey, n)
+    return pow(message, ekey, n)
 
 def decrypt_int(cyphertext, dkey, n):
     """Decrypts a cypher text using the decryption key 'dkey', working
     modulo n"""
 
-    message = fast_exponentiation(cyphertext, dkey, n)
+    message = pow(cyphertext, dkey, n)
 
     safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
     message -= (1 << safebit)                   #remove safebit before decode
diff --git a/rsa/fastrsa.py b/rsa/fastrsa.py
index 3a26437..e9adab6 100644
--- a/rsa/fastrsa.py
+++ b/rsa/fastrsa.py
@@ -166,24 +166,6 @@ def str642int(string):
 
     return integer
 
-
-def fast_exponentiation(a, e, n):
-    """Calculates r = a^e mod n
-    """
-    #Single loop version is faster and uses less memory
-    #MSB is always 1 so skip testing it and start with next exponent bit.
-    msbe = bit_size(e) - 2      #Find MSB-1 of exponent
-    test = long(1 << msbe)      #Isolate each exponent bit with test value
-    a %= n                      #Throw away any overflow modulo n
-    result = a                  #Start with result = a (skip MSB test)
-    while test != 0:            #Repeat til all exponent bits have been tested
-        if e & test != 0:       #If exponent bit is 1, square and mult by a
-            result = (result * result * a) % n  #Then reduce modulo n
-        else:                   #If exponent bit is 0, just square
-            result = (result * result) % n      #Then reduce modulo n 
-        test >>= 1              #Move to next exponent bit
-    return result
-
 def read_random_int(nbits):
     """Reads a random integer of approximately nbits bits rounded up
     to whole bytes"""
@@ -238,7 +220,7 @@ def jacobi_witness(x, n):
     """
 
     j = jacobi(x, n) % n
-    f = fast_exponentiation(x, (n-1)/2, n)
+    f = pow(x, (n-1)/2, n)
 
     if j == f: return False
     return True
@@ -416,7 +398,7 @@ def encrypt_int(message, key):
     safebit = bit_size(n) - 2                   #safe bit is (MSB - 1)
     message += (1 << safebit)                   #add safebit to ensure folding
 
-    return fast_exponentiation(message, key['e'], key['n'])
+    return pow(message, key['e'], key['n'])
 
 def verify_int(cyphertext, key):
     """Decrypts cyphertext using public key 'key', working modulo n"""
@@ -427,7 +409,7 @@ def verify_int(cyphertext, key):
     if not type(cyphertext) is types.LongType:
         raise TypeError("You must pass a long or int")
 
-    message = fast_exponentiation(cyphertext, key['e'], key['n'])
+    message = pow(cyphertext, key['e'], key['n'])
 
     #Note: Bit exponents start at zero (bit counts start at 1) this is correct
     safebit = bit_size(n) - 2                   #safe bit is (MSB - 1)
@@ -442,8 +424,8 @@ def decrypt_int(cyphertext, key):
     q = key['q']
     n = p * q
     #Decrypt in 2 parts, using faster Chinese Remainder Theorem method
-    m1 = fast_exponentiation(cyphertext, key['dp'], p)
-    m2 = fast_exponentiation(cyphertext, key['dq'], q)
+    m1 = pow(cyphertext, key['dp'], p)
+    m2 = pow(cyphertext, key['dq'], q)
     dif = m1 - m2
     if dif < 0: dif += p
     h = (key['qi'] * dif) % p
@@ -475,8 +457,8 @@ def sign_int(message, key):
     message += (1 << safebit)                    #add safebit before encrypt
 
     #Encrypt in 2 parts, using faster Chinese Remainder Theorem method
-    c1 = fast_exponentiation(message, key['dp'], p)
-    c2 = fast_exponentiation(message, key['dq'], q)
+    c1 = pow(message, key['dp'], p)
+    c2 = pow(message, key['dq'], q)
     dif = c1 - c2
     if dif < 0: dif += p
     h = (key['qi'] * dif) % p