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 lexigraphic schools. There is also some tension between fans of two spellings of cypher (the alternate is cipher). In English, the cypher spelling has historical pride of place. This and related articles in the Wikipedia are often revised by those with strong opinions on the spelling question.

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. People involved in such work, and with cryptography in general, are known as cryptographers (or for those in the other school, cryptologists).

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), after which the receiver decodes the codetext. The other is called enciphering (yielding, naturally, cyphertext), after which the receiver decyphers the cyphertext. The exact operation of the encryption and decryption is controlled by one or more keys.

Cryptography has four main goals, though they are nearly always concealed beneath a blanket of marketing speak. Examining any proposed crypto system with these in mind, and ignoring the marketing blather, will be a very useful exercise in the real world. They are:

message confidentiality: Only the authorised recipient 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) as this makes cryptanalysis easier.
message integrity: The recipient should be able to determine if the message has been altered during transmission.
authentication: The recipient 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, or poorly implemented, crypto systems achieve them only by accident, and users can and do reduce even well designed and implemented crypto systems to the security equivalent of Swiss cheese. But even with well designed, well implemented, and properly used crypto 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 be intended for an environment with limited computing resources, or confidentiality might not matter.

In addition, some confusion may arise in a crypto system design regarding whom we are referring to when speaking of the "sender" or "recipient"; some examples for real crypto systems in the modern world 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.

When confusion on these points is present (at the design stage, during implementation, or by a user), unintended failures in reaching 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; each such failure demonstrates 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's Crimean War era work on mathematical cryptanalysis of polyalphabetic cyphers) or encryption (eg, Auguste Kerckhoffs' writings in the later 19th century). 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 into the German Army's Enigma system); both cryptography and cryptanalysis have become far more mathematical since WWII. 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 known use of cryptography is found in non-standard hieroglyphics on monuments from Egypt's Old Kingdom (ca 4000 years ago). These are not thought to be serious attempts at secret communications, however, but rather attempts at mystery, intrigue, or even amusement for literate onlookers. Each of which has been, intermittently, still another use of cryptography, or of something that looks (impressively if misleadingly) like it. Later, Hebrew scholars made use of simple substitution ciphers (such as the Atbash cipher) beginning perhaps around 500 to 600 BCE. Cryptography has a long tradition in religious writing likely to offend the dominant culture or political authorities. Perhaps the most famous is the 'Number of the Beast' from the book of Revelations in the Christian New Testament. 666 is almost certainly a cryptographic (ie, coded) way of concealing a dangerous reference; most scholars believe it's a way of referring to Rome (and so to Roman policies of persecution) that would be understood by the initiated (who 'had the codebook') and yet be safe (or less dangerous) if it came to the attention of those authorities. At least for orthodox Christian writing, the need for such concealment ended with Constantine's conversion.

The classical Greeks are said to have known of cyphers (eg, the scytale transposition cypher said to have been used by the Spartan military). The Romans certainly did (eg, the Caesar cipher and its variations). There is mention of a book about Roman military cryptography (especially Caesar's); it has been, unfortunately, lost. Cryptography became (secretly) important still later as a consequence of political competition and religous analysis. For instance, in Europe during and after the Renaissance, the various Italian states, most specifically including the Papacy, were responsible for substantial improvements in cryptographic practice (eg, polyalphabetic cyphers). And in the Arab world, textual analysis of the Koran led to the invention of the letter frequency counting technique for breaking monoalphabetic substitution cyphers around 1000 CE.

Both cryptography, cryptanalysis, and secret agent betrayal 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 (mostly secretly) ahead after World War I. Marian Rejewski, in Poland, attacked and 'broke' the early German Army Enigma system (an electromechanical rotor cypher machine) using purely mathematical techniques in (1932 and up to '39). His work was extended by Alan Turing, Gordon Welchman, and others at Bletchley Park beginning in 1939, leading to sustained breaks into several other of the Enigma variants and their assorted networks. US Navy cryptographers (with help from the British and the Dutch after 1940) broke into several Japanese Navy crypto systems. The break into one of them famously led to the US victory in the Battle of Midway. A US Army group, the SIS, managed to break the highest security Japanese diplomatic cypher 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. An earlier term had been 'Boniface'.

World War II Cryptography

By World War II mechanical and electromechanical cryptographic machines 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 information about this period has begun to be declassified in recent years as the official 50-year (British) secrecy period has come to an end, and as the relevant US have slowly opened.

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 also used several similar machines for attaches in some Japanese embassies. One of these was called the 'M-machine' by the US, another was referred to as 'Red'. All were broken, to one degree or another by the Allies. Other cypher machines used in WWII included the British Type X and the American SIGABA; both were electromechanical rotor designs similar in spirit 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 a little later the book, Mathematical Theory of Communication, with Warren Weaver. 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, with 'advice' and modification by the NSA, at the invitation of the National Bureau of Standards (now NIST), in an effort to develop secure electronic 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 has been made effectively obsolete by the adoption of the Advanced Encryption Standard, also a NIST project, 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 officially supplanted by AES (Advanced Encryption Standard) in 2001 when NIST announced the selection of Rinjdael, by two Belgian cryptographers. It remains in wide use nonetheless, having been incorporated into many national and organizational standards.

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 cryptographic 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 logical class, as were the Caesar and Atbash cyphers and essentially all crypto systems throughout history; the key for a code is, of course, the codebook. Of necessity, a key in such a system had to be exchanged between the communicating parties in some secure way -- the term usually used is 'via a secure channel') such as a trustworthy courier with a briefcase handcuffed to a wrist or face-to-face contact -- prior to any use of the system. 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 or conventional key cryptosystem.

In contrast, in asymmetric key cryptography, there is a pair of mathematically related keys for the algorithm, one of which is used for encryption and the other for decryption. Some of these algorithms have the additional 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. An algorithm of this kind is known as a public key / private 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 recipient (regardless of number of senders) as possession of a public key (by anyone whatsoever) does not compromise the 'security' of the algorithm so long as the corresponding private key is not known to any attacker (effectively this means not known to anyone except the sender). Note, however, that it has NOT been proven, for any of the good public/private asymmetric key algorithms, that a private key cannot be deduced from a public key (or vice versa). Informed observers believe it to be currently impossible (and perhaps forever impossible) for the 'good' algorithms, however; and no workable deduction techniques have been publicly 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 within 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; indeed this is true of all encryption algorithms using keys, regardless of class.

This is an example of the fundamental problem for those who wish to keep their communications secure; 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 future 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, possibly even for all(?) future attackers. Distinguishing between well designed / implemented / used crypto systems and crypto trash is another, quite difficult, problem for those who are not themselves expert cryptographers. It is even quite difficult for those who are.

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 eventually led to schemes essentially identical to RSA encryption and Diffie-Hellman key exchange in 1973 and 1974. Some of these have now been published, and the inventors (James Ellis, Clifford Cocks, and Malcolm Williamson) have made public (some of) their work.

Some algorithms of various kinds

Hash functions, aka message digest functions, cryptographic hash functions

Public key / private key encryption algorithms (aka asymmetric key algorithms)

Secret key algorithms (aka symmetric key algorithms)

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

Cryptography

Classical Cryptography

World War II Cryptography

Modern Cryptography

Some algorithms of various kinds

Hash functions, aka message digest functions, cryptographic hash functions

Public key / private key encryption algorithms (aka asymmetric key algorithms)

Secret key algorithms (aka symmetric key algorithms)

Pseudo-random number generators

Anonymous communication

Terminology

Further Reading

Related topics