# 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#!/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