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

Question

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.

Answer 1

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)