| Cryptography (from Greek kryptós, "hidden", and
gráphein, "to write") is, traditionally, the study of means of converting information from its normal, comprehensible form into an incomprehensible format, rendering it unreadable
without secret knowledge — the art of encryption. In the past,
cryptography helped ensure secrecy in important communications, such as those of spies, military leaders, and diplomats. In recent
decades, the field of cryptography has expanded its remit in two ways. Firstly, it provides mechanisms for more than just
keeping secrets: schemes like digital signatures and digital cash, for
example. Secondly, cryptography has come to be in widespread use by many civilians
who do not have extraordinary needs for secrecy, although typically it is transparently built into the infrastructure for computing
and telecommunications, and users are not aware of it.
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, "cryptography" is also often used to
refer to the field as a whole; crypto is an informal abbreviation.
Cryptography is an interdisciplinary subject, drawing from
several fields. Before the time of computers, it was closely related to linguistics. Nowadays the emphasis has shifted, and cryptography makes extensive use of technical areas of
mathematics, especially those areas collectively known as discrete mathematics. This includes topics from number theory, information theory, computational complexity, statistics and
combinatorics. It is also a branch of engineering, but an unusual one as it must deal with active, intelligent and malevolent opposition (see
cryptographic engineering and security engineering).
Associated fields are 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) — and traffic analysis,
which is the analysis of patterns of communication in order to learn secret information.
Terminology
The original information which is to be protected by cryptography is called the plaintext. Encryption is the process of converting
plaintext into an unreadable form, termed ciphertext, or, occasionally,
a cryptogram. Decryption is the reverse process, recovering the plaintext back from the ciphertext. Enciphering and
deciphering are alternative terms. A cipher is an algorithm for encryption and decryption. The exact operation of ciphers is normally
controlled by a key — some secret piece of
information that customises how the ciphertext is produced. 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; this is what an end-user interacts
with, e.g. PGP or GPG.
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 method for classical cryptography, substituting larger units of text, typically words or phrases
(e.g., "apple pie" replaces "attack at dawn"). In contrast, classical ciphers usually substitute or rearrange individual
letters (e.g., "attack at dawn" becomes "buubdl bu ebxo" by substitution.). The secret information in a code is specified
in a codebook.
"Cipher" is alternatively spelt "cypher"; similarly "ciphertext" and "cyphertext", and so forth. Both spellings have long
histories in English, and there is occasional tension between their adherents. The first recorded usage of the word
'cryptography' however, 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".
Cryptanalysis
Main article: Cryptanalysis
A cryptanalyst might appear to be the natural adversary of a cryptographer, and to an extent this is true: one can view this
contest all through the history of cryptography.
However, it is possible, in fact preferable, to interpret the two roles as complementary: a thorough understanding of
cryptanalysis is necessary to create secure cryptography.
There are a wide variety of cryptanalytic attacks, and it is convenient to classify them. One distinction concerns what an
attacker can know and do in order to learn secret information, e.g. 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? (see ciphertext only, known plaintext and chosen plaintext). While these example scenarios all view the cipher as an abstract black box, other attacks are based on the implementation of the cipher. If a cryptanalyst has access to, for example, timing or power consumption, he may be able to break a cipher otherwise resistant to analysis.
If a cryptosystem uses a key or a password, it is at risk from an exhaustive search; this is very commonly the weakest point in such systems. 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.
The earliest forms of secret writing required only pen and paper, and are now collectively termed classical cryptography.
The two main categories are transposition ciphers, which
rearrange the order of letters in a message, and substitution
ciphers, which systematically replace groups of letters with others. Classical ciphers tend to leak varying amounts of
information about the statistics of the plaintext, and because of this they are
easily broken, for example by frequency analysis. Classical
ciphers still enjoy popularity today, though mostly as puzzles (see cryptogram).
Early in the 20th century, several mechanical devices were invented for performing encryption, including rotor machines - most famously the Enigma cipher used in World War II. The ciphers
implemented by these machines brought about a significant increase in the complexity of cryptanalysis. The various attacks on
Enigma, for example, succeeded only after considerable effort. Occasionally, these devices have featured in films, such as in the
James Bond adventure From Russia with Love.
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 DES and the invention of RSA. It is well that much progress has been made in a short time; popular applications such as the Internet and mobile phones have
repositioned cryptography, historically the sole province of a few groups with exceptional needs for secrecy, into a mainstream
technology on which millions rely.
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. Note also quantum
cryptography.
Secure communications
See also: Information security
Cryptography is commonly used for securing communications. Four desirable properties are:
- 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.
Cryptography can provide mechanisms to help achieve all of the above. However, some goals aren't 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 use the same key for encryption and decryption, or a little more precisely, the key used for decryption
is "easy" to calculate from the key used for encryption. Other terms include "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 very
difficult to invert (one-way), though 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 mathematical 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 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. Digital signatures are central to the operation of public key
infrastructure and many network security schemes (eg, 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.
Warnings
Myths and misunderstandings about cryptography are widespread, and there is an abundance of insecure cryptographic software on
the market, sometimes pejoratively referred to as snake oil. Readers, buyers, and users should therefore exercise substantial caution when
selecting books and products; self-education is advised. Even software with known strong algorithms may be insecure, because of
poor implementation.
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.
Surprisingly, cryptography does have provably secure ciphers — the one-time pad, for example. However, such schemes require keys as long as the plaintext, so they are almost
always too cumbersome to use.
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 some remarkable protocols: zero-knowledge
proof, secure multiparty computation
and secret sharing, for example.
Cryptography can be used to implement digital
rights management.
External links
|
