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.

I tried out the paper/pencil explanation @ http://sergematovic.tripod.com/rsa1.html, and it seemed to make sense just fine until I came to decryption. Here is what I worked out:

Key Creation:

Choose two different prime numbers p and k:

p = 23
k = 29

Find n by calculating p * q:

n = 23 * 29
n = 667

Find z by calculating (p - 1) * (q - 1):

z = (23 - 1) * (29 - 1)
z = 22 * 28
z = 616

Pick a number k that is coprime to z:

616 % 2 != 0
616 % 3  = 0
k = 3

The public key consists of n and k:

Public Key:
n = 667
k = 3

Find a number j where (k * j) % z = 1:

(3 * 411) % 616 = 1
j = 411

(The work for this one is a bit long, so work: http://sprunge.us/HeXg, code: http://sprunge.us/YDFF?c, command: ./tiny-RSA-j-finder 3 616)

j is the secret key:

Private Key:
j = 411

Encryption:

Public key from earlier:

Public Key:
n = 667
k = 3

Choose a number p to encrypt (with the obvious requirement that it be smaller than the modulus n):

p = 13

Find the encrypted result E by calculating E = (p ^ k) % n:

(13 ^ 7) % 667 = 492
E = 492

(Again, work is long, so work: http://sprunge.us/DBFF, code: http://sprunge.us/TRdC?c, command: ./tiny-RSA-modexp 13 7 667)

Decryption:

Public Key:

Public Key:
n = 667
k = 3

Private Key:

Private Key:
j = 411

Encrypted Result:

Encrypted Integer:
E = 492

Recover the integer p by calculating p = (E ^ j) % n

(492 ^ 411) % 667 = 144
p = 144

(Same modexp algorithm, same code, work: http://sprunge.us/NiAi, command: ./tiny-RSA-modexp 492 411 667)

?:

Now here is the issue: I input 13 as p and recovered 144 instead. At first I thought I had messed up the modexp part, but I got the same results when using the University of Minnesota modexp calc @ http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html.

So did I mess up somewhere, were the original instructions wrong, and/or something else?

And more importantly, if I messed up, where did I mess up and which instruction(s) is/are wrong if the instructions were wrong?

Any help is appreciated.

PS: Yes I understand that the keysize is waaaaaaay to small to be secure IRL, however I just wanted to learn how the algorithm works.

share|improve this question
    
During encryption, the public exponent 3 turned into a 7. –  Thomas Aug 31 '13 at 10:31
add comment

1 Answer 1

up vote 3 down vote accepted

At the encryption step, you wrote:

Public Key:
n = 667
k = 3

Input:
p = 13

Encrypted Integer:
E = (p ^ k) % n

And then mistakenly calculated:

(13 ^ 7) % 667 = 492
______^_____________

If you calculate it right using k = 3, you will get E = 196 which correctly decrypts to 13.

(as expected)

share|improve this answer
    
I can't believe I missed that. After checking it does work out, though. Thanks! –  haneefmubarak Aug 31 '13 at 20: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.