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.
3
turned into a7
. $\endgroup$ – Thomas Aug 31 '13 at 10:31616 % 2 != 0
and616 % 3 = 0
, didn't you mean to reverse those with regards to which is!=
and which is=
? $\endgroup$ – temporary_user_name May 1 '16 at 1:52