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 concealed in ciphers that are much more difficult to read for an unauthorized person than for a legitimate reader employing the decryption key.

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. Furthermore, they should be able to verify that the sender did actually send the message.
non-repudiation: The sender should not be able to deny sending the message.

Not all cryptographic systems and algorithms achieve all of the above goals. Some are not 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.

Although cryptography has a long and complex history, it wasn't until the 19th centry that it developed anything more than ad hoc approaches to either cryptanalysis (eg, C Babbage) or encryption (Kerckoffs). This increasingly mathematically theoretical trend accelerated up to WWII (notably in W Freidman's applications of statistical techniques to cryptography) and became essentially completly mathematical afterwards. Even then, it has taken the Internet to bring effective cryptography into common use by anyone other than national governments.

Classical Cryptography

The earliest use of cryptography can be found with the use of non-standard hieroglyphics on monuments by the Egyptians around 1900 BCE. Hebrew scholars also made use of simple substitution ciphers (such as the Atbash cipher) beginning perhaps around 500 to 600 BCE.

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 Bazeries) has shed some light on the identity of that 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. Fortunately, cryptography was also invoved in setting him free.

Mathematical cryptography leaped ahead before WWII. M Rejewski in Poland attacked and broke the German Enigma system using purely mathematical techniques, and his work was extended by A Turing and others at Bletchley Park beginning in 1939. US Navy cryptographers (with help from the British and the Dutch) broke into several Japanese Navy crypto systems leading most famously to the US victory at Midway. The US Army SIS group managed to break the highest security Japanese diplomatic system (called Purple by the Americans) before the War began. The Americans referred to the intelligence resulting from cryptanalysis as Magic. The British eventually settled on Ultra for intelligence resulting from cryptanalysis.

World War II Cryptography

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

The Germans made heavy use of an electro-mechanical system known as Enigma, the Japanese Foreign Office used the independently developed Purple code or J-machine.

Modern Cryptography

The era of modern cryptography started with Claude Shannon, arguably the father of mathematical cryptography. In 1949 he published the paper Communication Theory of Secrecy Systems. This, in addition to his other works on information and communication theory established a strong theoretical basis for cryptography.

1976 saw two major advances. First was the DES (Data Encryption Standard) developed by IBM and the NSA in an effort to develop secure banking facilities (DES was later published as a FIPS (Federal Information Processing Standard) in 1977). DES was the first widely used computer cipher approved by a national crypto agency such as NSA which was accessible to the public. 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) are still used today, although DES was effectively replaced by AES (Advanced Encryption Standard) in 2001.

Secondly, and perhaps more importantly, was the publication of the paper New Directions in Cryptography by Whitfield Diffie and Martin Hellman. This paper introduced a radical 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 encryption algorithms were symmetric key algorithms, in which the same key must be used by both the sender and the receipient. The 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. This rapidly becomes unmanageable when the number of participants increases beyond some small number. In particular, a separate key is required for each communicating pair if other parties are not to decrypt their messages. A system of this kind is also known as a "private key cryptosystem."

In asymmetric key cryptography, there are a pair of related keys, 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 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 emphasise that there are two distinct keys with different properties. Only one key pair is now needed per receiver as possession of the public key does not compromise the security of the private key. It is not been proved, for good algorithms, that the private key cannot be deduced from the public key, but informed observers believe it to be so. Some of the well known public key / private key algorithms can be broken by on or another cryptanalytic attack and so, like essentially all encryption algorithms, the protocols in which they are used must be chosen and implemented carefully.

However, both asymmetric key cryptography and the best known of the public key / private key algorithms (usually termed RSA) seem to have been developed by a military agency before public research caught up. On December 17, 1997, GCHQ released documents claiming that they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were published during the 1960s and 1970s which eventually led to schemes similar to RSA and Diffie-Hellman in 1973 and 1974.