Public-key algorithms use separate keys to encrypt and decrypt data. Usually, the key used to encrypt the data is a public key. A public key is a key that can be accessible to anyone without jeopardizing the security of a message. To decrypt ciphertext encrypted with a public-key algorithm, a private key is usually used. A private key is a key that is only known by the intended receiver(s). The public and private keys should have no relation to each other whatsoever.

Most public-key algorithms use some fairly complex mathematical ideas to come up with sets of keys and encryption. We will look at one of the more simple public-key algorithms. In fact, this algorithm was the first public-key algorithm, developed by Whitfield Diffie and Martin Hellman. The algorithm is called the Diffie-Hellman algorithm. Although this example is not secure with small numbers, we will use small numbers anyway to illustrate how it works. This algorithm is not used to encrypt messages. It is only used for secure key distribution.

Mike and Emily would like to use the Diffie-Hellman algorithm to come up with a secret key. The first thing that Mike and Emily must do is come up with a public key (for encryption) and a private key (for decryption). To do this, they must first come up with two integers, n and g. g should be less than n, and both should be greater than 1. For this example we will assume g=8 and n=59. Next, Mike must pick a random integer. We will call this integer x. Mike picks the number 4 out of a hat. Emily must do the same thing. Emily looks at the digits of pi and takes the eighth digit, 6. Emily stores this value to a variable called y. Both Mike and Emily must now use their random numbers in an equation:

 Mike: X = g^x mod n
Emily: Y = g^y mod n

Please note that there are both capital and lowercase Xs and Ys. These are separate variables. 'mod' takes the value before the mod (g^x or g^y), divides it by the value after the mod (n), and returns the remainder. Mike and Emily calculate X and Y:

 Mike: X = g^x mod n = 8^4 mod 59 = 4096 mod 59 = 25
Emily: Y = g^y mod n = 8^6 mod 59 = 262144 mod 59 = 7

After Mike and Emily calculate X and Y, they send them to each other. Mike sends X to Emily and Emily sends Y to Mike. Mike is the only one who knows x, and Emily is the only one who knows y. Mike and Emily can now calculate their secret key using the following equations (the results are also shown):

 Mike: k = Y^x mod n = 7^4 mod 59 = 2401 mod 59 = 41
Emily: k = X^y mod n = 25^6 mod 59 = 244140625 mod 59 = 41

Notice how both Mike and Emily get 41 as the key. Regardless of what values are chosen for g, n, x, and y, k will always come out equal for both Mike and Emily. Additionally, no one else can calculate this key since x and y are kept secret. Many public-key algorithms use these rules to come up with public and private keys.

The next section, digital signatures, will describe how public-key algorithms can be put to use.