# Help with example RSA problem

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.

• I suspect the problem is with d. – Harvey Jun 21 '13 at 3:50
• Your $d$ is OK, even if you did not derive it using a standard method, like the extended Euclidian algorithm. I concur with poncho's answer. I tried with 5347 as an octal number, that does not work either. And that's not the intend here, which is just wrong. – fgrieu Jun 21 '13 at 3:59
• @fgrieu, poncho: [Sorry to put this here] Would either of you be available for some short term consulting? I need a simplistic crypto design reviewed. I tried e-mailing Françous at two googled e-mail addresses, but I'm not sure if I got them right. – Harvey Jun 21 '13 at 4:41
• @poncho: same question. I can't figure out if stack exchange supports private messages – Harvey Jun 21 '13 at 4:42
• Ah, no private messages for stack exchange – Harvey Jun 21 '13 at 4:50

$16657^5 \bmod 16781$