Cryptography

Cryptography (from Greek kryptós, "hidden", and gráphein, "to write") is generally understood to be the study of the principles and techniques by which information is converted into an encrypted version that is difficult (ideally, impossible) for any unauthorized person to convert to the original information, while still allowing the intended reader to do so. In fact, cryptography covers rather more than merely encryption and decryption. It is, in practice, a specialized branch of information theory with substantial additions from other branches of mathematics. And perspective and approaches, because of the inherent conflict between those authorized, and those not, to see the information / interfere in the exchange / pretend to be other than they are / etc, from such sources as Machiavelli, Sun Tzu, and Karl von Clausewitz.

The term cryptology has sometimes been used instead of cryptography for this field; it is recent coinage, due apparently to William F. Friedman in the early 20th century. There is some tension between these two lexigraphic schools, as there is between the two spellings of cipher and cypher both of which are used and have long histories in English.

Unsurprisingly, the study of hiding the meaning of messages from others by encrypting them 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 some of those in the other lexigraphic school, cryptologists).

The original unencrypted information being sent from one person (or organization) to another is usually called the plaintext. Encryption is the process of converting the plaintext into some unreadable form (ideally one undistinguisable from random gibberish), and decryption converts this back to the plaintext. Encryption includes two major classes of technique: encoding (yielding codetext) and enciphering (yielding ciphertext). The exact operation of the encryption and decryption, for all schemes with any pretense to security, is controlled by one or more keys.

Table of contents
1 Overview: goals
2 Classical Cryptography
3 World War II Cryptography
4 Modern Cryptography
5 Some cryptographic algorithms of various kinds
6 Further Reading
7 Related topics
8 External links

Overview: goals

Popular understanding of the field of cryptography has traditionally been encrusted with rumor and myth. In modern times (ie, since the introduction of publicly accessbiel high quality crypto systems such as PGP), this regrettable tradition has been continued by exaggerated marketing claims for commercial cryptographic products. Readers are cautioned to take care; for example see the warning note in the reference section below.

In essence, cryptography concerns four main goals. To avoid confusion and the far too common mystical fog about the subject, it is important to be familiar with these purposes and their associated limitations. They are:

  1. message confidentiality: Only an 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 statistical characteristics of the plaintext) as this makes cryptanalysis easier thus making confidentiality less attainable.
  2. message integrity: The recipient should be able to determine if the message has been altered during transmission.
  3. sender authentication: The recipient should be able to identify the sender, and verify that the purported sender actually did send the message.
  4. sender 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 or bluff or lack of interest on the part of the opposition. Users can, and regularly do, find weaknesses in even well-designed cryptograpic schemes from those of high reputation.

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 wish to be anonymous, and would therefore deliberately choose not to bother with non-repudiation. Alternatively, the system may be intended for an environment with limited computing resources, or message confidentiality might not be an issue.

In classical cryptography, messages are typically enciphered and transmitted from one person or group to some other person or group. In modern cryptography, there are many possible options for "sender" or "recipient". Some examples, for real crypto systems in the modern world, include:

  1. a computer program running on a local computer,
  2. a computer program running on a 'nearby' computer which 'provides security services' for users on other nearby systems,
  3. a human being (usually understood as 'at the keyboard'). However, even in this example, the presumed human is not generally taken to actually encrypt or sign or decrypt or authenticate anything. Rather, he or she instructs a computer program to perform these actions. This 'blurred separation' of human action from actions which are presumed (without much consideration) to have 'been done by a human' is a source of problems in crypto system design, implementation, and use. Such problems are often quite subtle and correspondingly obscure; indeed, generally so, even to practicing cryptographers with knowledge, skill, and good engineering sense.

When confusion on these points is present (eg, at the design stage, during implementation, by a user after installation, or ...), failures in reaching each of the stated goals can occur quite easily -- often without notice to any human involved, and even given a perfect cryptosystem. Such failures are most often due to extra-cryptographic issues; each such failure demonstrates that good algorithms, good protocols, good system design, and good implementation do not alone, nor even in combination, provide 'security'. Instead, careful thought is required regarding the entire crypto system design and its use in actual production by real people on actual equipment running 'production' system software (eg, operating systems) -- too often, this is absent or insufficient 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 encryption or cryptanalysis (the science of finding weaknesses in crypto systems). Examples of the latter include Charles Babbage's Crimean War era work on mathematical cryptanalysis of polyalphabetic cyphers, repeated publicly rather later by the Prussian Kasiski. During this time, there was little theoretical foundation for cryptography; rather, understanding of cryptograpy generally consisted of hard-won fragments of knowledge and rules of thumb; see, for example, Auguste Kerckhoffs' crypto writings in the latter 19th century. An increasingly mathematical 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 version of the Enigma system). Both cryptography and cryptanalysis have become far more mathematical since WWII. Even then, it has taken the wide availability of computers, and the Internet as a communications medium, to bring effective cryptography into common use by anyone other than national governments or similarly large enterprises.

