Cryptography

Cryptography (from Greek kryptós, "hidden", and gráphein, "to write") is the study of the principles and techniques by which information can be translated into a "garbled" version that is difficult for an unauthorized person to read, while still allowing the intended reader to convert the resulting gobbledygook back into the original information. The term cryptology has sometimes been used instead of cryptography with this definition; but there is some tension between these two schools.

The original information being sent is usually called the plaintext. Encryption is the plaintext-to-garble conversion, and decryption is the garble-to-plaintext conversion. One main type of encryption is called encoding (yielding codetext), the other is called enciphering (yielding, naturally, ciphertext). The exact form of the encryption and decryption is controlled by one or more keys.

Unsurprisingly, the study of hiding messages from others has been accompanied by the study of how to read such messages when one is not the intended receiver; this area of study is called cryptanalysis.

Cryptography has four main goals:

message confidentiality: Only the authorised receiver should be able to extract the contents of the message from its encrypted form. In addition, it should not be possible to obtain information about the message contents (such as a statistical distribution of certain characters).
message integrity: The receiver should be able to determine if the message has been altered since transmission.
authentication: The receiver should be able to identify the sender, and verify that the purported sender actually did send the message.
non-repudiation: The sender should not be able to deny sending the message.

Not all cryptographic systems or algorithms achieve all of the above goals, or are even intended to. Poorly designed crypto systems achieve them only by accident; but even with well designed systems, some goals aren't practical (or desirable) in some contexts. For example, the sender of the message may want to be anonymous, or the system may have to be designed for an environment with limited computing resources.

In addition, some confusion may arise in a crypto system design regarding whom we are referring to when speaking of the "sender" or "receiver"; some examples for real crypto systems include:

1) a computer program on a local system,

2) a computer program on a 'nearby' system which 'provides security services' for users on other nearby systems,

3) or -- what most people assume is "obviously" meant -- a human being using some computer system.

In situations like this, unintended failures of each of the stated goals can occur quite easily, often without notice to any human involved, and even given perfect algorithms, superb and provably secure system design, and error free implementation. Such failures are most often due to extra-cryptographic issues, showing that good algorithms and good protocols alone do not provide 'security'. Instead, careful thought is required regarding the entire system design -- and too often, this is absent in practice with real-world crypto systems.

Although cryptography has a long and complex history, it wasn't until the 19th century that it developed anything more than ad hoc approaches to either cryptanalysis (eg, Charles Babbage) or encryption (eg, Auguste Kerckhoffs). An increasingly mathematically theoretical trend accelerated up to World War II (notably in William F. Friedman's application of statistical techniques to cryptography and in Marian Rejewski's initial break of the German Army Enigma system) and became essentially completely mathematical afterwards. Even then, it has taken widely available computers and the Internet to bring effective cryptography into common use by anyone other than national governments or similarly sized enterprises.

Classical Cryptography

The earliest use of cryptography can be found with the use of non-standard hieroglyphics on monuments by the Egyptians from the Old Kingdom (ca 3500 years ago). These are not regarded as serious attempts at secret communications, however, but rather as an attempt at mystery, intrigue, or even amusement. Later, Hebrew scholars also made use of simple substitution ciphers (such as the Atbash cipher) beginning perhaps around 500 to 600 BCE. As did the Greeks (eg, the scytale transposition cipher said to have been used by the Spartans) and the Romans (eg, the Caesar cipher and its variations). Cryptography became (secretly) important in Europe during and after the Renaissance. The various Italian states, specifically including the Papacy, were responsible for substantial improvements in cryptographic practice (eg, polyalphabetic cyphers).

Both cryptography and cryptanalysis featured in the Babington plot during the reign of Queen Elizabeth I. And an encrypted message from the time of the Man in the Iron Mask (decrypted around 1900 by Étienne Bazeries ) has shed some, regrettably non-definitive, light on the identity of that legendary, and unfortunate, prisoner. Cryptography, and its misuse, was involved in the plotting which led to the execution of Mata Hari and even more reprehensibly in the travesty which led to Dreyfus' conviction and imprisonment, both in the early 20th century. Fortunately, cryptographers were also involved in setting Dreyfus free; Mata Hari, in contrast, was shot.

Mathematical cryptography leapt (secretly) ahead after World War I. Marian Rejewski, in Poland, attacked and 'broke' the early German Army Enigma system (an electromechanical rotor machine) using purely mathematical techniques (1932 et seq), and his work was extended by Alan Turing, Gordon Welchman, and others at Bletchley Park beginning in 1939. US Navy cryptographers (with help from the British and the Dutch after 1940) broke into several Japanese Navy crypto systems leading most famously to the US victory at Midway, and into some of the Japanese attache systems as well. The US Army SIS group managed to break the highest security Japanese diplomatic cipher system (a electromechanical stepping switch machine called Purple by the Americans) before WWII began. The Americans referred to the intelligence resulting from cryptanalysis, perhaps especially that from the Purple machine, as 'Magic'. The British eventually settled on 'Ultra' for intelligence resulting from cryptanalysis, particularly that from message traffic enciphered by the various Enigmas.

World War II Cryptography

By World War II mechanical and electromechanical cryptographic systems were in wide use, although where these were impractical manual systems were still used. Great advances were made in both practical and mathematical cryptography in this period, all in secrecy. Some of this information has begun to be declassified in recent years as the official 50-year (British) secrecy period has come to an end.

