Cryptographic History and Techniques
Since the beginning of time people have kept secrets. Probably from the beginning of your memory you have done the same. It's a natural human desire. People have always had, and always will have, some secrets that they either want to keep to themselves or share with only a privileged few. The easiest secret to keep is one that you will tell to no one. The more people you wish to share a secret with, and the more public the forum in which you will communicate your secret, the harder it is to keep your secret a secret.
Secrets in History
In antiquity it was easier to keep a secret because the ability to read was a privilege known to a select few. The number of people who could read a written secret was very limited. Merely by restricting access to the written word, a secret could be retained. The security of such a scheme is obviously limited.
As the ability to read became more prevalent the need to keep secrets from those with the ability to read became more necessary. This need manifested itself most notably in war. While those doing the actual fighting were most likely illiterate, the ones who waged the war were not and each side, no doubt, employed soldiers who could read and speak the language of their enemies. Military communications in the battlefield were probably the genesis of cryptography.
Early attempts at cryptography were simplistic. It is rumored that Caesar used a rudimentary cipher to obfuscate his messages. Those with whom he wished to share a secret were told how to reconstruct the original message. This cipher, The Caesar Cipher, was a simple substitution cipher: Every letter in the alphabet was replaced by the letter three places away modulus the length of the alphabet. In other words, the letter A became D, B became E, X became A, Y became B, Z became C, etc. It's a simple cipher to decode but li brx grq'w nqrz krz lw'v qrw reylrxv!—in other words, if you don't know how it's not obvious! Another variant of this is the ROT-13 cipher. Each letter is rotated 13 places.
Simple substitution ciphers are not very good since each occurrence of a letter is replaced by the same letter. Analysis of a language will result in the probability of letters following other letters—notice the occurrence of the letter r in the above "ciphertext." It's probably a vowel—and this information can be used to determine the substitution offset.
Confidentiality was not the only concern in antiquity. Authentication was another. When few could write, a signature would probably suffice. As the knowledge of reading and writing became more prevalent, wax seals bearing the unique mark of the "signer" were used to authenticate letters, documents, and edicts. The rise of industry brought the capability to make such a seal to more people and the seal ceased being unique. In effect, it became trivial to forge a seal.
Jumping to modern times, ciphers, and their cryptanalysis, have a very notable place in history. Prior to the United States' involvement in World War II, the United States Army was able to crack a code used by the Japanese government. This capability allowed the United States to be forewarned about the attack on Pearl Harbor. This knowledge was not put to good use, though, and the United States suffered great losses as a result of this "surprise" attack. During the same war the German government used an encryption device called Enigma to encipher its communications. This device used a set of rotors (Enigma machines had 5 but only 3 were used for any given communication) that contained the letters of the alphabet and could be independently set. Each letter of input text was transformed into a seemingly random character of output. Seemingly random, because the permutations of transposition were astronomical. The cracking of the Enigma machine was an incredible feat started by the Polish and finished by the British and the story behind the cryptanalysis of Enigma is large enough to be its own book. In fact, several books have been written on the subject.
Communication technology has grown steadily from the days of Caesar to modern times. From papyrus paper to telegram, telex, telephone, FAX, and e-mail, the ability to communicate has been made easier and more ubiquitous. At the same time, the ability to keep such communications secret has remained something of a black art known only to a few—generally governments and military organizations.
The security of each method of communication is dependent on the medium over which the communication is made. The more open the medium the greater the possibility of the message falling into the hands of those for whom it was not intended. Modern day methods of communication are open and public. A telephone call or FAX transmission goes across a shared, public, circuit-switched phone network. An e-mail is transmitted across a shared, public, packet-switched network. An entity in the network between communications endpoints could easily intercept the message. Retention of a secret transmitted using modern methods of communication requires some sort of cryptographic technique to prevent any of these eavesdroppers from learning the secret.
At its base modern cryptography relies on a secret known by the intended recipient(s) of the message. Typically the method of encipherment, the algorithm, is known but the "key" to unlock the secret is not. There are certain cryptosystems that are based upon a secret algorithm—so-called "security through obscurity"—but typically people are reluctant to use an algorithm which is not open to public scrutiny (the debate over the Clipper Chip is a prime example of this).
The problem, then, is to ensure the secrecy of the key—that it is obtainable only by those to whom it should be known. Modern cryptography provides for this.
Rise of the Internet
The popularity of the Internet has given rise to many claims on it. Everybody from browser companies to workstation vendors to router vendors lays claim to being the genesis of or the backbone of the Internet. Most agree, though, that the modern Internet was born in the late '60s under the name ARPANET. The ARPANET was a research tool for those doing work for the United States government under the direction of the Advanced Research Projects Agency (ARPA). The original contract was awarded to BBN of Cambridge, Massachusetts.
ARPANET traffic consisted of communications between universities and military and government laboratories. Researchers at disparate locations were able to exchange files and electronic messages with each other via ARPANET. As the network grew it split into two: MILNET, which was used for military use, and ARPANET (it retained the name), which continued to be used for experimental research. In the early '80s, a standard for ARPANET communications protocols, actually a suite of protocols, was specified. This was termed the TCP/IP protocol suite which eventually became just TCP/IP. It is the base of almost all network traffic today.
In 1987 the National Science Foundation (NSF) funded a network to connect the six supercomputer centers that were spread out nationwide. This network, called NSFnet, spanned the United States from San Diego, California on the west coast to Princeton, New Jersey on the east coast. The original NSFnet was over 56K leased lines, fast in those days but slow by today's standards, so NSF also solicited proposals to build a new high-speed network. The winning proposal was submitted by MCI, IBM, and MERIT (an organization which came out of a network at the University of Michigan), and the backbone of what we call the Internet was built.
Over the course of the '90s, the backbone of this network grew by the addition of different long-haul carriers providing leased line connections and local Internet Service Providers (ISPs) providing local access and short-haul connections. Today, through mutually beneficial service agreements, networks are connected with each side agreeing to carry the other's traffic on the condition that its traffic is also carried. This has created a worldwide network in which, for the price of the initial connection, access is provided to a virtually unlimited amount of resources spanning the entire globe.
Internet Security
The Internet is an ethereal thing. It can appear quite different when looked at for different purposes. For the purposes of secret-sharing, imagine the Internet as a huge town hall which is packed with people. Attempting to communicate a secret in such an environment is difficult, and the chance of others overhearing a conversation between two people increases as the distance between those two people increases. Since the Internet is truly global, no secret of any value can be communicated on it without the help of cryptography.
As the Internet grows (almost exponentially in recent years), its utility increases. Messages can be sent cheaply and reliably and communication is the lifeblood of business. For a company to engage in electronic commerce—the sale of goods and services over the Internet—security is a must. Sensitive information such as credit card numbers must be protected and a business must be able to authenticate each and every sale. In addition, businesses can use the Internet to inexpensively connect disparate offices. Interoffice electronic mail and even phone calls can be routed over the Internet. Because sensitive corporate information would most likely be transmitted over these links, the need for security should be obvious.
But, Internet security concerns are not solely business'. Each and every person has a need and a right to privacy, and when someone goes on-line, the expectation of privacy does not disappear. As consumer electronics become more and more Internet-aware, the need for security grows. When our phones and VCRs become accessible over the Internet, we won't want pranksters or hackers to steal our phone line or randomly turn our VCRs on and off.
Privacy is not just confidentiality, though; it also includes anonymity. People must be comfortable in cyberspace and an often ignored component of that is the ability for an individual to remain anonymous. What we read, where we go, to whom we talk, for whom we vote, and what we buy is not information that most people traditionally publicize, and if people are required to disclose information in cyberspace that they would not normally disclose in real life, they will be reluctant to engage in Internet activity.
Thankfully, cryptography can address these concerns.