Classical Cryptography

The earliest known use of cryptography is found in non-standard hieroglyphs carved into monuments from Egypt's Old Kingdom (ca 4500 years ago). These are not thought to be serious attempts at secret communications, however, but rather to have been attempts at mystery, intrigue, or even amusement for literate onlookers. These are examples of 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, encrypted) way of concealing a dangerous reference; many scholars believe it's a concealed reference to the Roman Empire, or the Emperor Nero, (and so to Roman policies of persecution of Christians) that would have been understood by the initiated (who 'had the codebook'), and yet be safe (or at least somewhat deniable and so less dangerous) if it came to the attention of the authorities. At least for orthodox Christian writing, the need for such concealment ended with Constantine's conversion and the adoption of Christianity as the official religion of the Empire.

The Greeks of Classical times are said to have known of cyphers (eg, the scytale transposition cypher claimed to have been used by the Spartan military). Herodutus tells us of secret messages physically concealed beneath wax on wooden tablets or as a tattoo on a slave's head concealed by regrown hair (see secret writing; these are not properly examples of cryptography). The Romans certainly did (eg, the Caesar cipher and its variations). There is ancient mention of a book about Roman military cryptography (especially Julius Caesar's); it has been, unfortunately, lost.

In India, cryptography was apparently well known. It is recommended in the Kama Sutra as a technique by which lovers can communicate without being discovered. This may imply that cryptanalytic techniques were less than well developed in India ca 500 CE.

Cryptography became (secretly) important still later as a consequence of political competition and religous analysis. For instance, in Europe during and after the Renaissance, citizens of the various Italian states, including the Papacy, were responsible for substantial improvements in cryptographic practice (eg, polyalphabetic cyphers invented by Leon Alberti ca 1465). And in the Arab world, religiously motivated textual analysis of the Koran led to the invention of the frequency analysis technique for breaking monoalphabetic substitution cyphers sometime around 1000 CE.

