The Mathematics of Communication: Keeping Secrets

Stephen J. Greenfield, Department of Mathematics, Rutgers, The State University of New Jersey, New Brunswick, New Jersey

Abstract

For thousands of 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. This course discusses some of the mathematical and social issues related to cryptography. Historically, governments did most cryptographic investigation and these efforts were rarely publicized. They 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. There's been an enormous increase in public cryptographic work 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 ATM (automatic teller machine), made a phone call using a cellular 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, and the difficulty and propriety of preserving intellectual property rights over a collection of bits.

This course covers a number of important topics in the mathematics and theoretical computer science discovered within the last quarter century including: modular arithmetic, algorithms and factoring, cubing and cube inquiry, Diffie-Hellman key exchange and RSA protocols, binary arithmetic, and randomness. The pedagogy has been adapted from strategies commonly used in the humanities and social sciences in an effort to make the course more appealing to students whose interests are in those fields. Active learning techniques included class discussions, group reports, debates and position papers. This requires some adjustment for instructors who may be most familiar with traditional teaching strategies in the mathematical sciences.

Learning Goals

What basic science is covered?

Concepts from mathematics and theoretical computer science will be introduced on an "as needed" basis, motivated by trying to address the social problems mentioned previously. Different topics may need differing mathematical underpinning, changing the concepts introduced. Here's a minimal list of the scientific concepts which can be covered:

  • Shamir's secret sharing scheme (polynomial interpolation, Lagrange interpolation)
  • Modular arithmetic
  • Fermat's little theorem
  • Euclidean algorithm for solving ax = 1 mod p
  • Euler's extension of Fermat's result to a product of two primes
  • RSA encryption and digital signatures
  • Attacks on RSA: factoring
  • Diffie-Hellman encryption
  • The difficulty of arithmetic
  • How to exponentiate efficiently; P versus NP; PRIMES is in P.
  • Binary notation and arithmetic
  • Hashing
  • Digital watermarks; introduction to steganography
  • AES (in the original course, this was DES!)
  • Randomness and one-time pads; pseudorandomness
  • Elements of probability
  • What is an algorithm?

In addition, students should be able to experiment actively with the computational ideas of the course. Thus, in Rutgers implementations, Maple was introduced early in the course, with very little discussion of the program. Maple was used as a calculator with larger capacity than those owned and used by students. Such calculators typically can't display meaningful examples of the topics discussed in this course.

How does this course advance institution-wide objectives?

Two important objectives were addressed with this course.


#1: Show students who are not majoring in science/engineering/technology the relevance of mathematics and science to their lives.

This was done by displaying the variety and power of the solutions that mathematics can offer to the "civic questions or problems" listed as part of the response to, "Why is this course a SENCER model?"

Active learning allowed students to test the mathematical techniques developed, either in class or in homework. Class discussions and papers further showed the relevance of the material. For example, there were several memorable class discussions about medical record privacy, with students taking and intelligently discussing very different positions. Teams prepared presentations about the crypto policies of various governments and the positions of the FBI and the EFF (Electronic Frontier Foundation). Students became intensely involved with the positions they were representing. In addition, the class discussions on intellectual property were fascinating, and many students were well-prepared.

This met not only Rutgers objectives, but fully justified the NSF funding which substantially aided the creation of this course. The NSF stated:

The role of science and technology in American society is undergoing dramatic change. In an increasingly technology-oriented society, a basic understanding of science and mathematics is essential not only for those who pursue careers in scientific and technical fields but for all people. At present, however, not all students have access to quality instruction in these areas, and most adults have limited opportunities to develop a better understanding of the role of science. This nation needs a population that is well prepared to fulfill the needs of a technically competent work force and that exercises their full rights and responsibilities of citizenship in a modern democracy.


#2: (An objective of the instructor, shared by many) Give students the chance to write about and present complex issues, issues having substantial technical and mathematical content stemming from important social, political, and legal questions.

Students at a large institution like Rutgers have an incredibly wide range of educational opportunities. But the chance to write and speak about important technical issues (and to have feedback about these efforts) is not common. For example, writing in undergraduate math and computer science courses is rarely extensive. This course allowed students in the humanities and social sciences to display some of their talents in written and spoken advocacy in a mathematics course, which many had not imagined was possible. I believe that they gained a measure of confidence and perhaps even pleasure in discussing some of the applications of mathematics to social and legal problems.




      Next Page »