History of cryptology

From Citizendium
Jump to navigation Jump to search
This article may be deleted soon.
To oppose or discuss a nomination, please go to CZ:Proposed for deletion and follow the instructions.

For the monthly nomination lists, see
Category:Articles for deletion.


This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

Cryptology (the science of secrets, from Greek) is the general term that encompasses both cryptography (the study of techniques for keeping secrets) and cryptanalysis (codebreaking, acquiring secrets without authorisation). The field has a long history; secret messages were used in ancient Egypt and China 4000 years ago.


Before the modern era, cryptography was concerned solely with message confidentiality (i.e. encryption) — conversion of messages from a comprehensible form into an incomprehensible one and back again at the other end, rendering it unreadable without secret knowledge (namely, the key). In recent decades, the field has expanded beyond confidentiality concerns to include techniques for authentication, digital signatures, interactive proofs, and secure computation.

The earliest forms of secret writing required little more than pen and paper. The main classical cipher types are transposition ciphers, which rearrange the order of letters in a message (e.g. 'help me' becomes 'ehpl em'); and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters (e.g. 'fly at once' becomes 'gmz bu podf' by replacing each letter with the one following it in the alphabet). Simple versions of either offered little confidentiality. An early and simple substitution cipher was the Caesar cipher, in which each letter in the plaintext was replaced by a letter some fixed number of positions further down the alphabet. It was named after Julius Caesar who used the cipher with a shift of 3 in order to communicate with his generals during his various military campaigns.

Encryption attempted to ensure secrecy in important communications, such as those of spies, military leaders, and diplomats, but it also had religious applications. For instance, early Christians used cryptography to obfuscate parts of their religious writings to avoid near certain persecution they would have faced had they been less obscured; famously, 666, the Number of the Beast from the Book of Revelation, is sometimes thought to be a ciphertext referring to the Roman Emperor Nero, one of whose policies was persecution of Christians[1]. There is record of several, even earlier, Hebrew ciphers as well. Cryptography is also recommended in the Kama Sutra as a way for lovers to communicate without discovery[2].

Steganography

Steganography (which is hiding a message so as to make its existence undetectable) was also first developed in ancient times. An early example, from Herodotus, concealed a message - a tattoo on a slave's head - by regrown hair[3]. More modern examples of steganography include the use of invisible ink, microdots, and digital watermarks to conceal information .

Cryptanalysis and communications intelligence

Ciphertexts produced by classical ciphers reveal statistical information about the plaintext, which can be used to break them. After the Arab discovery of frequency analysis (around the year 1000), nearly all such ciphers became more or less breakable by an informed attacker. Such classical ciphers still enjoy popularity today, though mostly as puzzles (see cryptogram). Essentially all ciphers remained vulnerable to cryptanalysis using this technique until the invention of the polyalphabetic cipher by Leon Battista Alberti around the year 1467, in which different parts of the message (often each successive plaintext letter) are enciphered using a different key. In the polyalphabetic Vigenère cipher, for instance, encryption uses a key word, which controls letter enciphering depending on which letter of the key word is used. Despite this improvement, polyalphabetic ciphers of this type remained partially vulnerable to frequency analysis techniques[3].

Although frequency analysis is a powerful and general technique, encryption was still often effective in practice: many a would-be cryptanalyst was unaware of the technique. Breaking a message without frequency analysis essentially required knowledge of the cipher used, thus encouraging espionage, bribery, burglary, defection, etc. to discover it. It was finally recognized in the 19th century that secrecy of a cipher's algorithm is not a sensible, nor practical, safeguard: in fact, any adequate cryptographic scheme (including ciphers) should still be secure even if the adversary knows the cipher itself. Secrecy of the key should be alone sufficient for confidentiality when it is attacked. This fundamental principle was first explicitly stated in 1883 by Auguste Kerckhoffs and is called Kerckhoffs' Principle; alternatively and more bluntly, it was restated by Claude Shannon as Shannon's Maxim, "The enemy knows the system".

Mechanical and electronic aids to cryptography

Various physical devices and aids have been used to assist with ciphers. One of the earliest may have been the scytale of ancient Greece, a rod supposedly used by the Spartans as an aid for a transposition cipher. In medieval times, other aids were invented such as the cipher grille, also used for a kind of steganography. With the invention of polyalphabetic ciphers came more sophisticated aids such as Alberti's own cipher disk, Johannes Trithemius' tabula recta and Thomas Jefferson's cylinder (reinvented by Bazeries around 1900). Early in the 20th century, several mechanical encryption/decryption devices were invented, and many patented, including rotor machines — most famously the Enigma machine used by Germany in World War II. The ciphers implemented by the better of these designs brought about a substantial increase in cryptanalytic difficulty[4].

Cryptography meets computing

The development of digital computers and electronics after WWII made possible much more complex ciphers. Furthermore, computers allowed for the encryption of any kind of data that is represented by computers in binary unlike classical ciphers which only encrypted written text, dissolving the need for a linguistic approach to cryptanalysis. Many computer ciphers can be characterised by their operation on binary bits (sometimes in groups or blocks), unlike classical and mechanical schemes, which generally manipulate traditional characters (i.e. letters and digits). However, computers have also assisted cryptanalysis, which has compensated to some extent for increased cipher complexity. Nonetheless, good modern ciphers have stayed ahead of cryptanalysis: it is usually the case that use of a quality cipher is very efficient, while breaking it requires an effort many orders of magnitude larger, making cryptanalysis so inefficient and impractical as to be effectively impossible.

Extensive open academic research into cryptography is relatively recent — it began only in the mid-1970s with the public specification of DES (the Data Encryption Standard), the Diffie-Hellman paper,[5] and the public release of the RSA algorithm. Since then, cryptography has become a widely used tool in communications, computer networks, and computer security generally. The security of many modern cryptographic techniques is based on the difficulty of certain computational problems, such as the integer factorisation problem or the discrete logarithm problem. In many cases, there are proofs that cryptographic techniques are secure if a certain computational problem cannot be solved efficiently.[6] With one notable exception - the one-time pad - these contingent proofs are the best available for cryptographic algorithms and protocols.

References

  1. Eerdmans Commentary on the Bible, James D G Dunn, John W Rogerson, eds., Wm. B. Eerdmans Publishing, 2003, ISBN 0-8028-3711-5
  2. Kama Sutra, Sir Richard F. Burton, translator, Part I, Chapter III, 44th and 45th arts.
  3. 3.0 3.1 Kahn, David (1967), The Codebreakers, ISBN 0-684-83130-9
  4. James Gannon, Stealing Secrets, Telling Lies: How Spies and Codebreakers Helped Shape the Twentieth Century, Washington, D.C., Brassey's, 2001, ISBN 1-57488-367-4.
  5. Diffie, Whitfield & Martin Hellman (Nov. 1976), "pdf New Directions in Cryptography", IEEE Transactions on Information Theory IT-22 pages = 644-654
  6. Goldreich, Oded (2001), Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press, ISBN 0-521-79172-3