The Germans made heavy use of an electromechanical rotor system known as Enigma, the Japanese Foreign Office used the independently developed electrical stepping switch based system called Purple by the US and the earlier similar machine used by some attaches in Japanese embassies. This last was called the 'M-machine' by the US. All were broken, to one degree or another by the Allies. Other cypher machines used included the British Type X and the American SIGABA; both were electromechanical rotor designs similar to the Enigma. Neither is known to have been broken by anyone.

Modern Cryptography

The era of modern cryptographic theory started with Claude Shannon, arguably the father of mathematical cryptography. In 1949 he published the paper Communication Theory of Secrecy Systems in the Bell System Technical Journal and, with Warren Weaver, a little later the book, Mathematical Theory of Communication. These, in addition to his other works on information and communication theory established a strong theoretical basis for cryptography.

1976 saw two major public (ie, non-secret!) advances. First was the DES (Data Encryption Standard) developed by IBM and the NSA in an effort to develop secure communication facilities for businesses such as banks. DES was later published as a FIPS (Federal Information Processing Standard) in 1977 (currently at FIPS 46-3), and made obsolete by the adoption of the Advanced Encryption Standard as FIPS 197. DES was the first cipher algorithm accessible to the public blessed by a national crypto agency such as NSA. The release of the specifications of the DES algorithm by NBS (now NIST) stimulated an explosion of public and academic interest in cryptography. DES and more secure variants of it (such as 3DES, see FIPS 46-3) are still used today, although DES was essentially replaced by AES (Advanced Encryption Standard) in 2001. It remains in wide use nonetheless.

Secondly, and even more importantly, was the publication of the paper New Directions in Cryptography by Whitfield Diffie and Martin Hellman. This paper introduced a radically new method of distributing cryptographic keys, known as asymmetric key cryptography. This essentially solved one of the fundamental problems of cryptography, key distribution.

Prior to this, all useful modern encryption algorithms had been symmetric key algorithms, in which the same key must be used with the underlying algorithm by both the sender and the recipient. All of the electromechanical machines used in WWII were of this class, as were the Caesar and Atbash cyphers and most useful cyphers throughout history. Of necessity then, that key had to be exchanged between the communicating parties in some secure way -- the term usually used is 'via a secure channel') such as a trusted courier or face-to-face contact -- prior to any effective use of the cipher algorithm. This requirement rapidly becomes unmanageable when the number of participants increases beyond some small number, or when (really) secure channels aren't available for key exchange. In particular, a separate key is required for each communicating pair if other parties are not to be able to decrypt their messages. A system of this kind is also known as a private key cryptosystem.

In contrast, in asymmetric key cryptography, there is a pair of related keys for the algorithm, one of which is used for encryption and the other for decryption. Some of these algorithms have the property that one of the keys may be made public since the other cannot be (by any currently known method) deduced from the 'public' key. The other key in these systems is kept secret and is usually called the 'private' key. A system of this kind is known as a public key algorithm, although the term asymmetric key cryptography is preferred by those who wish to avoid the ambiguity of using that term for all such algorithms and to stress that there are two distinct keys with different secrecy requirements. As a result, only one key pair is now needed per receiver (regardless of number of senders) as possession of a public key (by anyone whatsoever) does not compromise the security of the corresponding private key. Note, however, that it has NOT been proven, for good public/private asymmetric key algorithms, that the private key cannot be deduced from the public key. Informed observers believe it to be so for the 'good' algorithms, however; and no examples have been shown for any of them.

Nevertheless, some of the well respected, and widely used, public key / private key algorithms can be broken by one or another cryptanalytic attack and so, like most encryption algorithms, the protocols in which they are used must be chosen and implemented carefully. All of them can be broken if the key length used is short enough to permit practical brute force key search. This is an example of the fundamental problem for those who wish to keep their communications confidential; they must choose a crypto system (algorithms + protocols + operation) that resists all attack from any attacker. There being no way to know who those attackers might be, nor what resources they might be able to deploy, nor what advances in cryptanalysis (or its associated mathematics) might in futrue occur, users may only do the best they know how, and then hope. In practice, for well designed / implemented / used crypto systems, this is believed to be enough. Distinguishing between well designed crypto systems and crypto trash is another, quite difficult, problem for those who are not themselves expert cryptographers.

However, both asymmetric key cryptography and the best known of the public key / private key algorithms (ie, what is usually called the RSA algorithm) seem to have been developed by a UK intelligence agency before the public announcement in '76. GCHQ has released documents claiming that they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were written during the 1960s and 1970s which led to schemes essentially identical to RSA encryption and Diffie-Hellman key exchange in 1973 and 1974. Some of these have now been published.

Some algorithms of various kinds

Hash functions, aka message digest functions

Public key algorithms (asymmetric key algorithms)

Secret key algorithms (symmetric key algorithms)

Enigma
One-time pad
Data Encryption Standard (DES, FIPS 46-3)
Lucifer cipher
RC4
Blowfish
International Data Encryption Algorithm (IDEA)
Advanced Encryption Standard (AES, FIPS 197)
IDEA
Twofish
RC6

Cryptography

Contents

Classical Cryptography

World War II Cryptography

Modern Cryptography

Some algorithms of various kinds

Hash functions, aka message digest functions

Public key algorithms (asymmetric key algorithms)

Secret key algorithms (symmetric key algorithms)

Pseudo-random number generators

Anonymous communication

Terminology

Further Reading

Related topics