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

I tried out the paper/pencil explanation here, 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


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


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


?:

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 information from the University of Minnesota modexp calc.

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 key size is way too 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. Aug 31 '13 at 10:31
• In the Key Creation step, when you wrote 616 % 2 != 0 and 616 % 3 = 0, didn't you mean to reverse those with regards to which is != and which is = ? May 1 '16 at 1:52

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! Aug 31 '13 at 20:43