• Bulgarian: криптография
• Chinese: 密码学 名词
• Czech: kryptografie
• Danish: kryptografi
• Dutch: cryptografie , geheimschrift
• Finnish: kryptografia, salaustekniikka
• French: cryptographie
• German: Kryptographie
• Japanese: 暗号論 (angōron)
• Portuguese: criptografia

Cryptography (or cryptology; derived from Greek κρύπτω krýpto "hidden" and the verb γράφω gráfo "to write" or λέγειν legein "to speak") is the practice and study of hiding information. In modern times, cryptography is considered to be a branch of both mathematics and computer science, and is affiliated closely with information theory, computer security, and engineering. Cryptography is used in applications present in technologically advanced societies; examples include the security of ATM cards, computer passwords, and electronic commerce, which all depend on cryptography.

Terminology

Until modern times, cryptography referred almost exclusively to encryption, the process of converting ordinary information (plaintext) into unintelligible gibberish (i.e., ciphertext).

The study of characteristics of languages which have some application in cryptology, i.e. frequency data, letter combinations, universal patterns, etc. is called Cryptolinguistics.

History of cryptography and cryptanalysis

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 by interceptors or eavesdroppers without secret knowledge (namely, the key needed for decryption of that message). In recent decades, the field has expanded beyond confidentiality concerns to include techniques for message integrity checking, sender/receiver identity authentication, digital signatures, interactive proofs, and secure computation, amongst others.

The earliest forms of secret writing required little more than local pen and paper analogs, as most people could not read. More literacy, or opponent literacy, required actual cryptography. The main classical cipher types are transposition ciphers, which rearrange the order of letters in a message (e.g., 'help me' becomes 'ehpl em' in a trivially simple rearrangement scheme), 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 English alphabet). Simple versions of either offered little confidentiality from enterprising opponents, and still don't. An early 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 is reported to have used it, with a shift of 3, to communicate with his generals during his military campaigns, just like EXCESS-3 code in boolean algebra.

Encryption attempts to ensure secrecy in communications, such as those of spies, military leaders, and diplomats. There is record of several early Hebrew ciphers as well. Cryptography is recommended in the Kama Sutra as a way for lovers to communicate without inconvenient discovery. Steganography (i.e., hiding even the existence of a message so as to keep it confidential) was also first developed in ancient times. An early example, from Herodotus, concealed a message - a tattoo on a slave's shaved head - under the regrown hair. More modern examples of steganography include the use of invisible ink, microdots, and digital watermarks to conceal information.

Ciphertexts produced by classical ciphers (and some modern ones) always reveal statistical information about the plaintext, which can often be used to break them. After the discovery of frequency analysis (perhaps by the Arab polymath al-Kindi) in the 9th century, nearly all such ciphers became more or less readily 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, most clearly by Leon Battista Alberti around the year 1467 (though there is some indication of earlier Arab knowledge of them). Alberti's innovation was to use different ciphers (i.e., substitution alphabets) for various parts of a message (perhaps for each successive plaintext letter in the limit). He also invented what was probably the first automatic cipher device, a wheel which implemented a partial realization of his invention. In the polyalphabetic Vigenère cipher, encryption uses a key word, which controls letter substitution depending on which letter of the key word is used. In the mid 1800s Babbage showed that polyalphabetic ciphers of this type remained partially vulnerable to frequency analysis techniques. The ciphers implemented by better quality examples of these designs brought about a substantial increase in cryptanalytic difficulty after WWI.

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 represented by computers in any binary format, unlike classical ciphers which only encrypted written language texts, thus dissolving much of the utility of a linguistic approach to cryptanalysis. Many computer ciphers can be characterized by their operation on binary bit sequences (sometimes in groups or blocks), unlike classical and mechanical schemes, which generally manipulate traditional characters (i.e., letters and digits) directly. 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 typically the case that use of a quality cipher is very efficient (i.e., fast and requiring few resources), while breaking it requires an effort many orders of magnitude larger than before, 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) by the US Government's National Bureau of Standards, the Diffie-Hellman paper, 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 present security level of many modern cryptographic techniques is based on the difficulty of certain computational problems, such as the integer factorisation or the discrete logarithm problems. In many cases, there are proofs that cryptographic techniques are secure if a certain computational problem cannot be solved efficiently. With one notable exception -— the one-time pad —- these proofs are contingent, and thus not definitive, but are currently the best available for cryptographic algorithms and protocols.

As well as being aware of cryptographic history, cryptographic algorithm and system designers must also sensibly consider probable future developments in their designs. For instance, continuous improvements in computer processing power have increased the scope of brute-force attacks, thus when specifying key lengths, the standard is similarly advancing. The potential effects of quantum computing are already being considered by some cryptographic system designers; the announced imminence of small implementations of these machines is making the need for this preemptive caution fully explicit.

