RSA Decryption using Extended Euclidean Algorithm

RSA is based on the great difficulty of integer factorization and is the most widely-used public-key cryptosystem used widely in e-commerce systems. Euclid algorithm and extended Euclid algorithm are the best algorithms to solve the public key and private key in RSA. Extended Euclid algorithm in IEEE P1363 is improved by eliminating the negative integer operation, which reduces the computing resources occupied by RSA and widely used in applications.

Decryption of RSA encrypted message in Python using extended euclidean algorithm when q, p and e values are given:

p = 1090660992520643446103273789680343
q = 1162435056374824133712043309728653
e = 65537
Cipher text = 299604539773691895576847697095098784338054746292313044353582078965

Python code to compute the private key and perform decryption using euclidean algorithm

#!/usr/bin/python 
import binascii

def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y

def main():

p = 1090660992520643446103273789680343
q = 1162435056374824133712043309728653
e = 65537
ct = 299604539773691895576847697095098784338054746292313044353582078965

# compute n
n = p * q

# Calulate phi phi(n)
phi = (p - 1) * (q - 1)

# Computation of modular inverse of e
gcd, a, b = egcd(e, phi)
d = a

print( "Private key: " + str(d) );

# Decryption of ciphertext
pt = pow(ct, d, n)
print( "The plaintext: " + str(pt) )

if __name__ == "__main__":
main()

Private key: 522550976146069021499058157764354003336248628589338241039193114657
The plaintext: 83678269879577658472958479799572658268