DREI 1997
Cryptography & Network Security

## 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!