# RSA given q, p and e? [closed]

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?

• Being only almost certain that this is incorrect I suggest that you should study (extended) Euclid (once again). Commented Oct 2, 2014 at 21:01
• Since people are not being terribly helpful, I will say that you need to make sure you are using an arbitrary precision integer calculator when you do this kind of math. Scientific notation will not cut it, you need all the digits in order for it to work. Having said that, your decryption exponent is still not right. Remember that $e\cdot d = 1 \mod (p-1)(q-1)$, so it's easy to check if your answer is correct. Commented Oct 2, 2014 at 22:13
• I suggest you using a bigint library to do the computation. Or try using Python, Pari/GP, Maple, Sage,... Commented Oct 3, 2014 at 5:39
• Sounds like you're using doubles instead of big integers. Commented Oct 3, 2014 at 20:28
• I'm voting to close this question as off-topic because this is asking for an example on how to implement the Extended Euclidian algorithm. Code requests are off topic on Crypto.SE. Commented Apr 12, 2019 at 15:19

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.

• Additional hint: watch for a striking regularity in the decimal expression of the plaintext.
– fgrieu
Commented Oct 8, 2014 at 8:03
• This code might work for these input values, but it crashes with some other input values. Commented Apr 26, 2017 at 21:26
• ValueError: pow() 2nd argument cannot be negative when 3rd argument specified Commented Mar 17, 2018 at 6:27
• it requires python3.8+ Changed in version 3.8: For int operands, the three-argument form of pow now allows the second argument to be negative, permitting computation of modular inverses. Commented Feb 6, 2022 at 4:35

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()

• This is just a code dump without any explanation why you even altered the code. Commented Apr 12, 2019 at 15:16
• As previously stated, the version of @user13741 answer crashes on some valid user inputs. As far as my tests went this version handles all valid inputs properly. Commented Apr 14, 2019 at 21:56
• It is previously stated in a comment somewhere below another question. You need to explain this in your answer, provide a link to the previous answer (or even comment, right click on the time behind the comment to obtain the link) and of course indicate how your code solves the issue. This could be a very helpful contribution if well applied. Commented Apr 15, 2019 at 11:54
• I would recommend using a robust lib like gmpy2 for the modular inverse. phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) m = pow(c, d, n) Then print out m as hex and convert the hex bytes to ascii characters. Commented Mar 14, 2021 at 7:33