3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Konrad Rudolph Mar 19 at 9:55
13
\$\begingroup\$

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

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)

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ And of course, it's even faster not to have decrypt at all when all it does is call pow. \$\endgroup\$ – MSalters Mar 19 at 10:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Mar 19 at 16:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – SEJPM Mar 19 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.