# RSA smaller number work-out-by-hand not working - I think I made a mistake

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.

-
During encryption, the public exponent 3 turned into a 7. –  Thomas Aug 31 '13 at 10:31

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)

-
I can't believe I missed that. After checking it does work out, though. Thanks! –  haneefmubarak Aug 31 '13 at 20:43