1
$\begingroup$

Like several previous askers, I seem to have made a mistake in my RSA calculation, but despite going back over it three times, I cannot spot it.

I picked 1000003 and 6000011 as my primes, p and q.

n = 1000003 * 6000011 = 6000029000033
z = φ(n) = (1000003 - 1) * (6000011 - 1) = 6000022000020
e = 17 (arbitrary pick of small integer that's coprime to z)

Public key is (e, n) = (17, 6000029000033)

Found d by solving (17 * e) mod z = (17 * d) % 6000022000020
d = 857146000003

d was calculated with an online multiplicative inverse calculator. I suspect this is where the error is, but I've redone it several times with different calculators to no avail.

So then I encrypted the number 6:

encryptedMessage = (message)^e mod n
encryptedMessage = (6)^17 mod 6000029000033
encryptedMessage = 4926601444670

Decryption is where I realized something must be wrong, because:

message = (encryptedMessage)^d mod n
message = 4926601444670 ^ 857146000003 mod 6000029000033

Except obviously that exponential operation is too huge to be done. I can't calculate it anywhere. It crashed my interpreter when I put it into python.

What am I doing wrong here?? :(

Or, perhaps, am I doing it right, and it's just that there's a necessary efficient method for this calculation which I'm not aware of?

Improve this question
$\endgroup$
5
  • $\begingroup$ Your $d$ is wrong, it doesn't satisfy $ed \equiv 1 \pmod{\mathrm{lcm}(p - 1, q - 1)}$. In fact it doesn't even satisfy the weaker (but sufficient) condition $ed \equiv 1 \pmod{\varphi(n)}$. A working $d$ for $e = 17$ is 4235309647073. What calculator did you use? $\endgroup$
    – Thomas
    May 1, 2016 at 3:30
  • $\begingroup$ For your second question about Python crashing, please see crypto.stackexchange.com/questions/13235/… $\endgroup$
    – Thomas
    May 1, 2016 at 3:31
  • $\begingroup$ I think I put the numbers in wrong....I must have. I don't know how....trying to retrace... $\endgroup$
    – temporary_user_name
    May 1, 2016 at 7:21
  • $\begingroup$ Yes, now they all give me the correct result as in Henno Brandsma's answer. I must have been using the wrong numbers somehow. I don't know what I typed in. Oh well. Thank you. $\endgroup$
    – temporary_user_name
    May 1, 2016 at 7:25
  • $\begingroup$ @Thomas : ​ Congruence mod $\phi(n)$ is a stronger condition than congruence mod the Lcm, since $\phi(n)$ is a multiple of the Lcm. ​ ​ ​ ​ $\endgroup$
    – user991
    May 1, 2016 at 18:34

2 Answers 2

Reset to default
2
$\begingroup$

Your $d$ is indeed incorrect. I get $d = 4235309647073$, using Wolfram alpha.

As to python, use the builtin pow function with a third argument equal to the modulus.

So

message = 6 encmessage = pow(message, 17, 6000029000033) assert message == pow(encmessage, 4235309647073, 6000029000033)

which will apply a smart algorithm like those in answers to this question. Never compute the direct power first!

Improve this answer
$\endgroup$
0
$\begingroup$
  1. $(e*d) \text{ mod } (\phi(n))=1$
  2. $(17*d) \text{ mod } 6000022000020=1$
  3. $d=4235309647073$.

I used WolframAlpha to compute d.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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