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.