DREI 1997
Cryptography & Network Security
| Articles | Lesson Plans | Photo Album | Projects | Main |
Cryptography: the mathematics of
communications
Keeping secrets
Three may keep a secret, if two of them are dead.
Benjamin Franklin
For several thousand years people have tried to communicate secretly and securely. Cryptography is the field of mathematics dedicated to exploring schemes to conceal messages and to verifying the difficulty of "breaking" these schemes: that is, revealing the hidden message without the consent or knowledge of those communicating.
Historically most cryptographic investigation was done by governments
and their efforts were publicized quite rarely. The efforts were
massive: the largest single employers of mathematically trained people
in the United States and the former Soviet Union have been the
government agencies with cryptographic responsibilities. But there's
been an enormous increase in the public work done in cryptography in
the last quarter century, and in the accompanying controversies. This
increase has been caused by the easy availability of computers and
their interconnections (via the Internet and the web) and by the
development of new ideas, such as public key cryptography, which allow
for secure communication between parties who have made no previous
commitment to each other. Every person who has used an automatic
teller machine (ATM), made a phone call using a portable phone, or
had their health records transmitted among caregivers or insurers
should be concerned about secure communication. Social issues include
the conflict between the right to privacy and the desire of some
government agencies to have assured access to certain
communications. Some of the topics relating to cryptography may be
introduced in various high school math courses.
The mathematics
Students need a good algebra background for many of the topics listed
below. Some of the topics involving "civil liberties" questions may,
however, provide opportunities for fertile interaction with social
studies classes. Analytic geometry is useful for many of the
mathematical topics. The abilitiy to think "outside the lines" is an
additional hard-to-assess requirement. What mathematical topics may
students learn while studying cryptography? They may learn about
modular addition and finite fields. They may learn the basics of
combinatorics, such as various ways to count. Additional topics of
discrete mathematics, including basic graph theory, may be
studied. Appropriate topics from number theory, such as some methods
for factoring large numbers and alternative methods for
exponentiating, are used. In addition, some parts of probability (such
as Bayes' Theorem) can be introduced. Depending on time and choice of
topics, a bit of group theory may also be included. The question "What
is an algorithm?" is essential in much of mathematical cryptography,
along with good descriptions of various cryptographic
protocols. Therefore reading and writing skills combined with
appropriate mathematical sophistication are needed. It is also
possible to mention the P versus NP controversy in a cryptography
course. This question has been characterized as the fundamental
problem in theoretical computer science.
Some topics
Here are brief descriptions of some topics which
could be addressed in some high school courses:
- A setting for cryptography: Alice and Bob want to
communicate. Eve will listen and try to decipher their
communications. The generally accepted rules of the game are that
Alice and Bob and Eve (the eavesdropper) all know what the
communication methods are, but the Alice and Bob get to agree ahead of
time on what specific "key" they will use. Eve is allowed to analyze
the messages, and she will sometimes create messages and responses.
- During the late 1940's, Claude Shannon published a
series of papers in the Bell System Technical Journal. He created a
field now known as Information Theory. How much information can a
stream of bits (0's and 1's) carry? How much information is there in a
typical English language sentence? The redundancy in most natural
languages frequently yields cryptographic weaknesses which can be
exploited using simple probabilistic arguments. The basic concepts of
information theory can be stated.
- Schemes for encryption used years ago, such as "grills" of various
types, make an interesting topic of study. Creation of grills and
sending concealed messages using these low-tech schemes can be an
interesting topic.
- Randomness: electronic communication should look
random if it conceals a message successfully. What does "random"
mean, and how can pseudo-random data be constructed? The use of random
bit streams to construct an unbreakable cryptosystem (the "one-time
pad") can be considered, along with its practical
problems. Discussion of these issues will involve material from
several areas of mathematics and theoretical computer science.
- How can two or more people share a secret? Suppose a company has a
formula locked in a safe, and wants to have at least 3 people from a
committee of 5 to agree whenever the safe is to be opened. What method
can be used to guarantee this procedure? In 1979, Adi Shamir
discovered an easy way to "share" such secrets. His method can be
explained to anyone having knowledge of high school algebra and
analytic geometry, and is exploited in many current computer
protocols.
- Social issue #1: how secure should e-mail be? The FBI asserts
rather generally that secure cryptographic communication will be a
great hindrance to capturing terrorists, criminals including drug
traffickers, and spies. Therefore all information transmission should
have "trapdoors" which the general population would allow the
government access to, with suitable legal protection. Also, software
sold internationally should have built-in limits to the kind of
cryptographic protocols with which it can be easily linked. There is
some debate about the FBI's assertions (a book to be published within
the next 6 months will primarily be devoted to rebutting them),
including some doubt that the "key-escrow" schemes suggested by
government agencies can actually be managed in the real world. Should
the U.S. government be allowed to prevent private parties from keeping
secrets? Note that in some countries international travelers are not
allowed to use any non-approved cryptographic communications
devices.
- Social issue #2: what about medical records? The latest proposal
from the U.S. government is that medical records should basically be
open to all police agencies because fraud in medical billing is
prevalent. Other countries with complex health systems (such as Great
Britain) have stringent protections built into medical records at many
levels. Why should Aunt Agnes know about your diseases and their
treatments? Why should a prospective employer be able to find out
about any past treatment for emotional illness or other conditions
with possible social stigma?
- Social issue #3: how secure should financial transactions be?
There's some evidence that some currently used European bank card
systems are easily broken, and their vulnerabilities have been
concealed because of the embarrassment of admitting the difficulties
and the cost in resources and education of customers involved in
replacing the systems. How secure should transaction systems be? Who
should have access to information about financial transactions (e.g.,
if Alice buys pornography, who should know about it)?
- Social issue #4: what is the future of copyright in
the digital world? Should I own my own writings or music or art, or
does a reader or consumer of some type have other, sometimes
conflicting rights? What about distributors? See the discussion on
digital watermarks for more about this.
- Suppose parties must submit a bid to an auction by a
desired date, and the transactions may be vulnerable to a corrupt
official, who may open a sealed bid to disclose information to
competitors. Realistic cryptographic procedures can make detection of
such cheating very likely.
- How can one "timestamp" a document? For example, two parties may
enter into a contract whose details they may prefer to keep private,
but whose execution may reasonably be foreseen to involve the
possibility of disagreement or even litigation. Techniques related to
cryptography provide an opportunity to record the document publically
in a condensed and secret fashion, with a very high likelihood that
neither party can later deny the agreement or its details.
- Digital watermarks: right now the Internet seems to be an
interesting place for intellectual property. Images, sounds, and
ideas, things of potentially huge value, may be digitized,
transported, and copied easily. The protections which such systems as
copyright and patent have afforded artists, composers, writers and
inventors (and which have given large profits to distributors!) seem
to be evaporating. How can the efficiencies of electronic distribution
not compromise these historic rights? Many proposals have been made to
embed ownership and transfer privileges "inside" these works, and
use that information to track misuse. The wonderful word "steganography" (meaning hidden writing) has been applied to the new
field. This is a rapidly developing area because of its many important
commercial applications.
- What is a cryptographic protocol? What is an algorithm? Trying to
convey precisely the idea of a comprehensive and coherent description
of an algorithm is difficult and just describing a few cryptographic
protocols is ambitious.
- Enigma was a German encryption system using before and during
World War II. Solution of this system by a team of British
mathematicians (one of whose members was Alan Turing) using techniques
based on work done by Polish mathematicians was said to have helped
Allied efforts substantially. Enigma can be described, and some idea
of "how to solve it" can be given.
- DES, the Data Encryption Standard, is probably the single most
widely used encryption method in the world. It is used in essentially
every financial transaction handled by "wire", including those done
with ATM'S. A large amount of controversy accompanied the introduction
of DES in the late 1970's. These controversies and the DES system will
be described. DES is a rather complex block cipher system. Similar but
simpler "toy" systems can be studied.
- The first "open" (non-classified) publication of a public key
system was by Diffie and Hellman in 1976. Such methods allow Alice and
Bob to communicate without having a mutually prearranged key,
using only published information. The paradoxical aspect of such
schemes is that their design allows privacy even though much of the
system is available to everyone. The original proposal was shown to
have some weaknesses but other suggestions were made, including RSA,
published by Rivest, Shamir, and Adelman in 1978. RSA, Inc., is now an
important company in secure electronic communication. Its systems and
others (such as PGP) rely for their security directly on the presumed
difficulty of factoring large numbers and finding "logarithms" in
groups. Most confidential web transactions use RSA methods.
- Suppose Alice and Bob are in different prison cells, and Eve is
the prison guard, transmitting all messages between Alice and
Bob. Alice and Bob have no prearrangement for communication, nor have
they access to any shared data. It is still possible, however, for
Alice and Bob to have communication whose information will be secure
from Eve with high probability. Peter Winkler, a mathematician working
at Lucent Technologies, has used these ideas to develop legal bidding
strategies in contract bridge which have been banned from formal
play!
- Digital cash: the money in your pocket is difficult to trace. As
the world moves to a digital economy, traditional bank transfers will
become easier to trace so privacy of financial transactions will
decrease. Can "anonymous" forms of digital cash be created? What are
the desired properties and problems of such cash?
- Coding theory was created as a part of information theory. It
contains a mathematical language which is also useful in
cryptography. Coding theory studies how to send messages so that
error-correction can be done efficiently while keeping information
content high. The goal is to provide patterns for signaling so that if
a message is distorted or damaged, the information it contains can be
reconstructed.
There are many cryptography links on the web. Here's a list of
links containing probably more than any one person needs to
know about cryptography. But we welcome additional links!