# Naïve RSA decryption in Python

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

• You can trivially make the code simpler/shorter and also (minimally) more efficient by removing the unnecessary variable assignment. But of course this isn’t what your professor meant. – Konrad Rudolph Mar 19 at 9:55

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.

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

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)

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

• And of course, it's even faster not to have decrypt at all when all it does is call pow. – MSalters Mar 19 at 10:41
• Keeping decrypt would be a good idea. If you were actually implementing RSA, you would also want PKCS or something there, and the performance penalty of a func call will be small compared to the time to call pow. – Oscar Smith Mar 19 at 16:50
• Also note that pow probably doesn't exhibit timing independent of base and exponent ("constant-time") allowing for timing side-channel attacks which one may want / need to defend against. – SEJPM Mar 19 at 20:16