|
Overview
An OverView
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 Algorithm
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
(with 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.
|
