The History of Cryptography

Cryptography is the art or science of secret writing. As long as people have been speaking and writing, there has been the need to keep conversations and letters private. Originally the word "cryptography" came from the Greek word "kryptos," (meaning to hide) and later from New Latin cryptographia, from crypt- + -graphia. Generally Cryptography could be categorized by three different methods of handling messages:

Ciphering Cryptography

This field includes all the cryptography techniques that handle message text as a series of separate elements. There are two major techniques:

• Replacement, where each possible 'element' has its own value and the process aims at altering it according to a specific macro/equation, and
  
  
• Repositioning, that deals with the distance of each 'element' from the start/specific point of the document.

The Invisible Writing

This was very popular during the Middle Ages and includes all the techniques that don't allow the reader to see the message until a certain process has been followed. Usually these techniques deal with a special, invisible ink that has to be covered with the proper substance - either a chemical or simply something sticky like ash or charcoal - to make the message visible.

The Codal Cryptography

This field refers to the replacement of some words with others with symbolic meaning so as to change the meaning of the message. It can either be applied to just some specific keywords - a technique very useful today as spy nets to handle the vast levels of information simply scan the messages for certain keywords - or to the whole document. To use this method you have to obtain or create a codebook.

One doesn't need a paper written with an incoherent display of letters and numbers to experience cryptography. Throughout the ages the encryption methods range from the very simple to the very sophisticated. One thing that was, and will always, remain a common link in the cryptographic world is the need to keep the decode key absolutely secret. No matter how simple or complicated the encode methodology is, keeping the decode key secret will make the encode process a success or failure.

Almost 4,000 years ago, a scribe in the town of Menet Khufu drew out the story of his master's life in hieroglyphics. The hieroglyphic "language" became the world's the first documented use of cryptography. Similarly, to an observer 5,000 years from now, a bill for consideration in the United States Senate or House could be considered an encrypted document. Using the complicated language of lawyers, any legal document appears to be in a different form of English, just as the Egyptians used a different form of Hieroglyphs.

5th Century BC Greek Skytale stick

In the fifth century BC, the Greeks used a system that consisted of a thin sheet of papyrus wrapped around a staff. This is now known as a Skytale. If a person wanted to send a message in secrecy, he could write the message down the length of the staff so that when the papyrus was unwrapped, the message would be unintelligible. To read it, the recipient would have to re-wrap the papyrus with an identical stick. Only then would the letters of the message properly line up.

Obviously such an encryption system would be foolish to use today, because if the parchment fell in a modern enemy's hands, it would be cracked within minutes. However, 2500 years ago, the percent of people who could read and write was much smaller than it is today. Therefore, at the time Skytales provided a secure method of communication.

It is believed that when Julius Caesar sent a message to the front lines, he would write his message in code. His encode scheme was to simply advance each letter in his message by three letters (at the end of the alphabet he would continue from the beginning), thus if the message was intercepted by the enemy they wouldn't know its contents.

For example, the message "ET TU, BRUTE" would become "HW WX, EUXWH". This process became known as a substitution cipher.

Jumping to 1895, the first wireless radio was invented, giving rise to a new age in cryptography. Radio provided military troops in World War I with much greater flexibility by eliminating the need to run wires between camps and headquarters. However radio is public; anyone can intercept the signals and look at them to his or her hearts content. No longer was it necessary to tap a wire directly; someone could simply put up a radio receiver and half the work was done. As a result, cryptographers of World War I had to invent stronger systems of encryption to withstand an enemy's best attack when a greater amount of encoded text is available.

For all the historical personalities involved in the evolution of cryptography in the United States this century, it is William Frederick Friedman, founder of Riverbank Laboratories, cryptanalyst for the US government, and lead code-breaker of Japan's World War II Purple Machine, who is "honored as the father of US cryptanalysis." In 1918 Friedman authored The Index of Coincidence and Its Applications in Cryptography, which is still considered by many in this field as the premiere work on cryptograph written this century.

Although cryptography was employed during World War I, two notable machines were employed during World War II: the Germans' Enigma machine, developed by Arthur Scherbius, and the Japanese Purple Machine, developed using techniques first discovered by Herbert O. Yardley.

Photo courtesy of National Cryptologic Museum German Enigma encryption machine

The German Enigma encryption machine was based on a set of rotating wheels, which were used to encrypt and decrypt messages. The way it worked was by "mapping" one alphabet onto another. For example, the first wheel might have mapped "F" to "N", the second "N" to "L", and so on. By repeating the process in reverse, the message can be decoded. The more wheels there were, the harder it was to decode.

The first advances in cracking the Enigma were made by the Polish in the 1930s. At that point, the machine only used three rotors in six possible combinations. Although breaking the Enigma in the 1930s was a major accomplishment, the Polish were unable to crack the Enigma after the German military took over its development in World War II. The Germans increased the number of rotor combinations to 60 by adding an additional two rotors to the pool (though the machine still only used 3).

Photo courtesy of National Cryptologic Museum British Bombe encryption machine

The British then continued working on deciphering the Enigma, starting where the Poles left off. A man by the name of Alan Turing, then a young mathematician, built a machine to crack the Enigma while working for the British government. His machine, called the Turing Bombe, used ?? rotors to create different letter-code combinations. It could chug along with different decode key combinations that would eventually crack an Enigma code in about 15 hours.