Cryptography, cryptanalysis, and secret agent betrayal featured in the Babington plot during the reign of Queen Elizabeth I which led to the execution of Mary, Queen of Scots. 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, if possible, 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 ahead (also secretly) after World War I. Marian Rejewski, in Poland, attacked and 'broke' the early German Army Enigma system (an electromechanical rotor cypher machine) using theoretical mathematics in 1932. The break continued up to '39, when changes in the way the German Army's Enigma machines were used required more resources than the Poles could deploy. 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 the assorted networks for which they were used. US Navy cryptographers (with cooperation from British and Dutch cryptographers 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 (an electromechanical 'stepping switch' machine called Purple by the Americans) even 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 encyphered by the various Enigmas. An earlier British term for Ultra had been 'Boniface'.

World War II Cryptography

By World War II mechanical and electromechanical cryptographic cypher machines were in wide use, although where these were impractical manual systems continued to be used. Great advances were made in both practical and mathematical cryptography in this period, all in secrecy. 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, as the relevant US archives have slowly opened, and as assorted memoirs and articles have been published.

The Germans made heavy use (in several variants) of an electromechanical rotor based cypher system known as Enigma. The German military also deployed several mechanical attempts at a one-time pad. Bletchley Park called them the Fish cypherss, and Max Newman and colleagues designed and deployed the world's first programmable digital electronic computer, the Colossus, to help with their cryptanalysis. The German Foreign Office began to use the one-time pad in 1919; some of this traffic was read in WWII partly as the result of recovery of some key material in South America that was insufficiently carefully discarded by a German courier.

The Japanese Foreign Office used a locally developed electrical stepping switch based system (called Purple by the US; see the entry Purple code), 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 TypeX and the American SIGABA; both were electromechanical rotor designs similar in spirit to the Enigma. Neither is known to have been broken by anyone during the war.

Modern Cryptography

The era of modern cryptography really begins 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 solid theoretical basis for cryptography and for cryptanalysis. And with that, cryptography more or less disappeared into secret government communicatiosn organisations such as the NSA. Very little work was again made public until the mid '70s, when everything changed.

1976 saw two major public (ie, non-secret) advances. First was the DES (Data Encryption Standard) submitted by IBM, 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 and other large financial organizations. After 'advice' and modification by the NSA, it was adopted and published as a FIPS Publication (Federal Information Processing Standard) in 1977 (currently at FIPS 46-3). It has been made effectively obsolete by the adoption in 2001 of the Advanced Encryption Standard, also a NIST competition, as FIPS 197. DES was the first publicly accessible cypher algorithm to be 'blessed' by a national crypto agency such as NSA. The release of its design details by NBS stimulated an explosion of public and academic interest in cryptography. DES, and more secure variants of it (such as 3DES or TDES; 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 Rijndael, by two Belgian cryptographers. DES remains in wide use nonetheless, having been incorporated into many national and organizational standards. However, its 56-bit key-size has been shown to be insufficient to guard against brute-force attacks (one such attack, undertaken by cyber civil-rights group The Electronic Frontier Foundation, succeeded in 56 hours -- the story is in Cracking DES, published by O'Reilly and Associates). As a result, use of straight DES encryption is now without doubt insecure for use in new crypto system designs, and messages protected by older crypto systems using DES should also be regarded as insecure. The DES key size (56-bits) was thought to be too small by some even in 1976, perhaps most publicly Whitfield Diffie. There was suspicion that government organizations even then had sufficient computing power to break DES messages.

Second 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, which went far toward solving one of the fundamental problems of cryptography, key distribution. It has become known as Diffie-Hellman key exchange. The article also stimulated the almost immediate public development of a new class of encyphering algorithms, the asymmetric key algorithms.

Prior to that time, all useful modern encryption algorithms had been symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient who must both keep it secret. All of the electromechanical machines used in WWII were of this logical class, as were the Caesar and Atbash cyphers and essentially all cypher and code systems throughout history. The 'key' for a code is, of course, the codebook, which must likewise be distributed and kept secret.

Of necessity, the key in every such system had to be exchanged between the communicating parties in some secure way prior to any use of the system (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, or a loyal carrier pigeon. This requirement rapidly becomes unmanageable when the number of participants increases beyond some (very!) small number, or when (really) secure channels aren't available for key exchange, or when, as is sensible crypto practice keys are changed frequently. In particular, a separate key is required for each communicating pair if no third party is to be able to decrypt their messages. A system of this kind is also known as a private key, secret key, or conventional key cryptosystem. D-H key exchange (and succeeding improvements) made operation of these systems much easier, and more secure, than had ever been possible before.

In contrast, with asymmetric key encryption, there is a pair of mathematically related keys for the algorithm, one of which is used for encryption and the other for decryption. Some, but not all, 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, somewhat confusingly, 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, for those using such algorithms, only one key pair is now needed per recipient (regardless of the number of senders) as possession of a receipient's public key (by anyone whomsoever) does not compromise the 'security' of messages so long as the corresponding private key is not known to any attacker (effectively, this means not known to anyone except the recipient). This unanticipated, and quite surprising, property of some of these algorithms made possible, and made practical, widespread deployment of high quality crypto systems which could be used by anyone at all. Which in turn gave government crypto organizations worldwide a severe case of heartburn; for the first time ever, those outside that fraternity had access to cryptography that wasn't readily breakable by the 'snooper' side of those organizations. Considerable controversy, and conflict, began immediately. It has not yet subsided. In the US, for example, exporting strong cryptography remains illegal; cryptographic methods and techniques are classified as munitions. Until 2001 'strong' crypto was defined as anything using keys longer than 40 bits -- the definition was relaxed thereafter. (See S Levy's Crypto for a journalistic account of the policy controversy in the US).

Note, however, that it has NOT been proven impossible, for any of the good public/private asymmetric key algorithms, that a private key (regardless of length) can be deduced from a public key (or vice versa). Informed observers believe it to be currently impossible (and perhaps forever impossible) for the 'good' asymmetric algorithms; no workable 'companion key deduction' techniques have been publicly shown for any of them. Note also that some asymmetric key algorithms have been quite thoroughly broken, just as many symmetric key algorithms have. There is no special magic attached to using algorithms which require two keys.

In fact, some of the well respected, and most widely used, public key / private key algorithms can be broken by one or another cryptanalytic attack and so, like other encryption algorithms, the protocols within which they are used must be chosen and implemented carefully to block such attacks. Indeed, all can be broken if the key length used is short enough to permit practical brute force key search; this is inherently true of all encryption algorithms using keys, including both symmetric and asymmetric algorithms.

This is an example of the most 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 by informed observers to be enough, and possibly even enough 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.

Non-secret Encryption

Asymmetric key cryptography, D-H key exchange, and the best known of the public key / private key algorithms (ie, what is usually called the RSA algorithm), all seem to have been developed at a UK intelligence agency before the public announcement by Diffie and Hellman 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 at GCHQ during the 1960s and 1970s which eventually led to schemes essentially identical to RSA encryption and to 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 cryptographic algorithms of various kinds

Hash functions, aka message digest functions, cryptographic hash functions

  • MD5 (one of a series of message digest algorithms by Prof Ron Rivest of MIT; 128 bit digest)
  • SHA-1 (developed at NSA 160-bit digest; the first released version was defective and replaced by this one; NSA has released several variants with longer 'digest' lengths)
  • RIPEMD-160 (developed in Europe for the RIPE project; 160-bit digest)
  • Tiger (by Ross Anderson et al)

Free/Open Source crypto systems (ie, algorithms + protocols + system design)

  • PGP (a name shared by several programs, some of which, especially recently, have not been Free Software in the GNU sense)
  • GPG
  • SSH
  • IPSec / Free S/WAN

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

General note on cryptographic references: There is a great amount of myth and misunderstanding in wide circulation about topics cryptographic. Some is grossly wrong, some is 'merely' subtly misleading, much of it is plausible to the crypto newcomer and even to the somewhat crypto experienced or informed. There is also a very great selection of poorly done, non-secure crytographic software on the market (purchaseware, shareware, freeware, journalware, xyzware). Readers, buyers, and users should exercise substantially more than the usual caution lest they lose one, two, or all of the reasons they have bothered with cryptography at all (see the article above for the goals of cryptography). At the time this sentence was written, each of the following references is reliable. Mostly. Consider that none covers up-to-date secret government cryptography (at minimum, publishing schedules do not permit it, more generally NSA and brethren don't talk), none is even complete for material available before publication, and none is error free. All of this, plus individual differences in comprehension of a complex field, may produce considerable distortions in your understanding of the current state of the art in cryptography. Nevertheless, try these references first if you wish to minimize those distortions.
  • The Beginner's Guide to Cryptography - This website gives a (quite) elementary overview of a few basic areas of cryptography.
  • An Introduction to the Use of Encryption - A useful and fairly non-technical introduction to the subject.
  • Ferguson, Niels, and Schneier, Bruce - Practical Cryptography, Wiley, 2003, ISBN 0471223573. Up to date cryptography reference. Covers both algorithms and protocols. This is an in depth consideration of one cryptographic problem, including paths not taken and some reasons why. Most of the material is not otherwise available in a single source. Some is not otherwise available. In a sense, a follow-up to 'Applied Cryptography'.
  • Schneier, Bruce - Applied Cryptography, 2 ed, Wiley, ISBN 0471117099. The best single volume available covering modern cryptographic practice and possibilities. About as comprehensive as a single volume could have been. Well written, not overly mathematical, and so accessible -- mostly -- to the non-technical.
  • Schneier, Bruce - Secrets and Lies, Wiley, ISBN 0471253111, a discussion of the context within which cryptography and cryptosystems work. Meta-cryptography, if you will. Required reading for would-be cryptographers, and nearly so for all cryptography users.
  • Ross Anderson -- Security Engineering, Wiley, advanced coverage of computer security issues, including cryptography, by one of its foremost practicioners, and most likely its best writer. Covers much more than merely cryptography. Brief on most topics due to the breadth of coverage. Exceptionally clearly written.
  • Bamford, James - The Puzzle Palace : A Report on America's Most Secret Agency ISBN 0140067485, and the more recent Body of Secrets. The best of a quite small group of books about the US Government's NSA. Most are inadequate, and untrustworthy, for various reasons, including an active reluctance to permit accurate information to be released in any form.
  • A. J. Menezes, P. C. van Oorschot and S. A. Vanstone - Handbook of Applied Cryptography ISBN 0849385237 (online version). Equivalent to Applied Cryptography in many ways, but seriously mathematical. For the technically inclined. Covers few meta-cryptographic topics, such as crypto system design.
  • Kahn, David - The Codebreakers ISBN 0684831309 The best available single volume source for cryptographic history, at least for events up to the mid '60s (ie, to just before DES and the public release of asymmetric key cryptography). The added chapter on more recent developments (in the most recent edition) is regrettably far too thin. See also his other publications on cryptography, and cryptographic history, which have been uniformly excellent.
  • Piper, Fred and Sean Murphy - Cryptography : A Very Short Introduction ISBN 0192803158 This book quickly sketches out the major goals, uses, methods, and developments in cryptography.
  • Singh, Simon - The Code Book ISBN 1857028899. An anecdotal introduction to the history of cryptography, but much better than such an approach might be expected to produce. Covers more recent material than does Kahn's The Codebreakers. Well written. Sadly, the included cryptanalytic contest has been won and the prize awarded; the cyphers are still worth having a go at, however.

Related topics

Echelon, Enigma, Espionage, IACR, Purple code, Ultra, Security engineering, SIGINT, Steganography, Cryptographers, SSL, Quantum Cryptography, Crypto-anarchism, Cypherpunk, RSA, Key authentication, ID-based cryptography.

External links




copyright © 2004 FactsAbout.com