Cryptography - A Brief History

What is Cryptography

Cryptography, from the Greek Krypto (hidden) and Grafo (written), is the study and implementation of techniques to hide information, or to protect it from being read. The information that is protected can be written text, electronic signals such as Morse, Telex or speech, or all kinds of digital information like computer files, e-mail messages or data transmissions.

The unprocessed readable information is called plaintext or plain data. The process of making the information unreadable is called encryption or enciphering. The result of encryption is a ciphertext or cryptogram. Reversing this process and retrieving the original readable information is called decryption or deciphering. An algorithm or so-called cipher is used to encrypt or decrypt information.

How a cryptographic algorithm works, is controlled by a secret key, sometimes called password or passphrase (on crypto machines, the key is the setting of the machine). The key is known only to those who are authorized to read the information. Without knowing the key, it should be impossible to reverse the encryption process, or the time required to reverse the process should take so much time that the information has become useless.

Cryptanalysis or crypto-analysis is the study and analysis of existing ciphers or encryption algorithms, in order to assess their quality, to find weaknesses or to find a way to reverse the encryption process without having the key. Decryption without a key (often also without authorization) is a cryptanalytic attack, referred to as breaking or cracking a cipher.

A cryptanalytic attack can exploit weaknesses in the algorithm or crypto device itself, exploit its implementation procedures, or try out all possible keys (a brute-force attack). In general, there are two types of attack: The ciphertext-only attack, where the cryptanalyst or attacker has access only to the ciphertext, and the known-plaintext attack, where the cryptanalyst has access to both ciphertext and its corresponding plaintext or assumed plaintext, to retrieve the corresponding key.

Cryptology comprises both cryptography (making) and cryptanalysis (breaking). The expressions 'code', 'encoding' and 'decoding' are frequently used in cryptography. A code, however, is a simple replacement of information with other information, and doesn't use an algorithm. Generally, these are code books or tables that convert one value (letters, words or phrases) into another value (letter sequence, numerical value or special symbols). Cryptography, on the other hand, uses an algorithm (often a combination of fractioning, transposition and substitution) to manipulate the information. Although technically wrong, the expression 'encoding' is often used to indicate encryption or enciphering and one should therefore look at the context in which such expressions are used.

A Brief History Top

Ever since mankind has existed, people have had secrets, and other people have wanted to know these secrets. The earliest forms of cryptography were performed by pencil and paper, and of course were available only to those who had access to proper education. These classical ciphers were mainly transposition ciphers, which rearrange the letters in a message, and substitution ciphers, which replaced letters, groups of letters or words with other letters, groups or words. One of the earliest reported substitution ciphers was the Caesar cipher or Caesar's shift, in which the letters of the alphabet were replaced by the letters of a second alphabet that was shifted a fixed number of positions again the normal alphabet. It was named after Julius Caesar who used it to communicate with his generals during his military campaigns.

Cryptography was used to secure secret communications from military leaders, diplomats, spies and religious groups. Unfortunately, most of the early ciphers revealed statistical information which could be used to break them. As early as the 9th century, Arab mathematicians discovered frequency analysis and developed methods to break ciphers. This started the race between codemakers and codebreakers.

Frequency analysis proved to solve many of the known ciphers, and it was only with the invention of the poly-alphabetic cipher by Leon Battista Alberti in the 15th century that codemakers were one step ahead of the codebreakers again. Poly-alphabetic ciphers like Vigenère use different sets of alphabets during the encryption process. For ages, these ciphers were considered to be unbreakable until Charles Babage in the 19th century developed the multiple frequency analysis techniques.

Cryptography was extensively used by governments to protect their diplomatic post. In the 18th century, all major countries in Europe started recruiting cryptologists to either protect their communication, mostly letters through postal services, or break the encrypted messages of other countries. These bureaus became known as the Black Chambers. Some of the most notorious Black Chambers were the Austrian Geheime Kabinets-Kanzlei in Vienna, the French Cabinet Noir and later the British Room 40, notorious for their great skill in intercepting and decrypting all kinds of military and diplomatic post.

