diff options
author | Barry Mead <barrymead@cox.net> | 2010-02-19 17:02:30 -0700 |
---|---|---|
committer | Barry Mead <barrymead@cox.net> | 2010-02-19 17:02:30 -0700 |
commit | 945aeebafd384fd87c55e6b0ecba4b64b3cddd81 (patch) | |
tree | da2a8a5c7489ce7cee754335f0cae02ef60b40ff | |
parent | f5f1af2f8681262425dcaa6f247ae2ea46b13d03 (diff) | |
download | rsa-945aeebafd384fd87c55e6b0ecba4b64b3cddd81.tar.gz |
Reduce ditionary lookups in Chinese Remainder exponentiation
-rw-r--r-- | rsa/fastrsa.py | 29 |
1 files changed, 16 insertions, 13 deletions
diff --git a/rsa/fastrsa.py b/rsa/fastrsa.py index a8f2ab6..7f19d34 100644 --- a/rsa/fastrsa.py +++ b/rsa/fastrsa.py @@ -434,15 +434,16 @@ def verify_int(cyphertext, key): def decrypt_int(cyphertext, key): """Decrypts a cypher text using the private key 'key', working modulo n""" - - n = key['p'] * key['q'] + p = key['p'] #Reduce dictionary lookups + q = key['q'] + n = p * q #Decrypt in 2 parts, using faster Chinese Remainder Theorem method - m1 = fast_exponentiation(cyphertext, key['dp'], key['p']) - m2 = fast_exponentiation(cyphertext, key['dq'], key['q']) + m1 = fast_exponentiation(cyphertext, key['dp'], p) + m2 = fast_exponentiation(cyphertext, key['dq'], q) dif = m1 - m2 - if dif < 0: dif += key['p'] - h = (key['qi'] * dif) % key['p'] - message = m2 + (h * key['q']) + if dif < 0: dif += p + h = (key['qi'] * dif) % p + message = m2 + (h * q) safebit = int(math.floor(math.log(n,2))) - 1 #safe bit is (MSB - 1) message -= (1 << safebit) #remove safebit before decode @@ -459,7 +460,9 @@ def sign_int(message, key): if not type(message) is types.LongType: raise TypeError("You must pass a long or int") - n = key['p'] * key['q'] #computer n from p and q + p = key['p'] #Reduce dictionary lookups + q = key['q'] + n = p * q if message < 0 or message > n: raise OverflowError("The message is too long") @@ -468,12 +471,12 @@ 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'], key['p']) - c2 = fast_exponentiation(message, key['dq'], key['q']) + c1 = fast_exponentiation(message, key['dp'], p) + c2 = fast_exponentiation(message, key['dq'], q) dif = c1 - c2 - if dif < 0: dif += key['p'] - h = (key['qi'] * dif) % key['p'] - cyphertext = c2 + (h * key['q']) + if dif < 0: dif += p + h = (key['qi'] * dif) % p + cyphertext = c2 + (h * q) return cyphertext |