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.