diff options
author | Barry Mead <barrymead@cox.net> | 2010-02-21 16:57:15 -0700 |
---|---|---|
committer | Barry Mead <barrymead@cox.net> | 2010-02-21 16:57:15 -0700 |
commit | 249324da95aa89f9a146837c02fd376e30f5c0b1 (patch) | |
tree | dad26295f538c9dea9fc334ee4d98c04b5650b4e /rsa/__init__.py | |
parent | 2005f503040beffee73957bdbbb4a767ea634284 (diff) | |
download | rsa-git-249324da95aa89f9a146837c02fd376e30f5c0b1.tar.gz |
Builtin pow function already performs efficient fast exponentiation modulo n
Diffstat (limited to 'rsa/__init__.py')
-rw-r--r-- | rsa/__init__.py | 24 |
1 files changed, 3 insertions, 21 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 |