1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Maarten Bodewes Apr 12 at 15:19

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Being only almost certain that this is incorrect I suggest that you should study (extended) Euclid (once again). $\endgroup$ – DrLecter Oct 2 '14 at 21:01
  • 6
    $\begingroup$ 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. $\endgroup$ – Travis Mayberry Oct 2 '14 at 22:13
  • $\begingroup$ I suggest you using a bigint library to do the computation. Or try using Python, Pari/GP, Maple, Sage,... $\endgroup$ – ddddavidee Oct 3 '14 at 5:39
  • $\begingroup$ Sounds like you're using doubles instead of big integers. $\endgroup$ – CodesInChaos Oct 3 '14 at 20:28
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Apr 12 at 15:19
3
$\begingroup$

I have used the following python code to compute the private key 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 key is:

$522550976146069021499058157764354003336248628589338241039193114657$

The plaintext is:

$83678269879577658472958479799572658268$

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

$\endgroup$
  • $\begingroup$ Additional hint: watch for a striking regularity in the decimal expression of the plaintext. $\endgroup$ – fgrieu Oct 8 '14 at 8:03
  • 1
    $\begingroup$ This code might work for these input values, but it crashes with some other input values. $\endgroup$ – Atte Juvonen Apr 26 '17 at 21:26
  • 1
    $\begingroup$ ValueError: pow() 2nd argument cannot be negative when 3rd argument specified $\endgroup$ – Aaron Esau Mar 17 '18 at 6:27
0
$\begingroup$

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()
$\endgroup$
  • 1
    $\begingroup$ This is just a code dump without any explanation why you even altered the code. $\endgroup$ – Maarten Bodewes Apr 12 at 15:16
  • $\begingroup$ 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. $\endgroup$ – bananabr Apr 14 at 21:56
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Apr 15 at 11:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.