# 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). – DrLecter Oct 2 '14 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. – Travis Mayberry Oct 2 '14 at 22:13
• I suggest you using a bigint library to do the computation. Or try using Python, Pari/GP, Maple, Sage,... – ddddavidee Oct 3 '14 at 5:39
• Sounds like you're using doubles instead of big integers. – CodesInChaos Oct 3 '14 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. – Maarten Bodewes Apr 12 '19 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 Oct 8 '14 at 8:03
• This code might work for these input values, but it crashes with some other input values. – Atte Juvonen Apr 26 '17 at 21:26
• ValueError: pow() 2nd argument cannot be negative when 3rd argument specified – Aaron Esau Mar 17 '18 at 6:27

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. – Maarten Bodewes Apr 12 '19 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. – bananabr Apr 14 '19 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. – Maarten Bodewes Apr 15 '19 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. – Albert Veli Mar 14 at 7:33