Cryptography soon became an important weapon in politics and in the many wars in Europe. By the end of the 19th century important steps were made in the development of cryptography. Auguste Kerckhoffs was one of the most important men to change cryptography from a dark art into a science, based on mathematics. It was Kerckhoffs who stated the fundamental principle that encryption should not depend on the secrecy of the system - which sooner or later would be compromised - but should solely depend on the secrecy of the key.

Many new pencil-and-paper ciphers or hand ciphers were developed and used during the First World War. Among them were ADFGVX, Playfair and Double Transposition. All of them were based on transposition, substitution and fractioning of letters. One important invention was the one-time pad encryption for Telex traffic by Gilbert Vernam in 1917. He realized that when a Telex signal is mixed with a truly random key with the same length as the message, the message would be unbreakable. Pencil-and-paper versions of his invention soon followed. With the rise of wireless communication, the need for secure communications for both military as civilian use grew exponential. The impractical and time-consuming hand ciphers could not keep up with the growing demand and this lead to the development of cipher machines.

George Fabyan founded in 1913 a private research laboratory in Geneva, Illinois, that pioneered modern cryptography, later known as the Riverbank's Department of Codes and Ciphers. During the First World War, Riverbank helped several U.S. government departments on cryptanalysis and trained military personnel. Their most renowned codebreakers were Elizebeth Smith and William F. Friedman, who later married. William became chief cryptanalyst for the War Department in 1921 and later led the U.S. Signals Intelligence Service (SIS) for more than two decades.

After the First World War, two types of machines dominated the market. The electromechanical rotor machines such as the German Enigma and Siemens & HalskeT-52, and the British Typex, and the fully mechanical pin-and lug machines like the Hagelin series. Although machines took over most of the work, pencil-and-paper based hand ciphers still remained in use for short-time tactical purposes, where the time to cryptanalyze them would render the tactical information useless. For example, the secure Double Transposition hand cipher was used until the end of the Second World War by both Allied an Axis forces. Some pencil-and-paper ciphers such as one-time pads were even used during the Cold War for clandestine operations by intelligence services.

Elizebeth Friedman worked from 1923 for the U.S. Navy and the Treasury Department, breaking encrypted communications of rum-runners during the Prohibition, drug-runners, smugglers and domestic and international criminal activities. William Friedman wrote eight monographs of which "The Index of Coincidence and its Applications in Cryptography" was at the time the most important of modern cryptography.

All major countries realized the importance of intelligence gathering and new organizations saw the light. During the Second World War, Elizebeth Firedmans's team worked at the U.S Coast Guard Cryptanalytic Unit 387. In Britain, Room 40 was reorganized into the Government Communications & Cipher School (GC&CS), which played a decisive role during the Second World War. Amongst their most famous cryptologist were Alan Turing, Alastair Denniston, Dilly Knox and John Tiltman.

In the United States, the Signal Intelligence Service (SIS) and the Communications Security section of the Office of Naval communications (OP-20-G) were the most important code breaking organizations with legendary cryptologists such as William Friedman and Meredith Gardner. Elizebeth Smith worked for Coast Guard Cryptanalytic Unit 387 and the FBI, leading the breaking of the Enigma machines used by German spies in South America during the Second World War.

The Second World War lead to improved cipher machines like the American SIGABA and SIGCUM, and the German Lorenz SZ-40 and Schlusselgeraet 41. To break the huge amount of encrypted message traffic the codebreaker had to build new, automated machines, which lead directly to the development of the first digital computers. In Bletchley Park, Max Newton and Tommy Flowers developed the Colossus, a digital programmable computer to break the Lorenz SZ-40/42 messages. This was the first step in the evolution of cryptography towards the new computer age. However, new improved electro-mechanical cipher machines such as the TSEC/KL-7, Fialka M-127 and Hagelin CX-52 were designed and remained in service until the 1980s, when the digitalization really broke through.

