Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 4 down vote accepted

You don't appear to have done anything wrong; you can double check your result by computing:

$16657^5 \bmod 16781$

and find that it is indeed 5347; that is, 16657 is the number that, when encoded with the public key, results in the value you were given.

I suspect that moral of this story is that random examples on the internet might be worth just as much as you pay for them.

share|improve this answer
1  
What bothers me is that this example was lifted and used in other places as well including a kids crypto competition. –  Harvey Jun 21 '13 at 4:14
    
Also, the original link is cited in many places on the internet. I think most readers simply skip the exercise. –  Harvey Jun 21 '13 at 4:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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