# Where is the mistake in my RSA by-hand calculation?

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?

• 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? – Thomas May 1 '16 at 3:30
• For your second question about Python crashing, please see crypto.stackexchange.com/questions/13235/… – Thomas May 1 '16 at 3:31
• I think I put the numbers in wrong....I must have. I don't know how....trying to retrace... – temporary_user_name May 1 '16 at 7:21
• 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. – temporary_user_name May 1 '16 at 7:25
• @Thomas : ​ Congruence mod $\phi(n)$ is a stronger condition than congruence mod the Lcm, since $\phi(n)$ is a multiple of the Lcm. ​ ​ ​ ​ – 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.

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!

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

I used WolframAlpha to compute d.