Essentially, prior to the early 20th century, cryptography was chiefly concerned with linguistic patterns. Since then the emphasis has shifted, and cryptography now makes extensive use of mathematics, including aspects of information theory, computational complexity, statistics, combinatorics, abstract algebra, and number theory. Cryptography is also a branch of engineering, but an unusual one as it deals with active, intelligent, and malevolent opposition (see cryptographic engineering and security engineering); most other kinds of engineering need deal only with neutral natural forces. There is also active research examining the relationship between cryptographic problems and quantum physics (see quantum cryptography and quantum computing).

Modern cryptography

The modern field of cryptography can be divided into several areas of study. The chief ones are discussed here; see Topics in Cryptography for more.

Symmetric-key Cryptography

Symmetric-key cryptography refers to encryption methods in which both the sender and receiver share the same key (or, less commonly, in which their keys are different, but related in an easily computable way). This was the only kind of encryption publicly known until June 1976. Despite its deprecation as an official standard, DES (especially its still-approved and much more secure triple-DES variant) remains quite popular; it is used across a wide range of applications, from ATM encryption to e-mail privacy and secure remote access. Many other block ciphers have been designed and released, with considerable variation in quality. Many have been thoroughly broken. See Category:Block ciphers.

Stream ciphers, in contrast to the 'block' type, create an arbitrarily long stream of key material, which is combined with the plaintext bit-by-bit or character-by-character, somewhat like the one-time pad. In a stream cipher, the output stream is created based on an internal state which changes as the cipher operates. That state change is controlled by the key, and, in some stream ciphers, by the plaintext stream as well. RC4 is an example of a well-known, and widely used, stream cipher; see Category:Stream ciphers. A public key system is so constructed that calculation of one key (the 'private key') is computationally infeasible from the other (the 'public key'), even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair. The historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".

In public-key cryptosystems, the public key may be freely distributed, while its paired private key must remain secret. The public key is typically used for encryption, while the private or secret key is used for decryption. Diffie and Hellman showed that public-key cryptography was possible by presenting the Diffie-Hellman key exchange protocol.

In 1997, it finally became publicly known that asymmetric key cryptography had been invented by James H. Ellis at GCHQ, a British intelligence organization, and that, in the early 1970s, both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively).

The Diffie-Hellman and RSA algorithms, in addition to being the first publicly known examples of high quality public-key algorithms, have been among the most widely used. Others include the Cramer-Shoup cryptosystem, ElGamal encryption, and various elliptic curve techniques. See Category:Asymmetric-key cryptosystems.

• List of cryptographers
• :Category:Cryptographers
• Books on cryptography
• List of important publications in computer science#Cryptography
• List of open problems in computer science#Cryptography

References

Further reading

• Handbook of Applied Cryptography by A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone CRC Press, (PDF download available), somewhat more mathematical than Schneier's Applied Cryptography.
• Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell. http://www.cs.umd.edu/~jkatz/imc.html.
• Introduction to Modern Cryptography by Phillip Rogaway and Mihir Bellare, a mathematical introduction to theoretical cryptography including reduction-based security proofs. PDF download.
• Stealing Secrets, Telling Lies: How Spies and Codebreakers Helped Shape the Twentieth Century, by James Gannon.
• Cryptonomicon by Neal Stephenson (novel, WW2 Enigma cryptanalysis figures into the story, though not always realistically).
• Alvin's Secret Code by Clifford B. Hicks (children's novel that introduces some basic cryptography and cryptanalysis).
• In Code: A Mathematical Journey by Sarah Flannery (with David Flannery). Popular account of Sarah's award-winning project on public-key cryptography, co-written with her father.
• Cryptography and Mathematics by Bernhard Esslinger, 200 pages, part of the free open-source package Cryptool, http://www.cryptool.com.
• Ibrahim A. Al-Kadi ,"The origins of cryptology: The Arab contributions”, Cryptologia, 16(2) (April 1992) pp. 97–126.
• Andreas Pfitzmann: Security in IT Networks: Multilateral Security in Distributed and by Distributed Systems
• Introduction to Cryptology Excellent coverage of many classical ciphers and cryptograpy concepts and of the "modern" DES and RSA systems.

External links

• AttackPrevention Resource for Cryptography Whitepapers, Tools, Videos, and Podcasts.
• Handbook of Applied Cryptography by A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone (PDF download available), somewhat more mathematical than Schneier's book.
• Cryptography: The Ancient Art of Secret Messages by Monica Pawlan - February 1998
• sci.crypt mini-FAQ
• NSA's CryptoKids.
• RSA Laboratories' Frequently Asked Questions About Today's Cryptography

cipher, code, coded message, coup de plume, criticism, cryptanalysis, cryptoanalysis, cryptoanalytics, cryptogram, cryptograph, cryptographer, cryptology, diagnostics, engrossment, epigraphy, exegetics, hermeneutics, ink spilling, inkslinging, inscription, invisible ink, lettering, lexicography, literary criticism, macrography, metoposcopy, micrography, oneirology, paleography, pathognomy, pen, pen-and-ink, pencil driving, physiognomics, physiognomy, scrivenery, scrivening, secret language, secret writing, semeiology, semeiotics, sympathetic ink, symptomatology, textual criticism, tropology, typewriting, typing, writing