I am making a code with basic RSA encryption/decryption. My professor wants me to speed up this function but it is already so simple and I am lost. Any ideas?
def decrypt(kenc,d,n): kdec=(kenc**d)%n return kdec
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It only takes a minute to sign up.Sign up to join this community
Simple does not mean fast, so you cannot judge performance based on how simple the implementation looks. Usually the most efficient way to perform a non-trivial task is not also the simplest way to do it. In this case though, there is a much more efficient solution that is about equally simple, and is probably sufficient.
There is a serious problem with this implementation: it computes
kenc**d is in general a very big number that takes a long time to compute, and then it takes a long time again to reduce it modulo
n. For example, trying it out with 1024bit RSA (the lowest setting!):
import Crypto from Crypto.PublicKey import RSA from Crypto import Random random_generator = Random.new().read key = RSA.generate(1024, random_generator) def decrypt(kenc,d,n): kdec=(kenc**d)%n return kdec (ciphertext,) = key.encrypt(42, 0) print(decrypt(ciphertext, key.d, key.n))
This does not finish in a reasonable time.
There is a simple remedy: use modular exponentiation, which keeps the size of the numbers that it is working with low throughout the whole calculation by reducing modulo
n as it goes along. You could implement it yourself, but Python handily provides a built-in function for this:
pow(x, e, n)
decrypt can be written as:
def decrypt(kenc, d, n): return pow(kenc, d, n)
With that change, the code above decodes the message quickly.
Further improvements are possible, but more complicated, and won't be drop-in replacements.