5¹ = 5 (mod 787)
5² = 5 ´ 5 = 25 (mod 787)
5⁴ = 25 ´ 25 = 625 (mod 787)
5⁸ = 625 ´ 625 = 273 (mod 787)
5¹⁶ = 273 ´ 273 = 551 (mod 787)
5³² = 551 ´ 551 = 606 (mod 787)
5⁶⁴ = 606 ´ 606 = 494 (mod 787)
5¹²⁸ = 494 ´ 494 = 66 (mod 787)
5²⁵⁶ = 66 ´ 66 = 421 (mod 787).

We stop now because squaring another time will take us to 5⁵¹² and that is a higher power than our target, 5²⁶⁵. Now using the binary expansion of 265, we get 5²⁶⁵ = 5^256+8+1 = 5²⁵⁶ ´ 5⁸ ´ 5¹ = 421 ´ 273 ´ 5 = 155 (mod 787). This took 10 multiplications, rather than the 264 multiplications needed for the naïve approach. Particularly convenient for implementation in modern computer systems is that the key is expressing the exponent in binary form. Since computers work with all numbers in binary form, this step actually takes no time at all.

Even with this more efficient method of computing exponents, RSA public key encryption is slow (by computer standards). Because of this, most implementations, such as in the Secure Socket Layer or in the PGP encryption program use a two step system that uses faster shared key encoding for most of the message.

A shared key system is based on a pseudo-random number generator. The "random number generators" in calculators and computer languages don’t actually generate truly random numbers. They start with some number, called a seed, and generate a deterministic sequence of numbers. This sequence is sufficiently irregular that it can be used in place of truly random numbers in many applications. Since the sequence is deterministic and not random, but irregular enough to play the role of random numbers, we properly call such systems "pseudo-random number generators." In many applications the seed is chosen based on some external factor, such as the system clock, so you get a different sequence each time you try. But all implementations I’ve seen allow the programmer to actually set the seed to a particular value. If you are debugging a program, it is very convenient to be able to repeat the exact same operations and not depend upon random input.

We use a pseudo-random number generator to send a signal consisting of a sequence of 0’s and 1’s, say 10110101, as follows. We agree in advance to use a particular pseudo-random number generator and a particular starting seed. Since we have an 8 bit signal, we generate an 8 bit pseudo-random number, that is a number between 0 and 255, say 147, which is written as 10010011. We now line up our bits and add them one at a time, mod 2. This yields the following

Shared key systems are much faster than public key systems. The disadvantage is that you need to agree on a key ahead of time. That isn’t possible if you are trying to set up a system to handle browsers coming to your shop on the web. In the Secure Socket Layer, the web site sends its public key to the browser. The browser then picks a seed and sends it back to the web site encrypted by the public key. After that, the two systems communicate using a shared key system with the chosen seed. This means that only the seed has to be encrypted using the slower public key encryption; most of the communication uses the faster shared key system.

Of course, there are lots of important details about picking a cryptographically secure pseudo-random number generator, that is a pseudo-random number generator where it is difficult to deduce the seed from the output. It is also important to have the browser pick a starting seed in some fashion that it can’t be easily guessed. Several years ago, researchers cracked Netscape’s encryption system by finding a trick to guess what seed it chose. It doesn’t matter how strong the encryption system is if you can guess the starting seed. Of course, this hole was patched shortly after it was pointed out. Algebraic structures, including modular arithmetic, play a vital role in pseudo-random number generators of all sorts. Unfortunately, I don’t think we will get into the details, as they are rather complicated. A good treatment for those of you who are interested in the details is in the book Applied Cryptography, by Bruce Schneier.

One final complication has been covered up by my saying you "tell everyone your public key." how exactly do you tell everyone? Of course, when you establish a secure connection to amazon.com, the amazon.com web server can send you the public key. But how do you know you are dealing with the actual amazon.com web server? What if some malicious party has fooled your computer into sending your message to an evil computer twin rather than the real amazon.com (whic is difficult but not impossible)? Then you will securely transmit your credit card number, safe in the knowledge that only the bad guys who have fooled your computer can read your credit card number. This problem is dealt with by using a form of digital signatures issued by an appropriate certificate authority. When you connect to amazon.com, you don't get the public key as plain text. Instead you are sent the public key in a message digitally signed by some certificate authority, such as VeriSign or Thawte. The message says that the certificate authority verifies that this is the public key for the site you think you are visiting, that is the certificate authority signs the message verifying that the public key you are being sent really is the public key for amazon.com, and that no one but the real amazon.com can read your messages. Of course, this is only useful if you have the public key of the certificate authority already. But you do have this public key already. The public keys for the major certificate authorities come preinstalled in both Internet Explorer and Netscape Navigator. You can also instruct your browser to accept certificates issued by other authorities once you are satisfied that you have a valid public key for that authority.

This has been just a taste of some of th tricks involved in computer security. There are a lot of other topics related to computer security, many involving interesting mathematics. If you are interested in reading more on this topic, Bruce Schneier has a new book out for a general audience entitled Secrets and Lies that has received good reviews, though I haven't read it yet so I can't vouch for it from personal assurance.