RSA given q, p and e? [closed]

Question

I am given the q, p, and e values for an RSA key, along with an encrypted message.

Here are those values:

p                 = 1090660992520643446103273789680343  
q                 = 1162435056374824133712043309728653  
e                 = 65537  
sample ciphertext = 299604539773691895576847697095098784338054746292313044353582078965  

I tried calculating d with the Extended Euclidean algorithm, but came out as 1.9404359e+59, which I am almost certain is incorrect. How should I calculate d?

Answer 1

I used the following python code to compute the private exponent and perform decryption. It uses the extended euclidean algorithm:

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

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

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

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()

The private exponent is:

$522550976146069021499058157764354003336248628589338241039193114657$

The plaintext is:

$83678269879577658472958479799572658268$

which works out to a 128-bit value, so I'm assuming it's correct.

Answer 2

Here is a slightly modifed version of @user13741 answer.

import math

def getModInverse(a, m):
    if math.gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m

    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (
            u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

def main():

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

    # compute n
    n = p * q

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

    # Compute modular inverse of e
    d = getModInverse(e, phi)

    print("n:  " + str(d))

    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print("pt: " + str(pt))

if __name__ == "__main__":
    main()