| Cryptography |
 |
Cryptography is about communication in the presence of adversaries. As an example a classic goal of cryptography is privacy: two parties wish to communicate privately, so that an adversary knows nothing about what was communicated.
A standard cryptographic solution to the privacy problem is a secret-key cryptosystem, which consists of the following:
- A message space M: a set of strings (plaintext messages) over some alphabet.
- A ciphertext space C: a set of strings (ciphertexts) over some alphabet.
- A key space K: a set of strings (keys) over some alphabet.
- An encryption algorithm E mapping KxM into C.
- A decryption alogorithm D mapping KxC into M. The algorithms E and D must have the property that
D(K,E(K,M))=M for all K, M.
To use a secret-key cryptosystem, the parties wishing to communicate privately agree on a key K which they will keep secret (hence the name secret-key cryptosystem). They communicate a message M by transmitting the ciphertext to obtain the message M using K, since M=D(K,C).
The cryptosystem is considered secure if it is unfeasible in practice for an eavesdropper who learns E(K,M), but who does not know K, to deduce M or any portion of M.
As cryptography has matured, it has addressed many goals other than privacy, and considered adversaries considerably more devious than a mere passive eavesdropper. One significant new goal is that of authentication, where the recipient of a message wishes to verify that the message he has received has not been forged or modified by an adversary and that the alleged sender actually sent the message exactly as it was received. Digital signatures are a special technique for achieving authentication; they are to electronic communication what handwritten signatures are to paper-based communication.
A note on terminology: the term cryptosystem refers to any scheme designed to work with a communication system in the presence of adversaries, for the purpose of defeating the adversaries' intentions. This is rather broad, but then so is the field. Cryptography refers to the art of designing cryptosystems, cryptanalysis refers to the art of breaking cryptosystems, and cryptology is the union of cryptography and cryptanalysis. It is not uncommon, however, even among professionals working in this area, to (mis)use the term cryptography to refer to any field of cryptology.
The goals and tools of cryptology
As cryptology has developed, the number of goals addressed has expanded, as has the number of tools available for achieving these goals. Cryptology provides methods that enable a communicating party to develop trust that his communications have the desired properties, in spite of the best efforts of an untrusted party (or adversary). The desired properties may include:
Privacy. An adversary learns nothing useful about the message sent.
Authentication. The recipient of a message can convince himself that the message as received originated with the alleged sender.
Signatures. The recipient of a message can convince a third party that the message as received originated with the alleged signer.
Minimality. Nothing is communicated to other parties except that which is specifically desired to be communicated.
Simultaneous exchange. Something of value (e.g. a signature on a contract) is not released until something else of value (e.g. the other party's signature) is received.
Coordination. In a multi-party communication, the parties are able to coordinate their activities toward a common goal even in the presence of adversaries.
Collaboration threshold. In a multi-party communication, the desired properties hold as long as the number of adversaries does not exceed a given threshold.
At a high level, the tools available for the attainment of these goals include:
Randomness. Each party may use a private natural source of randomness (such as a noise diode) to produce "truly random" bits in order to generate his own secret keys or to perform randomized computations.
Physical protection. Each party must physically protect his secrets from the adversary. His most important secret is usually the key that he has randomly generated - this key will provide him with unique capabilities.
By contrast, design information, such as equipment blueprints or cryptographic algorithm details, is usually assumed to be unprotectable, so security does not require the secrecy of such design information. (Kerckhoff's second requirement of a cryptosystem was that "compromise of the system should not incovenience the correspondents.")
Channel properties. Unusual properties of the communication channel can sometimes be exploited.
Information theory. Some systems, such as the Vernam one-time pad are secure in an information-theoretic sense: the adversary is never given enough information to work with to break the code; no amount of computational power can help him overcome this.
Computational complexity theory. The adversary's task is more often computaionally infeasible, rather than information-theoretically impossible. Modern cryptography uses computaional complexity theory to design systems that one has reason to believe cannot be broken with any amount of computation in practice, even though they are breakable in principle (withh extraordinary luck - by guessing a secret key - or by using inordinate amounts of computation).
Cryptographic operators. These computational mappings - such as encryption and decryption functions, one-way functions, and pseudo-random sequence generators - are basic building blocks for constructing cryptographic systems. Note that these need not be functions, since they may use randomization, so that different computations may yield different outputs, even for the same input. Complex operators may be created by composing simpler ones.
Cryptographic protocols. A protocol specifies how each party is to initiate and respond to messages, including erroneous or illegal messages. The protocol may also specify initialization requirements, such as setting up a directory of public keys. A party following the protocol will be protected against certain specified dangers, even if the other parties do not follow the protocol.
The design of protocols and the design of operators are rather independent, in the same sense that the implementation of an abstract data type may be independent of its use. The protocol designer creates protocols assuming the existence of operators with certain security properties. The operator designer proposes implementations of those operators, and tries to prove that the proposed operators have the desired properties.
|
