Cryptography (or
cryptology; from
Greek ,
kryptos, "hidden,
secret"; and ,
gráphō, "I write", or ,
-logia, respectively) is the practice and study
of hiding
information. Modern
cryptography intersects the disciplines of
mathematics,
computer science, and
engineering. Applications of cryptography
include
ATM cards,
computer passwords, and
electronic commerce.
Terminology
Until modern times cryptography referred almost exclusively to
encryption, which is the process
of converting ordinary information (
plaintext) into unintelligible gibberish (i.e.,
ciphertext). Decryption is the
reverse, in other words, moving from the unintelligible ciphertext
back to plaintext. A
cipher (or
cypher) is a pair of
algorithms
which create the encryption and the reversing decryption. The
detailed operation of a cipher is controlled both by the algorithm
and in each instance by a
key. This is a secret parameter
(ideally known only to the communicants) for a specific message
exchange context. Keys are important, as ciphers without variable
keys can be trivially broken with only the knowledge of the cipher
used and are therefore less than useful for most purposes.
Historically, ciphers were often used directly for encryption or
decryption without additional procedures such as authentication or
integrity checks.
In
colloquial use, the term "
code" is often used to mean any method
of encryption or concealment of meaning. However, in cryptography,
code has a more specific meaning. It means the replacement
of a unit of plaintext (i.e., a meaningful word or phrase) with a
code word (for example,
apple pie
replaces
attack at dawn). Codes are no longer used in
serious cryptography—except incidentally for such things as unit
designations (e.g., Bronco Flight or Operation Overlord) —- since
properly chosen ciphers are both more practical and more secure
than even the best codes and also are better adapted to
computers.
Some use the terms
cryptography and
cryptology
interchangeably in English, while others (including US military
practice generally) use
cryptography to refer specifically
to the use and practice of cryptographic techniques and
cryptology to refer to the combined study of cryptography
and cryptanalysis. English is more flexible than several other
languages in which
cryptology (done by cryptologists) is
always used in the second sense above. In the English Wikipedia the
general term used for the entire field is
cryptography
(done by cryptographers).
The study of characteristics of languages which have some
application in cryptography (or 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).
Encryption was used to (attempt) to ensure
secrecy in
communications, such as those of
spies, military leaders, and
diplomats. 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, among
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 literate opponents, required actual cryptography. The
main classical cipher types are
transposition ciphers, which rearrange
the order of letters in a message (e.g., 'hello world' becomes
'ehlol owrdl' 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
Latin 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. There is record of several early Hebrew ciphers
as well.
The earliest known use of cryptography is some carved ciphertext on
stone in Egypt (ca 1900 BCE), but this may have been done for the
amusement of literate observers. The next oldest is bakery recipes
from Mesopotamia.
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
mathematician and
polymath,
Al-Kindi (also known as
Alkindus), in the
9th century, nearly all such ciphers became more or less readily
breakable by any 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 development of the
polyalphabetic cipher, most clearly by
Leon Battista Alberti around
the year 1467, though there is some indication that it was known to
Al-Kindi. Alberti's innovation was to use different ciphers (i.e.,
substitution alphabets) for various parts of a message (perhaps for
each successive plaintext letter at 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 extended
frequency analysis techniques.
Although frequency analysis is a powerful and general technique
against many ciphers, encryption has still been often effective in
practice; many a would-be cryptanalyst was unaware of the
technique. Breaking a message without using frequency analysis
essentially required knowledge of the cipher used and perhaps of
the key involved, thus making espionage, bribery, burglary,
defection, etc. more attractive approaches to the cryptanalyticly
uninformed. It was finally explicitly recognized in the 19th
century that secrecy of a cipher's algorithm is not a sensible nor
practical safeguard of message security; in fact, it was further
realized that any adequate cryptographic scheme (including ciphers)
should remain secure even if the adversary fully understands the
cipher algorithm itself. Security of the key used should alone be
sufficient for a good cipher to maintain confidentiality under an
attack. This fundamental principle was first explicitly stated in
1883 by
Auguste Kerckhoffs and is
generally called
Kerckhoffs'
principle; alternatively and more bluntly, it was restated by
Claude Shannon, the inventor of
information theory and the
fundamentals of theoretical cryptography, as
Shannon's
Maxim — 'the enemy knows the system'.
Various physical devices and aids have been used to assist with
ciphers. One of the earliest may have been the
scytale of
ancient
Greece, a rod supposedly used by the Spartans as an aid for a
transposition cipher (see image above). In medieval times, other
aids were invented such as the
cipher grille, which was also used for
a kind of steganography. With the invention of polyalphabetic
ciphers came more sophisticated aids such as Alberti's own
cipher disk,
Johannes Trithemius'
tabula recta scheme, and
Thomas Jefferson's
multi-cylinder (not publicly known, and
reinvented independently by
Bazeries around
1900). Many mechanical encryption/decryption devices were invented
early in the 20th century, and several patented, among them
rotor machines — famously including
the
Enigma machine used by the German
government and military from the late 20s and during
World War II. The ciphers implemented by better
quality examples of these machine 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 representable in any binary format, unlike
classical ciphers which only encrypted written language texts; this
was new and significant. Computer use has thus supplanted
linguistic cryptography, both for cipher design and 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 (ie, memory or CPU capability)), while
breaking it requires an effort many orders of magnitude larger, and
vastly larger than that required for any classical cipher, making
cryptanalysis so inefficient and impractical as to be effectively
impossible. Alternate methods of attack (bribery, burglary, threat,
torture, ...) have become more attractive in consequence.
Extensive open academic research into cryptography is relatively
recent; it began only in the mid-1970s. Medieval work was both less
systematic, less comprehensive, and more likely to attract
attention from the Church or others as Satanically inspired or
dangerous to the state or those in power; at least two of Johannes
Trithemius' books were added to the Index of banned books by the
Roman Catholic Church. In recent times, IBM personnel designed the
algorithm that became the Federal (ie, US)
Data Encryption Standard; Whitfield
Diffie and Martin Hellman published
their
key agreement algorithm,; and the
RSA
algorithm was published in
Martin
Gardner's
Scientific
American column. Since then, cryptography has become a widely
used tool in communications,
computer
networks, and computer security generally. Some modern
cryptographic techniques can only keep their keys secret if certain
mathematical problems are intractable, such as the
integer factorisation or the
discrete logarithm problems, so there are
deep connections with abstract mathematics. There are no absolute
proofs that a cryptographic technique is secure (but see
one-time pad); at best, there are proofs that
some techniques are secure
if some computational problem
is difficult to solve, or this or that assumption about
implementation or practical use is met.
As well as being aware of cryptographic history, cryptographic
algorithm and system designers must also sensibly consider probable
future developments while working on their designs. For instance,
continuous improvements in computer processing power have increased
the scope of
brute-force attacks,
thus when specifying
key lengths, the
required key lengths are 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 may
be making the need for this preemptive caution rather more than
merely speculative.
Essentially, prior to the early 20th century, cryptography was
chiefly concerned with
linguistic and
lexicographic 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,
number theory, and finite mathematics
generally. 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); other
kinds of engineering (eg, civil or chemical 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.
The modern study of symmetric-key
ciphers relates mainly to the study of
block ciphers and
stream ciphers and to their applications. A
block cipher is, in a sense, a modern embodiment of Alberti's
polyalphabetic cipher: block ciphers take as input a block of
plaintext and a key, and output a block of ciphertext of the same
size. Since messages are almost always longer than a single block,
some method of knitting together successive blocks is required.
Several have been developed, some with better security in one
aspect or another than others. They are the
modes of operation and must
be carefully considered when using a block cipher in a
cryptosystem.
The
Data Encryption
Standard (DES) and the
Advanced Encryption Standard
(AES) are block cipher designs which have been designated
cryptography standards by the US
government (though DES's designation was finally withdrawn after
the AES was adopted). 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 a hidden internal state which
changes as the cipher operates. That internal state is initially
set up using the secret key material.
RC4 is a
widely used stream cipher; see
Category:Stream ciphers. Block
ciphers can be used as stream ciphers; see
Block cipher modes of
operation.
Cryptographic hash
functions are a third type of cryptographic algorithm. They
take a message of any length as input, and output a short, fixed
length
hash which can be used in (for
example) a digital signature. For good hash functions, an attacker
cannot find two messages that produce the same hash.
MD4 is a long-used hash function which is now broken;
MD5, a strengthened variant of MD4, is also
widely used but broken in practice. The U.S.
National
Security Agency developed the Secure
Hash Algorithm series of MD5-like hash functions: SHA-0 was a
flawed algorithm that the agency withdrew; SHA-1 is widely deployed
and more secure than MD5, but cryptanalysts have identified attacks
against it; the SHA-2 family improves on SHA-1, but it isn't yet
widely deployed, and the U.S. standards authority thought it
"prudent" from a security perspective to develop a new standard to
"significantly improve the robustness of NIST's overall hash
algorithm toolkit." Thus, a
hash function
design competition is underway and meant to select a new U.S.
national standard, to be called SHA-3, by 2012.
Message authentication
codes (MACs) are much like cryptographic hash functions, except
that a secret key is used to authenticate the hash value on
receipt.
Public-key cryptography
Symmetric-key cryptosystems use the same key for encryption and
decryption of a message, though a message or group of messages may
have a different key than others. A significant disadvantage of
symmetric ciphers is the
key
management necessary to use them securely. Each distinct pair
of communicating parties must, ideally, share a different key, and
perhaps each ciphertext exchanged as well. The number of keys
required increases as the
square of
the number of network members, which very quickly requires complex
key management schemes to keep them all straight and secret. The
difficulty of securely establishing a secret key between two
communicating parties, when a
secure
channel doesn't already exist between them, also presents a
chicken-and-egg problem
which is a considerable practical obstacle for cryptography users
in the real world.
In a groundbreaking 1976 paper,
Whitfield Diffie and
Martin Hellman proposed the notion of
public-key (also, more generally, called
asymmetric
key) cryptography in which two different but mathematically
related keys are used — a
public key and a
private key. 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 1978,
Ronald Rivest,
Adi Shamir, and
Len
Adleman invented
RSA, another public-key
system.
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.
In addition to encryption, public-key cryptography can be used to
implement
digital signature
schemes. A digital signature is reminiscent of an ordinary
signature; they both have the characteristic that
they are easy for a user to produce, but difficult for anyone else
to
forge. Digital signatures can also be
permanently tied to the content of the message being signed; they
cannot then be 'moved' from one document to another, for any
attempt will be detectable. In digital signature schemes, there are
two algorithms: one for
signing, in which a secret key is
used to process the message (or a hash of the message, or both),
and one for
verification, in which the matching public key
is used with the message to check the validity of the signature.
RSA and
DSA are two of the most popular
digital signature schemes. Digital signatures are central to the
operation of
public key
infrastructures and many network security schemes (eg,
SSL/TLS, many
VPNs, etc).
Public-key algorithms are most often based on the
computational complexity of
"hard" problems, often from
number
theory. For example, the hardness of RSA is related to the
integer factorization problem,
while Diffie-Hellman and DSA are related to the
discrete logarithm problem. More
recently,
elliptic curve
cryptography has developed in which security is based on
number theoretic problems involving
elliptic curves. Because of the difficulty of
the underlying problems, most public-key algorithms involve
operations such as
modular
multiplication and exponentiation, which are much more
computationally expensive than the techniques used in most block
ciphers, especially with typical key sizes. As a result, public-key
cryptosystems are commonly
hybrid
cryptosystems, in which a fast high-quality symmetric-key
encryption algorithm is used for the message itself, while the
relevant symmetric key is sent with the message, but encrypted
using a public-key algorithm. Similarly, hybrid signature schemes
are often used, in which a cryptographic hash function is computed,
and only the resulting hash is digitally signed.
Cryptanalysis
The goal of cryptanalysis is to find some weakness or insecurity in
a cryptographic scheme, thus permitting its subversion or
evasion.
It is a commonly held misconception that every encryption method
can be broken.
In connection with his WWII work at Bell Labs, Claude Shannon
proved that the one-time pad cipher is
unbreakable, provided the key material is truly random, never reused, kept secret from all
possible attackers, and of equal or greater length than the
message. Most ciphers, apart from the one-time pad, can be
broken with enough computational effort by
brute force attack, but the amount of
effort needed may be
exponentially
dependent on the key size, as compared to the effort needed to
use the cipher. In such cases, effective security could be
achieved if it is proven that the effort required (i.e., "work
factor", in Shannon's terms) is beyond the ability of any
adversary. This means it must be shown that no efficient method (as
opposed to the time-consuming brute force method) can be found to
break the cipher. Since no such showing can be made currently, as
of today, the one-time-pad remains the only theoretically
unbreakable cipher.
There are a wide variety of cryptanalytic attacks, and they can be
classified in any of several ways. A common distinction turns on
what an attacker knows and what capabilities are available. In a
ciphertext-only attack, the
cryptanalyst has access only to the ciphertext (good modern
cryptosystems are usually effectively immune to ciphertext-only
attacks). In a
known-plaintext
attack, the cryptanalyst has access to a ciphertext and its
corresponding plaintext (or to many such pairs).
In a chosen-plaintext attack, the
cryptanalyst may choose a plaintext and learn its corresponding
ciphertext (perhaps many times); an example is gardening, used by the British during WWII. Finally, in a
chosen-ciphertext attack, the
cryptanalyst may be able to
choose ciphertexts and learn
their corresponding plaintexts. Also important, often
overwhelmingly so, are mistakes (generally in the design or use of
one of the
protocols
involved; see
Cryptanalysis
of the Enigma for some historical examples of this).
Cryptanalysis of symmetric-key ciphers typically involves looking
for attacks against the block ciphers or stream ciphers that are
more efficient than any attack that could be against a perfect
cipher. For example, a simple brute force attack against DES
requires one known plaintext and 2
^{55} decryptions, trying
approximately half of the possible keys, to reach a point at which
chances are better than even the key sought will have been found.
But this may not be enough assurance; a
linear cryptanalysis attack against DES
requires 2
^{43} known plaintexts and approximately
2
^{43} DES operations. This is a considerable improvement
on brute force attacks.
Public-key algorithms are based on the computational difficulty of
various problems. The most famous of these is
integer factorization (e.g., the RSA
algorithm is based on a problem related to integer factoring), but
the
discrete logarithm problem is
also important. Much public-key cryptanalysis concerns numerical
algorithms for solving these computational problems, or some of
them, efficiently (ie, in a practical time). For instance, the best
known algorithms for solving the
elliptic curve-based version of
discrete logarithm are much more time-consuming than the best known
algorithms for factoring, at least for problems of more or less
equivalent size. Thus, other things being equal, to achieve an
equivalent strength of attack resistance, factoring-based
encryption techniques must use larger keys than elliptic curve
techniques. For this reason, public-key cryptosystems based on
elliptic curves have become popular since their invention in the
mid-1990s.
While pure cryptanalysis uses weaknesses in the algorithms
themselves, other attacks on cryptosystems are based on actual use
of the algorithms in real devices, and are called
side-channel attacks. If a
cryptanalyst has access to, say, the amount of time the device took
to encrypt a number of plaintexts or report an error in a password
or PIN character, he may be able to use a
timing attack to break a cipher that is
otherwise resistant to analysis. An attacker might also study the
pattern and length of messages to derive valuable information; this
is known as
traffic analysis, and
can be quite useful to an alert adversary. Poor administration of a
cryptosystem, such as permitting too short keys, will make any
system vulnerable, regardless of other virtues. And, of course,
social engineering,
and other attacks against the personnel who work with cryptosystems
or the messages they handle (e.g.,
bribery,
extortion,
blackmail,
espionage,
torture, ...) may be the most productive
attacks of all.
Cryptographic primitives
Much of the theoretical work in cryptography concerns
cryptographic primitives —
algorithms with basic cryptographic properties — and their
relationship to other cryptographic problems. More complicated
cryptographic tools are then built from these basic primitives.
These primitives provide fundamental properties, which are used to
develop more complex tools called
cryptosystems or
cryptographic protocols, which guarantee one or more
high-level security properties. Note however, that the distinction
between cryptographic
primitives and cryptosystems, is
quite arbitrary; for example, the
RSA algorithm
is sometimes considered a cryptosystem, and sometimes a primitive.
Typical examples of cryptographic primitives include
pseudorandom functions,
one-way functions, etc.
Cryptosystems
One or more cryptographic primitives are often used to develop a
more complex algorithm, called a cryptographic system, or
cryptosystem. Cryptosystems (e.g.
El-Gamal encryption) are designed to
provide particular functionality (e.g. public key encryption) while
guaranteeing certain security properties (e.g.
CPA security in the
random oracle model). Cryptosystems use
the properties of the underlying cryptographic primitives to
support the system's security properties. Of course, as the
distinction between primitives and cryptosystems is somewhat
arbitrary, a sophisticated cryptosystem can be derived from a
combination of several more primitive cryptosystems. In many cases,
the cryptosystem's structure involves back and forth communication
among two or more parties in space (e.g., between the sender of a
secure message and its receiver) or across time (e.g.,
cryptographically protected
backup data).
Such cryptosystems are sometimes called
cryptographic protocols.
Some widely known cryptosystems include
RSA
encryption,
Schnorr signature,
El-Gamal encryption,
PGP, etc. More complex cryptosystems
include
electronic cash systems,
signcryption systems, etc. Some more
'theoretical' cryptosystems include
interactive proof systems, (like
zero-knowledge proofs,),
systems for
secret sharing,
etc.
Until recently, most security properties of most cryptosystems were
demonstrated using empirical techniques, or using ad hoc reasoning.
Recently, there has been considerable effort to develop formal
techniques for establishing the security of cryptosystems; this has
been generally called
provable
security. The general idea of provable security is to give
arguments about the computational difficulty needed to compromise
some security aspect of the cryptosystem (ie, to any
adversary).
The study of how best to implement and integrate cryptography in
software applications is itself a distinct field, see:
cryptographic engineering and
security engineering.
Legal issues
Prohibitions
Cryptography has long been of interest to intelligence gathering
and
law enforcement agencies.
Actually secret communications may be criminal or even
treasonous; those whose communications are open to
inspection may be less likely to be either. Because of its
facilitation of
privacy, and the diminution
of privacy attendant on its prohibition, cryptography is also of
considerable interest to civil rights supporters. Accordingly,
there has been a history of controversial legal issues surrounding
cryptography, especially since the advent of inexpensive computers
has made widespread access to high quality cryptography
possible.
In some countries, even the domestic use of cryptography is, or has
been, restricted.
Until 1999, France
significantly restricted the use of cryptography domestically,
though it has relaxed many of these. In China, a license is still required to use
cryptography. Many countries have tight restrictions on the
use of cryptography.
Among the more restrictive are laws in
Belarus, Kazakhstan, Mongolia, Pakistan, Russia, Singapore, Tunisia, and
Vietnam.
In the
United
States, cryptography is legal for domestic use, but there
has been much conflict over legal issues related to
cryptography. One particularly important issue has been the
export of cryptography and
cryptographic software and hardware. Probably because of the
importance of cryptanalysis in
World War
II and an expectation that cryptography would continue to be
important for national security, many Western governments have, at
some point, strictly regulated export of cryptography. After World
War II, it was illegal in the US to sell or distribute encryption
technology overseas; in fact, encryption was designated as
auxiliary military equipment and put on the
United States Munitions List.
Until the development of the
personal
computer, asymmetric key algorithms (ie, public key
techniques), and the
Internet, this was not
especially problematic. However, as the Internet grew and computers
became more widely available, high quality encryption techniques
became well-known around the globe. As a result, export controls
came to be seen to be an impediment to commerce and to
research.
Export controls
In the 1990s, there were several challenges to US export
regulations of cryptography. One involved
Philip Zimmermann's
Pretty Good Privacy (PGP) encryption
program; it was released in the US, together with its
source code, and found its way onto the Internet
in June 1991.
After a complaint by RSA Security (then called RSA Data Security,
Inc., or RSADSI), Zimmermann was criminally investigated by the
Customs Service and the FBI for several years. No charges were ever
filed, however.
Also, Daniel
Bernstein, then a graduate student at UC Berkeley, brought a lawsuit against the US government
challenging some aspects of the restrictions based on free speech grounds. The 1995 case
Bernstein v. United States ultimately resulted
in a 1999 decision that printed source code for cryptographic
algorithms and systems was protected as
free speech by the United States
Constitution.
In 1996, thirty-nine countries signed the
Wassenaar Arrangement, an arms control
treaty that deals with the export of arms and "dual-use"
technologies such as cryptography. The treaty stipulated that the
use of cryptography with short key-lengths (56-bit for symmetric
encryption, 512-bit for RSA) would no longer be export-controlled.
Cryptography exports from the US are now much less strictly
regulated than in the past as a consequence of a major relaxation
in 2000; there are no longer very many restrictions on key sizes in
US-
exported mass-market
software. In practice today, since the relaxation in US export
restrictions, and because almost every
personal computer connected to the
Internet, everywhere in the world, includes
US-sourced
web browsers such as
Mozilla Firefox or
Microsoft Internet Explorer,
almost every Internet user worldwide has access to quality
cryptography (i.e., when using sufficiently long keys with properly
operating and unsubverted software, etc) in their browsers;
examples are
Transport Layer
Security or
SSL stack.
The
Mozilla Thunderbird and
Microsoft Outlook E-mail client programs similarly can connect
to
IMAP or
POP servers via TLS, and can send and
receive email encrypted with
S/MIME. Many
Internet users don't realize that their basic application software
contains such extensive
cryptosystems.
These browsers and email programs are so ubiquitous that even
governments whose intent is to regulate civilian use of
cryptography generally don't find it practical to do much to
control distribution or use of cryptography of this quality, so
even when such laws are in force, actual enforcement is often
effectively impossible.
NSA involvement
Another
contentious issue connected to cryptography in the United States is
the influence of the National Security Agency on cipher development and policy. NSA was
involved with the design of
DES during its development at
IBM and its consideration by the
National Bureau of Standards as
a possible Federal Standard for cryptography. DES was designed to
be resistant to
differential
cryptanalysis, a powerful and general cryptanalytic technique
known to NSA and IBM, that became publicly known only when it was
rediscovered in the late 1980s. According to
Steven Levy, IBM rediscovered differential
cryptanalysis, but kept the technique secret at NSA's request. The
technique became publicly known only when Biham and Shamir
re-rediscovered and announced it some years later. The entire
affair illustrates the difficulty of determining what resources and
knowledge an attacker might actually have.
Another instance of NSA's involvement was the 1993
Clipper chip affair, an encryption microchip
intended to be part of the
Capstone cryptography-control
initiative. Clipper was widely criticized by cryptographers for two
reasons. The cipher algorithm was then classified (the cipher,
called
Skipjack, though it was
declassified in 1998 long after the Clipper initiative lapsed). The
secret cipher caused concerns that NSA had deliberately made the
cipher weak in order to assist its intelligence efforts. The whole
initiative was also criticized based on its violation of
Kerckhoffs' principle, as the scheme
included a special
escrow key held by the
government for use by law enforcement, for example in
wiretaps.
Digital rights management
Cryptography is central to digital rights management (DRM), a group
of techniques for technologically controlling use of
copyrighted material, being widely implemented and
deployed at the behest of some
copyright
holders. In 1998, American President
Bill
Clinton signed the
Digital Millennium Copyright
Act (DMCA), which criminalized all production, dissemination,
and use of certain cryptanalytic techniques and technology (now
known or later discovered); specifically, those that could be used
to circumvent DRM technological schemes. This had a noticeable
impact on the cryptography research community since an argument can
be made that
any cryptanalytic research violated, or might
violate, the DMCA. Similar statutes have since been enacted in
several countries and regions, including the implementation in the
EU Copyright Directive. Similar restrictions are called for by
treaties signed by
World Intellectual
Property Organization member-states.
The
United States Department of
Justice and FBI have not enforced the DMCA as rigorously as had
been feared by some, but the law, nonetheless, remains a
controversial one. One well-respected cryptography researcher,
Niels Ferguson, has publicly stated
that he will not release some of his research into an Intel security design for fear of prosecution under the
DMCA, and both Alan Cox (longtime number 2
in Linux kernel development) and
Professor Edward Felten (and some of
his students at Princeton) have encountered problems related to the
Act. Dmitry Sklyarov was
arrested during a visit to the US from Russia, and jailed for some
months for alleged violations of the DMCA which had occurred in
Russia, where the work for which he was arrested and charged was
then, and when he was arrested, legal. In 2007, the cryptographic
keys responsible for
Blu Ray and
HD DVD content scrambling were
discovered and released onto
the
internet. Both times, the
MPAA sent out numerous DMCA takedown notices, and there
was a
massive internet
backlash as a result of the implications of such notices on
fair use and
free
speech both legally protected in the US and in some other
jurisdictions.
See also
Notes
- Liddell and Scott's Greek-English Lexicon. Oxford University
Press. (1984)
- Oded
Goldreich, Foundations of Cryptography, Volume 1: Basic
Tools, Cambridge University Press, 2001, ISBN
0-521-79172-3
- Kama Sutra, Sir Richard F. Burton, translator, Part I,
Chapter III, 44th and 45th arts.
- David Kahn,
The
Codebreakers, 1967, ISBN 0-684-83130-9.
- Ibrahim A. Al-Kadi (April 1992), "The
origins of cryptology: The Arab contributions”, Cryptologia
16 (2): 97–126
- 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.
- Whitfield Diffie and Martin Hellman,
"New Directions in
Cryptography", IEEE Transactions on Information Theory, vol.
IT-22, Nov. 1976, pp: 644–654. ( pdf)
- AJ Menezes, PC van Oorschot, and SA Vanstone, Handbook of Applied Cryptography ISBN
0-8493-8523-7.
- FIPS PUB 197: The official Advanced Encryption
Standard.
- NCUA letter to credit unions, July 2004
- RFC 2440 - Open PGP Message Format
- SSH at windowsecurity.com by Pawel Golen, July
2004
- Bruce
Schneier, Applied Cryptography, 2nd edition, Wiley,
1996, ISBN 0-471-11709-9.
- National Institute of Standards and
Technology
- Whitfield Diffie and Martin Hellman,
"Multi-user cryptographic techniques" [Diffie and Hellman, AFIPS
Proceedings 45, pp109–112, June 8, 1976].
- Ralph
Merkle was working on similar ideas at the time and encountered
publication delays, and Hellman has suggested that the term used
should be Diffie-Hellman-Merkle aysmmetric key cryptography.
- David Kahn, "Cryptology Goes Public", 58 Foreign Affairs
141, 151 (fall 1979), p. 153.
- R.
Rivest, A.
Shamir, L.
Adleman. A
Method for Obtaining Digital Signatures and Public-Key
Cryptosystems. Communications of the ACM, Vol. 21 (2),
pp.120–126. 1978. Previously released as an MIT "Technical Memo" in
April 1977, and published in Martin Gardner's Scientific
American Mathematical recreations
column
- Clifford Cocks. A Note on 'Non-Secret Encryption',
CESG Research Report, 20 November 1973.
- "Shannon": Claude Shannon and Warren Weaver, "The
Mathematical Theory of Communication", University of Illinois Press,
1963, ISBN 0-252-72548-4
- Pascal Junod, "On the Complexity of Matsui's Attack", SAC
2001.
- Dawn Song, David Wagner, and Xuqing Tian, "Timing Analysis of Keystrokes and Timing Attacks
on SSH", In Tenth USENIX Security
Symposium, 2001.
- S. Brands, "Untraceable Off-line Cash in Wallets with
Observers", In Advances in Cryptology — Proceedings of
CRYPTO,
Springer-Verlag, 1994.
- László Babai. "Trading group theory for randomness". Proceedings
of the Seventeenth Annual Symposium on the Theory of
Computing, ACM, 1985.
- S.
Goldwasser, S. Micali, and C. Rackoff, "The Knowledge Complexity
of Interactive Proof Systems", SIAM J. Computing, vol. 18, num. 1,
pp. 186–208, 1989.
- G. Blakley. "Safeguarding cryptographic keys." In
Proceedings of AFIPS 1979, volume 48, pp. 313–317, June
1979.
- A. Shamir. "How to share a secret." In Communications of
the ACM, volume 22, pp. 612–613, ACM, 1979.
- RSA Laboratories' Frequently Asked Questions About
Today's Cryptography
- Cryptography & Speech from Cyberlaw
- "Case Closed on Zimmermann PGP Investigation",
press note from the IEEE.
- Bernstein v USDOJ, 9th Circuit court of appeals
decision.
- The Wassenaar Arrangement on Export Controls for
Conventional Arms and Dual-Use Goods and Technologies
- "The Data Encryption Standard (DES)" from
Bruce
Schneier's CryptoGram newsletter, June 15, 2000
- E. Biham and A.
Shamir, "Differential cryptanalysis of DES-like
cryptosystems", Journal of Cryptology, vol. 4 num. 1, pp. 3–72,
Springer-Verlag, 1991.
- Levy, pg. 56
- Digital Millennium Copyright Act
- http://www.macfergus.com/niels/dmca/cia.html
Further reading
- Excellent coverage of many classical ciphers and cryptography
concepts and of the "modern" DES and RSA systems.
- Cryptography and Mathematics by Bernhard Esslinger, 200 pages, part of
the free open-source package CrypTool,
PDF download.
- 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.
- 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.
- Oded Goldreich, Foundations of Cryptography, in two volumes, Cambridge
University Press, 2001 and 2004.
- Introduction to Modern Cryptography by Jonathan Katz
and Yehuda Lindell. [701783].
- Alvin's Secret Code by Clifford B. Hicks (children's novel that introduces
some basic cryptography and cryptanalysis).
- Ibrahim A. Al-Kadi, "The Origins of Cryptology: the Arab
Contributions," Cryptologia, vol. 16, no. 2 (April 1992),
pp. 97–126.
- 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.
- Andreas Pfitzmann: Security in IT Networks:
Multilateral Security in Distributed and by Distributed
Systems
- Introduction to Modern Cryptography by Phillip Rogaway and Mihir Bellare, a mathematical introduction to
theoretical cryptography including reduction-based security proofs.
PDF download.
- Cryptonomicon by Neal Stephenson (novel, WW2 Enigma cryptanalysis figures into the story,
though not always realistically).
- Johann-Christoph Woltag, 'Coded Communications (Encryption)' in
Rüdiger Wolfrum (ed) Max Planck Encyclopedia of Public
International Law (Oxford University Press 2009). * , giving an
overview of international law issues regarding cryptography.
External links