Simple Public Key Explanation

Found this interesting tidbit from Cyphernomicon 2.5: Crypto. This is based on a posting by Matthew Ghio in the Usenet group alt.anonymous dated 1994-09-03. It explains, in relatively simple terms, how public key cryptography works. I did correct the math error.

You pick two prime numbers; for example 3 and 11. Multiply them together, equals 33. Now you calculate the product of one less than each number, plus one. (3-1)(11-1)+1=21. There is a mathematical relationship that says that x = x^21 mod 33 for any x from 0 to 32. Now you factor 21, yields 3 and 7.

You pick one of those numbers to be your private key and the other one is your public key. So you have:

Public key: 3
Private key: 7

Someone encrypts a message for you by taking plaintext message m to make ciphertext message c: c=m^3 mod 33

You decrypt c and find m using your private key: m=c^7 mod 33

If the numbers are several hundred digits long (as in PGP), it is nearly impossible to guess the secret key.

Public key cryptography is used in a number of other things — SSL being the most widely used.