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?

  • $\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 '16 at 3:30
  • $\begingroup$ For your second question about Python crashing, please see crypto.stackexchange.com/questions/13235/… $\endgroup$
    – Thomas
    May 1 '16 at 3:31
  • $\begingroup$ I think I put the numbers in wrong....I must have. I don't know how....trying to retrace... $\endgroup$ May 1 '16 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$ May 1 '16 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 '16 at 18:34

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.


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!

  1. $(e*d) \text{ mod } (\phi(n))=1$
  2. $(17*d) \text{ mod } 6000022000020=1$
  3. $d=4235309647073$.

I used WolframAlpha to compute d.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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