It was Claude Elwood Shannon who laid the foundations for modern cryptography in 1948 with his famous Information Theory. William Friedman became head of the crypto division of the U.S. Armed Forces Security Agency (AFSA) in 1949 and chief cryptologist for its successor the National Security Agency (NSA) in 1952. Elizebeth and William Friedman had lead the United States into to modern age of cryptography.

The development of electronics and digital computers after the Second World War made it possible to create encryption algorithms, far more complex than before. The new computer algorithms were no longer based on the simple substitution, transposition and fractioning of letters and words, but on a large number of complex operations on data bits. One of the first block ciphers - encryption performed on blocks of data bits - was the Lucifer cipher, designed by Feistel and Coppersmith for IBM, and based on what is known as a Feistel network.

It was the predecessor of DES, the first ever cryptographic standard. However, the computer revolution did not only lead to better encryption systems, but also to faster and better codebreaking techniques. The race between codemakers and codebreakers continued as before. Absolute security was one of the reasons that one-time pad systems remained in use until the 1980s for Telex traffic and such, although the expensive and complex key distribution, a typical downside of one-time pad, made it only affordable to the military and diplomatic services.

The cryptologic community remained very closed and mainly controlled by government agencies until the 1970s. The public release of DES (Data Encryption Standard) and the RSA public-key algorithm were a turning point in the spreading of cryptography. Following Kerckhoffs' principle, newly designed crypto algorithms were released into the public domain, to subject them to extensive academic research. The advantage was obvious. A very large open crypto community could assess new algorithms, discover weaknesses and propose improvements or disapprove the use of a weak algorithm. This lead to a 'survival of the fittest' situation, resulting in quality encryption standards.

The most widely used symmetric algorithms today are the Advanced Encryptions Standard (AES), International Data Encryption Algorithm (IDEA), Blowfish and Triple DES. Nevertheless, secret algorithms are still developed and used, mainly by government agencies. Another type of computer algorithms are stream ciphers. They were developed as an answer to the key distribution problem of long keys, as used in systems like one-time pad. Where a block cipher performs a cryptographic function on a fixed number of plain bits, the stream cipher produces a continuous stream of random values that is mixed with the plain bits. Some well-known stream ciphers are RC4, SEAL and SOBER.

Another field of cryptography is message integrity and authentication. How can we be sure that the message that we receive is authentic and has not been tampered or modified? The solution is a Hash function, a special one-way function. Hash functions use a crypto algorithm, controlled by a secret key, to take an input and return a unique fixed-size string, which is called the hash value. This value is used to 'sign' the message. This unique value cannot be reproduced without the secret key. Therefore it is impossible to change the message content, since this would require the calculation of a new signature value, which is impossible without knowing the key. Meanwhile many different cryptographic hash functions are developed. MD5, SHA-2 and RIPEMD are some of the modern secure hash functions.

The most important development for modern cryptography was public-key cryptography. Until 1970, all encryption was based on symmetric-key algorithms. Both encryption and decryption are performed with the same key. Both sender and receiver of an encrypted message have to use the same key. The disadvantage of this system was a complex key distribution system with several security issues. The invention of the asymmetric-key algorithm by James Ellis was a revolution in the world of cryptography. With asymmetric-key cryptography, two keys are used. A public key for encryption only, and a secret private key for decryption. The public key cannot be used to decrypt the information. This solved the expensive and risky problem of secret key distribution.

From now on, you could make your public key available to everyone. Everyone can encrypt his message, destined to you, with your public key, but only you, with your private secret key, can decrypt the message. There is no longer a need to share a secret key! James Ellis' invention at the Government Communications Headquarters (GCHQ), the successor of the GC&CS, remained top secret. However, Whitfield Diffie and Martin Hellman proposed an asymmetric-key algorithm in 1976 and Ronald Rivest, Adi Shamir, and Len Adleman invented RSA, another public-key system in 1978. Because of their solution to the secret key distribution problem, the Diffie-Hellman and RSA algorithms are among the most widely used crypto algorithms in the world.

