1
$\begingroup$

I am trying to implement RSA algorithm. I got a code in python. When I run it, it takes more than 10 minutes even when the primes are within 100 and message size is 8 decimal digits. Plese suggest what may be the problem in the code.

# Write Python3 code here 
from decimal import Decimal


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


p = int(input('Enter the value of p = '))
q = int(input('Enter the value of q = '))
no = int(input('Enter the value of text = '))
n = p * q
t = (p - 1) * (q - 1)

for e in range(2, t):
    if gcd(e, t) == 1:
        break

for i in range(1, 10):
    x = 1 + i * t
    if x % e == 0:
        d = int(x / e)
        break
print('pvt key= ', d)

ctt = Decimal(0)
ctt = pow(no, e)
ct = ctt % n

dtt = Decimal(0)
dtt = pow(ct, d)
dt = dtt % n

print('n = ' + str(n) + ' e = ' + str(e) + ' t = ' + str(t) + ' d = ' + str(d) + ' cipher text = ' + str(
    ct) + ' decrypted text = ' + str(dt))
$\endgroup$
  • $\begingroup$ What primes within 100 are selected? And what are the decimal digits of size 8. It seems impossible that it takes more than 10 minutes. $\endgroup$ – 孙海城 Jul 11 at 14:17
  • 1
    $\begingroup$ If p,q are less than 100 then n is less than 9999, and RSA does not work for messages >= n (or < 0). Also note the primes must be distinct or RSA doesn't work; see the basic definitions in wikipedia. $\endgroup$ – dave_thompson_085 Jul 12 at 1:18
6
$\begingroup$

What we've got here is a so-called naive implementation, which doesn't consider time complexity of power-then-modulo operations involving large integers. I'd recommend you to read up on square and multiply, exponentiation by squaring, binary exponentiation, for a bit of context. Typical naive implementations have O(2m) complexity, while optimised versions could achieve only O(m).

If you replace the commented-out code with the uncommented, you'll get significant execution speed improvements:

# ctt = pow(no, e)
# ct = ctt % n
ct = pow(no, e, n)
...
# dtt = pow(ct, d)
# dt = dtt % n
dt = pow(ct, d, n)

See Python built-in function docs for more details of what I've done.

Please note I did not verify reminder of your algorithm.

| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ The question's code already does multiplication by squaring (or similar), because two-argument pow does. What remains to be gained (which is, a lot) comes mostly from early modular reduction. Wikipedia has an article on modular exponentitaition. If one is really into making things as fast as they can be, there's R. Brent and P. Zimmermann's modern computer artihmetic. $\endgroup$ – fgrieu Jul 11 at 11:02
  • 1
    $\begingroup$ Your answer showed me path to go ahead. I felt that really efficient operation can reduce execution time drastically. Thank you very much for giving attention here. $\endgroup$ – DeoChandra Jul 11 at 13:29

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.