In 1940, while the British, Polish, and French were working hard on cracking the German Enigma (and for the most part, succeeding), the US Signals Intelligence Service (SIS) worked on Japan's code machine. What made cracking the Japan's Purple more difficult than the German Enigma was that it used a revolutionary concept in machine cryptography. Purple used telephone stepping switches instead of rotors in its encryption scheme. A stepping switch was used in those days to route telephone calls from source to destination. By utilizing this, the encrypted letters did not follow patterns that code breakers were accustomed to with traditional rotor machines.

Photo courtesy of National Cryptologic Museum American SIGABA encryption machine

The US countered Japan by creating the ECM Mark II model CSP 889/2900 (a.k.a. SIGABA). SIGABA was the only machine used by any participant of the war to remain totally unbroken for the duration of its use. The SIGABA was also a rotor machine, much like the German Enigma. After World War II, the SIGABA remained in service until 1959, when it was retired for being too slow.

The first general purpose electronic computer was the Electronic Numerical Integrator And Computer, or ENIAC, and was built in the 1950's at the University of Pennsylvania's Moore School. It spanned 150 feet wide, needed 17,480 vacuum tubes operating at a rate of 100,000 pulses per second, and had twenty banks of flashing lights that indicated the results of its computations. ENIAC could add 5,000 numbers or do fourteen 10-digit multiplications in a second--dead slow by present-day standards, but fast compared with the same task performed on a hand calculator. By comparison, the fastest mechanical relay computers being operated experimentally at Harvard, Bell Laboratories, and elsewhere could do no more than 15 to 50 additions per second, a full two orders of magnitude slower.

Solid-state electronics, transistors, and integrated circuits were the revolutionary developments that made possible the miniaturization of computers and heralded the world of today. It was suddenly possible to perform far more complicated encryption and decryption techniques, but with it came the ability of others to perform attacks on that cryptography. The faster a computer can perform the operations necessary to test keys, the faster a particular key can be broken. This is called a brute force attack, since it blindly tries all the possible options. In a good algorithm, this is the only way to try and recover the message or the key. Because of the computational requirements, the amount of time required to perform a brute-force attack is strongly related to the size of the key, as well as being influenced by the encryption technique.

Elliptic Curve Cryptography (ECC) is a competing algorithm to the popular RSA public key and Diffie-Hellman encryption schemes. It uses a complex mathematical function to scramble data and not only offers more cryptography strength in a smaller key length than RSA, but is regarded as being faster and requiring less processing power. This makes an ideal system for Smartcards and mobile phones.

The RSA public key methodology is based on an integer factorization problem, while DSA is based on a discrete logarithm problem. Both function in a similar effect, using their specific type of equation to scramble a transmission, which is then decoded using the same formula. In today's eBusiness world, that means for transmission security the key in both equations must be at least 150 decimal places long -- approximately 500 bits of data -- to be considered secure.

ECC uses fewer decimal places to provide longer-term security. Fewer decimal places mean fewer bits that are needed to encrypt the data. ECC is based on an algebraic problem, where RSA is based on integer factorization. Because ECC is a more complex problem, it's a higher strength algorithm at smaller "key" sizes - the "key" being the formula, or answer, to unlock the encryption."

The following discussion of the IP Security Protocol is from the Web site: http://www.ietf.org/html.charters/ipsec-charter.html and includes text from a related paper regarding AES dated November 2000:

Rapid advances in communication technology have accentuated the need for security in the Internet. The IP Security Protocol Working Group (IPSEC) will develop mechanisms to protect client protocols of IP. A security protocol in the network layer will be developed to provide cryptographic security services that will flexibly support combinations of authentication, integrity, access control, and confidentiality.

The protocol formats for the IP Authentication Header (AH) and IP Encapsulating Security Payload (ESP) will be independent of the cryptographic algorithm. The preliminary goals will specifically pursue host-to-host security followed by subnet-to-subnet and host-to-subnet topologies.

Protocol and cryptographic techniques will also be developed to support the key management requirements of the network layer security. The Internet Key Management Protocol (IKMP) will be specified as an application layer protocol that is independent of the lower layer security protocol.

It is the intention of the IETF IPsec Working Group that AES (Advanced Encryption Algorithm) [sic] will eventually be adopted as the default IPsec ESP cipher and will obtain the status of MUST be included in compliant IPsec implementations. AES is the successor to the venerable DES. It is the culmination of a four-year competitive process initiated by NIST (National Institute of Standards and Technology). The competition was an open one, with public participation and comment solicited at each step of the process. The AES, formerly known as Rijndael, was chosen from the five finalists. The four other finalists, MARS, RC6, Serpent and Twofish, were all adjudged to be sufficiently secure. The AES is the government's designated encryption cipher, and will be definitively described in a FIPS (Federal Information Processing Standard), expected to be completed by summer 2001. The expectation is that AES will suffice to protect sensitive (unclassified) government information at least until the next century.

Biometric systems use physical characteristics unique to each individual to grant--or deny--access to computer resources. These systems go a crucial step beyond traditional passwords or security-access cards (also called smart cards) by ensuring that the individual trying to log on is actually the authorized person--not just someone who found a key card in a desk or the Post-It note with a password under the keyboard. Although many technologies fit in the biometric space, each works a bit differently.