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
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.