Public-key algorithms are based on the computational complexity problem. The Diffie-Hellman algorithm is based on the discrete logarithm problem and RSA is based on the problem of factorization of large primes. Asymmetric-key algorithms require large keys and heavy computation, which makes them suitable only for encryption of small amounts of data. Therefore, strong traditional symmetric algorithms are often used to encrypt the actual information and the asymmetric-key algorithm is then used to encrypt the secret key for the symmetric algorithm. One of the most popular implementations of this principle is Philip Zimmermann's PGP, which is a combination of powerful symmetric block ciphers, the practical public-key asymmetric cryptography and the message integrity of digital signatures by hash functions.

Cryptography Today Top

What has cryptography to do with you? Everything! Today, cryptography is embedded in all aspects of your life to protect your privacy. When you connect your computer to the Internet to browse, to e-mail, or login onto your favorite social network, that connection is secured by TLS (Transport Layer Security). The TLS protocol uses strong cryptography to prevent eavesdropping, tampering, and message forgery. And it's not only your personal computer that uses encryption. When shopping, customer cards are scanned and cryptography protects the personal data of the customers. If you use your credit card to pay or draw money from an ATM, the transaction is securely processed by your bank

Information on the chip of your ID card and health insurance card are encrypted. When you call someone with your mobile phone, your digitized voice is encrypted to prevent eavesdropping. The remote key of the central locking system of your car communicates with your car to generate unique keys, protected by cryptography. Let's put it this way: How would you like it when someone, let's say your life insurance broker, could simply use the Internet to read the computer files of your doctor? Or when someone could check your police record without authorization? What if your employer could check what you do with your money? Cryptography prevents people from illegally invading your privacy.

The most important benefit of cryptography is indeed privacy. Today our lives are completely digitized. Nearly all your private information is stored in one of the many databases from the government, police, city services, banks, commercial holdings, health care services and so on. All this information can get exposed to unauthorized people. We need to stay in control of the technology that ensures our privacy. Cryptography protects the right to privacy and the right to communicate confidentially. Secure communications can protect one’s intimate private life, his business relations, and his social or political activities.

These basic rights are written in the constitution of many, but not all countries. Of course, it is illegal to use cryptography for criminal or terrorist purposes. This does not mean that the use of cryptography should be illegal. Just as with weapons, a knife or a crowbar, it is not because you could use these objects for illegal purposes that they should be regarded as illegal. It is useless to make cryptography illegal. Criminals simply don’t care about the law. If you outlaw cryptography, only outlaws will have cryptography (read privacy).

However, even the most liberal and democratic countries have laws that control the use of cryptography and some countries have stricter laws than others. Many governments are reluctant to permit the use of cryptography by their citizens because it limits the government’s surveillance capabilities. The laws are often a balancing between the protection of the individual privacy and a nation’s security or its the fight against crime. Democratic countries tend to permit cryptography for personal use and have legal mechanisms to bypass the right to privacy with a court order in case of a criminal investigation or a threat of the nation. The boundaries between lawful surveillance and state organized invasion of privacy is often a subjected to discussion, even in democratic countries.

Depending on the country, laws on cryptography can restrict specific types of cryptography partially or allow only government licensed systems, limit the strength of the encryption or demand key escrow. Some laws can force someone to hand over the decryption keys following a judicial warrant and there are laws that restrict the import or export of cryptographic software, equipment or knowledge, or even regard export of cryptography as weapons export.

One might have no objection to his current government having the possibility to invade your privacy 'in case they really need to', and of course only when approved by the justice department. But governments change, and what you believe to be a democracy today, can be a totalitarian state tomorrow. That's why we need to be able to use strong encryption without limitations, to assure our basic rights, today and tomorrow. Is cryptography important to you? You bet it is!

More on this Website Top

More on the Web (opens in new tab) Top

Web Analytics Made Easy -

© Dirk Rijmenants 2004. Last changes: 30 April 2022