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?