While learning about RSA, I found this example problem. The answer is supposed to be "a 4-digit number that is a pattern of digits." I have computed it to be 16657 twice.
OK, now to see if you understand the RSA decryption algorithm, suppose you are person A, and you have chosen as your two primes $p = 97$ and $q = 173$, and you have chosen $e = 5$. Thus you told B that $N = 16781$ (which is just $pq$) and you told him that $e = 5$.
He encodes a message (a number) for you and tells you that the encoding is 5347. Can you figure out the original message? Hint--well, not really a hint, but a check of your final answer: it is a four-digit number that is a pattern of digits.
I have failed to decode this to a 4-digit number. What am I doing wrong?
p = 97
q = 173
N = 16781
dp = 16512 = (p-1)(q-1)
e = 5
d = ?
C = 5347
M = ?
I computed d = 6605 since that seems to be the smallest value of d possible for:
ed = 1(mod (p-1)(q-1))
5d = 1(mod 96 * 172)
5d = 1(mod 16512)
# I need a multiplier for 16512 that when added to 1 yields a number that
# ends in a 5 or a 0 so it will evenly divide by e=5
# 1 + 2 times dp will yield a number that ends in a 5
d = 6605
Now I need to compute M = C^d(mod N)
:
M = C^d(mod 16781)
5347^6605(mod 16781)
6605 = 4096 + 2048 + 256 + 128 + 64 + 8 + 4 + 1
5347^1 (mod 16781) = 5347
5347^2 (mod 16781) = 12366 (not included in final math)
5347^4 (mod 16781) = 9484
5347^8 (mod 16781) = 96
5347^64 (mod 16781) = 389
5347^128 (mod 16781) = 292
5347^256 (mod 16781) = 1359
5347^1024(mod 16781) = 3105
5347^2048(mod 16781) = 8731
5347^4096(mod 16781) = 11059
5347^6605(mod 16781) = 16657
I've also computed the same result in Excel by reproducing the same table above one power at a time for 6605 rows.
Update: It turns out to have been a mistake. The original author corrected the problem, but not before the error was copied across the internet.
d
. $\endgroup$ – Harvey Jun 21 '13 at 3:50