Cryptography
From Wikipedia, the free encyclopedia that anyone can edit
Cryptography is the field concerned with linguistic and mathematical techniques for securing information, particularly in communications. Historically, cryptography was concerned solely with encryption; that is, means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable without secret knowledge. Encryption was used primarily to ensure secrecy in important communications, such as those of spies, military leaders, and diplomats. In recent decades, however, the field of cryptography has expanded its remit: modern cryptography provides mechanisms for more than just keeping secrets and has a variety of applications including, for example, authentication, digital signatures, electronic voting and digital cash. Moreover, people without extraordinary needs for secrecy use cryptographic technology, which is often built transparently into much of computing and telecommunications infrastructure.
Cryptography is an interdisciplinary subject, drawing from several fields. Older forms of cryptography were chiefly concerned with patterns in language. More recently, the emphasis has shifted, and cryptography makes extensive use of mathematics, particularly discrete mathematics, including topics from number theory, information theory, computational complexity, statistics and combinatorics. Cryptography is also considered a branch of engineering, but it is considered to be an unusual one as it deals with active, intelligent and malevolent opposition (see cryptographic engineering and security engineering). Cryptography is a tool used within computer and network security.
An associated field is steganography — the study of hiding the very existence of a message, and not necessarily the contents of the message itself (for example, microdots, or invisible ink).
Contents |
Terminology
The study of how to circumvent the use of cryptography is called cryptanalysis, or codebreaking. Cryptography and cryptanalysis are sometimes grouped together under the umbrella term cryptology, encompassing the entire subject. In practice, the term cryptography (from the Greek kryptós, "hidden", and gráphein, "to write") is often used to refer to the field as a whole; crypto is an informal abbreviation. The first recorded usage of the word 'cryptography' occurs in Sir Thomas Browne's Discourse of 1658 entitled The Garden of Cyrus: "the strange Cryptography of Gaffarel in his Starrie Booke of Heaven".
Encryption (or enciphering) is the process of converting ordinary information (plaintext) into an unreadable form, termed ciphertext, or a cryptogram. Decryption, or deciphering, is the reverse process, recovering the plaintext back from the ciphertext. A cipher (sometimes spelt cypher) is an algorithm for encryption and decryption. The exact operation of a cipher is normally controlled by a key — some secret piece of information that customizes how the ciphertext is produced. Cryptographic protocols specify the details of how ciphers (and other cryptographic primitives) are to be used to achieve specific tasks. A suite of protocols, ciphers, key management, user-prescribed actions implemented together as a system constitute a cryptosystem.
In ordinary parlance, a (secret) "code" is often used synonymously with "cipher". In cryptography, however, the term has a specialised technical meaning: Codes are a historical method which involves substituting larger units of text, typically words or phrases (for example, "apple pie" replaces "attack at dawn"). In contrast, classical ciphers usually substitute or rearrange individual letters (or small groups of letters) — for example, "attack at dawn" becomes "buubdl bu ebxo" by substitution.
Cryptanalysis
Main article: Cryptanalysis
The goal of cryptanalysis is to find some weaknesses or insecurity in a cryptographic scheme. Cryptanalysis might be undertaken by a hostile attacker, attempting to subvert a system; or by the system's designer (or others) wishing to evaluate whether a system is secure.
There are a wide variety of cryptanalytic attacks, and they can be classified in several ways. One distinction concerns what an attacker can know and do in order to learn secret information. For example, does the cryptanalyst have access only to the ciphertext? Does he also know or can he guess some corresponding plaintexts? Or even: Can he choose arbitrary plaintexts to be encrypted? These scenarios correspond to ciphertext only, known plaintext and chosen plaintext attacks, respectively.
While pure cryptanalysis uses weaknesses in the algorithms themselves, other attacks are based upon the implementation, known as side-channel attacks. If a cryptanalyst has access to, say, the amount of time the algorithm took to encrypt a number of plaintexts, he may be able to use a timing attack to break a cipher that is otherwise resistant to analysis. An attacker also might consider studying the pattern and length of messages to derive valuable information; this is known as traffic analysis.
If a cryptosystem uses a key derived from a password, it may be at risk of exhaustive search, due to the insufficient size or randomness of passwords. This is a common weak point in cryptographic systems. For network applications, a password-authenticated key agreement protocol can address some of the limitations of passwords. For standalone applications, either a secure means for storing the password-derived data and/or a passphrase is often recommended.
Linear and differential cryptanalysis are general methods for symmetric key cryptography. When cryptography relies on hard mathematical problems, as is usually the case in asymmetric cryptography, algorithms for tasks such as factoring become potential tools for cryptanalysis.
History of cryptography
Main article: History of cryptography
Cryptography has had a long and colourful history. Generally, the earliest forms of secret writing (now collectively termed classical cryptography) required only pen and paper. The two main categories of classical ciphers are transposition ciphers, which rearrange the order of letters in a message, and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters. One of the earliest and simplest substitution ciphers was the Caesar cipher, used by Julius Caesar. Text encrypted by classical ciphers tends to reveal a certain statistical information about the plaintext. By using this information, classical ciphers are easily broken (e.g. by frequency analysis). Classical ciphers still enjoy popularity today, though mostly as puzzles (see cryptogram).
Various devices and aids have been used for encryption. One of the earliest may have been the scytale. Early in the 20th century, several mechanical devices were invented for performing encryption, including rotor machines — most famously the Enigma machine used by Germany in World War II. The ciphers implemented by these machines brought about a significant increase in the complexity of cryptanalysis.
With the advent of digital computers and electronics, very complex ciphers could be implemented. A characteristic of computer ciphers is that they operate on binary strings, unlike classical and mechanical schemes, which use an alphabet of around 26 letters (depending on the language). Computer ciphers are also much more resistant to cryptanalysis; few are susceptible to a ciphertext-only attack.
Extensive academic research into modern cryptography is relatively recent — it only began in the open community during the 1970s with the specification of the Data Encryption Standard (DES) and the invention of RSA. Since then, cryptography has become a widely-used tool in communications and computer security.
As well as noting lessons from its history, cryptographers are also careful to consider the future. Moore's law is routinely taken into account when specifying key lengths, and the potential effects of quantum computing have already been considered.
Secure communications
See also: Information security
Cryptography is commonly used for securing communications. Desired properties can include:
- Confidentiality, also known as secrecy: only an authorised recipient should be able to extract the contents of the message from its encrypted form. Otherwise, it should not be possible to obtain any significant information about the message contents.
- 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.
- Anti-replay: the message should not be allowed to be sent multiple times to the recipient without the sender knowing.
- Proof of delivery: the sender should be able to prove the recipient received the message.
Cryptography can provide mechanisms to help achieve all of the above. However, some goals are not always necessary, practical or even desirable in some contexts. For example, the sender of a message may wish to remain anonymous; clearly non-repudiation would be inappropriate in that case.
Symmetric key cryptography
Main article: Symmetric key algorithm
Symmetric key ciphers either use the same key for encryption and decryption, or the key used for decryption is easily calculated from the key used for encryption. Other terms include secret-key, private-key, one-key and single-key cryptography.
Symmetric key ciphers can be broadly grouped into block ciphers and stream ciphers. Stream ciphers encrypt one bit at a time, in contrast to a block cipher, which operates on a group of bits (a "block") of a certain length all in one go. Depending on the mode of operation, block ciphers can be implemented as self-synchronizing stream ciphers (CFB mode). Likewise, stream ciphers can be made to work on individual blocks of plaintext at a time. Thus, there is some duality between the two. The block ciphers DES, IDEA and AES, and the stream cipher RC4, are among the most well-known symmetric key ciphers.
Other cryptographic primitives are sometimes classified as symmetric cryptography:
- Cryptographic hash functions produce a hash of a message. While it should be easy to compute, it must be impossible to invert (one-way), and given a hash, it must be computationally difficult to find a message that computes to that hash (collision). Other properties are usually needed as well. MD5 and SHA-1 are well-known hash functions.
- Message authentication codes (MACs), also known as keyed-hash functions, are similar to hash functions, except that a key is needed to compute the hash. As the name suggests, they are commonly used for message authentication. They are often constructed from other primitives, such as block ciphers, unkeyed-hash functions or stream ciphers.
Public key cryptography
Main article: Public key cryptography / Asymmetric key algorithm
Symmetric key encryption has a troublesome drawback — two people who wish to exchange confidential messages must share a secret key. The key must be exchanged in a secure way, and not by the means they would normally communicate. This is usually inconvenient, and public-key (or asymmetric) cryptography provides an alternative. In public key encryption there are two keys used, a public and a private key, with the public key for encryption and the private key for decryption. It must be difficult to derive the private key from the public key. This means that someone can freely send their public key out over an insecure channel and yet be sure that only they can decrypt messages encrypted with it.
Public key algorithms are usually based on hard computational problems. RSA, for example, relies on the (conjectured) difficulty of factorisation. For efficiency reasons, hybrid encryption systems are used in practice; a key is exchanged using a public-key cipher, and the rest of the communication is encrypted using a symmetric-key algorithm (which is typically much faster). Elliptic curve cryptography is a type of public-key algorithm that may offer efficiency gains over other schemes.
Asymmetric cryptography also provides mechanisms for digital signatures, which are a way to establish with high confidence (under the assumption that the relevant private key has not been compromised in any way) that the message received was sent by the claimed sender. Such signatures are often, in law or by implicit inference, seen as the digital equivalent of physical signatures on paper documents. In a technical sense, they are not as there is no physical contact nor connection between the "signer" and the "signed". Properly used high quality designs and implementations are capable of a very high degree of assurance, likely exceeding any but the most careful physical signature. Examples of digital signature protocols include DSA and ElGamal signatures. Digital signatures are central to the operation of public key infrastructure and many network security schemes (e.g., Kerberos, most VPNs, etc). Like encryption, hybrid algorithms are typically used in practice; rather than signing an entire document, a cryptographic hash of the document is signed instead.
Asymmetric cryptography also provides the foundation for password-authenticated key agreement and zero-knowledge password proof techniques. This is important in light of empirical and theoretical proof that secure password-only authentication over a network cannot be achieved with just symmetric cryptography and hash functions.
Other topics
See also: Topics in cryptography
The security of all practical encryption schemes remains unproven, both for symmetric and asymmetric schemes. For symmetric ciphers, confidence gained in an algorithm is usually anecdotal — e.g. no successful attack has been reported on an algorithm for several years despite intensive analysis. Such a cipher might also have provable security against a limited class of attacks. For asymmetric schemes, it is common to rely on the difficulty of the associated mathematical problem, but this, too, is not provably secure.
Cryptography has a cipher with a strong proof of security: the one-time pad. However, it requires keys (at least) as long as the plaintext, so it is widely considered too cumbersome to use in practice.
When the security of a system fails, it is rare that a weakness in the cryptographic algorithms is exploited. More often, it is a mistake in the implementation, the protocols used or some other human error. The study of how best to implement and integrate cryptography is a field in itself, see: cryptographic engineering, security engineering and cryptosystem.
Cryptography can be used to implement various protocols: zero-knowledge proof, secure multiparty computation and secret sharing, for example.
Cryptography can be used to implement digital rights management.
References
- 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.
- David Kahn, The Codebreakers, 1967, ISBN 0684831309.
- A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography ISBN 0849385237 [1].
- Bruce Schneier, Applied Cryptography, 2nd edition, Wiley, 1996, ISBN 0471117099.
See also
- Topics in cryptography — an analytical list of articles and terms.
- Books on cryptography — an annotated list of suggested readings.
- List of cryptographers — an annotated list of cryptographers.
- Important publications in cryptography — some cryptography papers in computer science.
- Open problems in cryptography
- List of cryptography topics — an alphabetical list of cryptography articles.
- Snake oil
External links
- Cryptography introduction, with several examples
- International Association for Cryptologic Research
- Helger Lipmaa's cryptography pointers
- RSA Laboratories' FAQ About today's cryptography essentially elementary coverage
- sci.crypt mini-FAQ (more recent)
- Savard's glossary an extensive and detailed view of cryptographic history with emphasis on crypto devices
- Open source project CrypTool - Exhaustive educational tool about cryptography and cryptanalysis, freeware.
- Cryptography World - A very basic guide to cryptography and key management.
- Handbook of Applied Cryptography (Free to download as .pdf)
- Techworld Elementary Primer: What is Encryption?
- Links for password-based cryptography
- Code Cracker Online tool to Crack many classic encryption codes (up to the XIX century)
- Crypto Law Survey Extensive survey of existing and proposed laws and regulations on cryptography by legal expert Dr. Bert-Jaap Koops (Tilburg University)
- NSA's CryptoKids
- Beginners' Guide to Cryptography
- An Overview of Cryptography
