RSA Encryption

This explanation and example of RSA encryption is confusing me. I found this in a pdf on the web.



quote:
--------------------------------------------------------------------------------

Example: RSA
n, e = public key, n = product of two primes p and q
d = private key
Encryption: C = M^e mod n
Decryption: M = C^d mod n
p, q = 5, 7
n = p * q = 35
e = 5
d = e^-1 mod ((p-1)(q-1)) = 5

Message M = 4
Encryption: C = 4^5 mod 35 = 9
Decryption: M = 9^5 mod 35
= 59049 mod 35
= 4


--------------------------------------------------------------------------------

If you aren't aware, M is the original message and C is the encrypted message (ciphertext).


Now, the calculation,

d = e^-1 mod ((p-1)(q-1)) = 5

seems to me to be wrong, unless I’m being a complete muppet. Surely it should be,

d = e^-1 mod ((p-1)(q-1))
= (1/5) mod 24
= 0.2.

However,

M != 9^0.2 mod 35, so the algorithm wouldn’t work.

As illustrated in the example, d = 5 makes the algorithm work. But having the private key identical to the public key (or even the inverse of it for that matter) doesn’t strike me as being particularly secure.

I found a different explanation of RSA that gave the same theory as this one. Can anyone shed some light on how this algorithm is supposed to work?

Ta Guys.

What site did you get this from?

0.2^-1 == 5.

This was the site I got the pdf from. The relative stuff starts on page 21.

http://www.cryptoengines.com/~peter/part1.pdf

http://public.csusm.edu/public/FranzL/M372/numth.pdf

in the chapter about linear congruences (2 i think) there is an example of RSA encryption, the best I have found so far.

-LC

The way that I was shown to do it is using the Euclidean Algorithm to find d.

try searching for that on google, I remember there are some examples of it around. like this one:

http://www.math.umn.edu/~garrett/js/gcd.html

I can't remember exactly what you do with it, I did all this stuff a long time ago, but it's something like running through Euclid's algorithm with Phi(n) and d, then you retrieve the third column of this process and use it to create e. I've got all the code to do it, but I don't have time to figure out exactly how I wrote it.

I also wrote a javascript RSA app a few years ago. It's not that great, I'm not even sure if it's still functional (I know it regularly corrupts the last few characters) and the source is horrendous (was actually one of the first programs I ever wrote, so it's full of yukky stuff):

RSApage

sorry if all that's a load of babble, I just happen to like RSA quite a bit....

-mark

Rijndael is the current standard. You can get it on PDF, and it is quite similar.