Syllabus Math
133
Dr. R. Beezer Spring
2005
Course Description Math 133. The Art and Science of Secret Writing. This freshman seminar will study
the mathematics of encryption, a science known as cryptology. Considerable attention will be given to the
military and social history of cryptology and the public-policy questions raised by its increasing use in
conjunction with the Internet. However, the focus will be on the use of mathematics to create and analyze
encryption algorithms, so the student will need the equivalent of four years of high school
mathematics. A variety of practical exercises will require the use of specialized software and
email programs, so the student should be willing to use unpolished programs on the Windows
platform.
Aims Students in this course will make a sustained, focused and in-depth exploration of cryptology -- its
history, its practice and its future. They will gain an appreciation of the exacting nature of mathematics;
the power of mathematics, especially when combined with advances in computing power; and they will
wrestle with the larger societal questions wrought by advances in technology. The seminar
format will allow for customized assignments and spirited discussions. Substantive written
work in mathematics and in position papers will develop and demonstrate their intellectual
independence.
Beyond the general purposes of freshman seminars, this course will have several more specific
goals.
-
- To introduce the student to the power of discrete mathematics and to become comfortable with
learning new modes of mathematical thought.
-
- To become familiar with the two-thousand year history of cryptology, and to therefore more fully
appreciate the revolutionary nature of the debut of public-key cryptography in the 1970’s.
-
- To consider critically the societal implications created by the convergence of strong encryption,
cheap computers and ubiquitous computers.
-
- To become a more informed consumer of encryption technologies, and a more savvy user of
electronic communications.
Prerequisites This mathematics employed in this course is accessible to any student with four years of
high school mathematics. Practicums will use software written for the Windows platform, so students
should be comfortable using unpolished programs with this operating system. In cases where programs
interoperate, other platforms (Mac, Linux) are acceptable.
Texts Six books will be required reading. The first is The Code Book, by Simon Singh. This is written for
a general audience and describes the major events in the history of cryptology, along with very readable
accounts of the underlying technical aspects of these events. It begins with Mary Queen of Scots’ trial for
treason on October 15, 1586 and concludes with a presentation on quantum cryptography. Along the way
are discussions of historical ciphers, the German Enigma machine in World War II, the US Federal Data
Encryption Standard (DES), public-key cryptography, and Pretty Good Privacy (PGP). This book is one
of the best popular accounts I have ever read dealing with mathematics and computer science, since the
examples are both non-trivial and accurate, yet are written so that they are understandable by an
educated nonspecialist.
Mathematics and Crytography, by Robert A. Beezer, is a collection of notes about the
relevant mathematics needed to understand classical crytogrpahy and the basics of modern
cryptography.
Cryptonomicon, by Neal Stephenson, is an historical, and futuristic, novel that features encryption and
networks prominently. Codes and Ciphers, by Mark Fowler, is really a children’s puzzle book, but the
puzzles are based on classical codes and ciphers and solving them will be a good (and fun) way to
understand those codes and ciphers.
Crypto, by Steven Levy, is a fascinating account of the origins of modern cryptography. Bruce
Schneier’s Secrets and Lies is an excellent discussion of how cryptograhy fits into the wider arena of
computer security and should be required reading for any modern professional who uses computers in their
work or business.
Course Outline
-
Unit 1 History, Classical Cryptography
-
-
Singh, The Code Book
-
-
Chapter 1
- The Cipher of Mary Queen of Scots
-
Chapter 2
- Le Chiffre Indechiffrable
-
Chapter 3
- The Mechanisation of Secrecy
-
Chapter 4
- Cracking the Enigma
-
Chapter 5
- The Language Barrier
-
Beezer, Mathematics and Cryptography
-
-
Chapter DGCD
- Division and Greatest Common Divisors
-
Chapter MA
- Modular Arithmetic
-
Chapter B
- Bases
-
Chapter BA
- Binary Arithmetic
-
Chapter SS
- Sharing a Secret
-
Unit 2 Revolution, Modern Ciphers
-
-
Beezer, Mathematics and Cryptography
-
-
Chapter DHKE
- Diffie-Hellman Key Exchange
-
Chapter DL
- Discrete Logarithms
-
Chapter DHKS
- Diffie-Hellman Knapsack Encryption
-
Chapter NT
- Number Theory
-
Chapter RSA
- RSA (Rivest-Shamir-Adelman) Cryptography
-
Singh, The Code Book
-
-
Chapter 6
- Alice and Bob Go Public
-
Chapter 7
- Pretty Good Privacy
-
Unit 3 The Future, Public Policy, Computer Security
-
-
Singh, The Code Book
-
-
Chapter 8
- A Quantum Leap into the Future
-
Levy, Crypto
-
-
Schneier, Secrets and Lies
Practicums This course will include a variety of practical examples for the students to work themselves.
Some aspects of cryptography sound simple when explained, but seem harder when performed, while other
aspects never seem very clear until practiced.
-
EM Email
- Set up addresses for electronic communication. Experiment with HushMail’s encrypted
email.
-
STEG Steganography
- Hide an encrypted message in an image, using a software tool designed
for this purpose.
-
MONO Monoalphabetic Substitution Cipher
- Decode a classic text that is encrypted using
a classical monoalphabetic substitution cipher, using software tools to make the task more
manageable.
-
VIG Vigenère Cipher
- Decode a classic text that is encrypted using a classical Vigenère cipher,
using software tools to make the task more manageable.
-
PONT Pontifex
- Practice the Solitaire (Pontifex) algorithm, as described in the novel
Cryptonomicon.
-
SDES Simplified DES
- Encode and decode messages by hand using an educational version of the
Data Encryption Standard (DES). Participate in a mock distributed brute-force attack.
-
PGP1-3 Pretty Good Privacy
- Become proficient in using the encryption program Pretty Good
Privacy (PGP) for public-key encryption and digital signatures. Understand the basics of key
management. Three separate practicums (key generation, encryption, digital signatures).
-
TIME Digital Time Stamping
- Learn to use Stamper to digitally time-stamp a message.
-
ANON Anonymous Remailers
- Learn to frustrate traffic analysis by using anonymous remailers
and mixmasters to camaflougue message traffic.
Evaluation Student achievement and progress will be evaluated by a variety of instruments. Practicums
will be graded on a pass/fail basis. There will be three in-class exams where students will write to display
their understanding of the readings, and the mathematics and protocols of encryption. Some questions will
be computational, some will be short answer or essay questions. The final material on social and public
policy material will require students to craft a research paper on a topic of their choosing, which at
that point they can study with the requisite technical understandings. These papers will be
the basis for in-class presentations, which will lend themselves to further debates among the
students.
Bibliography
The vast majority of the books listed in the following annotated bibliography are available in the UPS
Library.
History
- Alvarez, David J. Secret messages : codebreaking and American diplomacy, 1930-1945.
Lawrence, KS, University Press of Kansas. 2000. A good history, especially for its coverage
of the pre-WWII time period.
- Benson, Robert Louis and Michael Warner, Eds. Venona: Soviet espionage and the American
response, 1939-1957. Washington, D.C., National Security Agency, Central Intelligence
Agency. 1996. Cold War era cryptanalysis.
- Calvocoressi, Peter. Top secret ultra. New York, Pantheon Books. 1980. A memoir of
WWII-era cryptanalysis in Europe.
- Clark, Ronald William. The man who broke Purple : the life of Colonel William F. Friedman,
who deciphered the Japanese code in World War II. Boston, Little, Brown. 1977.
- Farago, Ladislas. The broken seal; the story of Operation Magic and the Pearl Harbor disaster.
New York, Random House. 1967. WWII-era cryptanalysis in the Pacific.
- Garlinski, Jozef. The Enigma war. New York, Scribner. 1980. WWII-era cryptanalysis in
Europe.
- Hinsley, F.H. and Alan Stripp, eds. Codebreakers : the inside story of Bletchley Park. Oxford,
New York, Oxford University Press. 1993. The history of Bletchley Park, where English and
American codebreakers helped win WWII.
- Kahn, David. The codebreakers; the story of secret writing. London, Weidenfeld and Nicolson.
1967. The most comprehensive history of cryptology, though insufficient for modern topics.
- Kozaczuk, Wadysaw. Enigma : how the German machine cipher was broken, and how it was
read by the Allies in World War Two. Frederick, Md., University Publications of America.
1984. An account of the Polish efforts to break Enigma, which laid the groundwork for
Bletchley Park to eventually succeed.
- Kippenhahn, Rudolf. Code breaking : a history and exploration. Woodstock, N.Y., Overlook
Press. 1999. The runner-up (to Singh’s The Code Book) as best choice for a history that
also contains some simplified technical explanations.
- Singh, Simon. The code book : the evolution of secrecy from Mary Queen of Scots to quantum
cryptography. New York, Doubleday. 1999. A well-written popular account of the history of
cryptology, with excellent technical descriptions.
- Thompson, James Westfall. Secret diplomacy; espionage and cryptography, 1500-1815. New
York, F. Ungar Pub. Co. 1963. A good account of classical cryptology in Europe.
- United States Army Air Forces. ULTRA and the history of the United States Strategic Air
Force in Europe vs. the German Air Force. Frederick, MD, University Publications of America.
1980. An official report on WWII-era cryptanalysis in Europe.
- Van Der Rhoer, Edward. Deadly magic : a personal account of communications intelligence
in World War II in the Pacific. New York, Scribner. 1978. WWII-era cryptanalysis in the
Pacific.
- Winterbotham, F. W. The Ultra secret. New York, Harper & Row. 1974. WWII-era
cryptanalysis in Europe.
- Yardley, Herbert O. The American Black Chamber. Indianapolis, Bobbs-Merrill. 1931. A
classic. Yardley was the first cryptologist officially in the employ of the United States.
Texts -- Elementary
- Barr, Thomas H. Invitation to Cryptology. Upper Saddle River, NJ, Prentice Hall. 2002.
Advertised for use at the freshman level for students with normal high school preparation in
mathematics.
- Buchmann, Johannes. Introduction to cryptography. New York, Springer-Verlag. 2001.
- Beutelspacher, Albrecht. Cryptology. Washington, DC, Mathematical Association of America.
1994. An entertaining elementary treatment.
- Caloyannides, Michael A. Privacy protection and computer forensics. Norwood, MA, Artech
House. 2004. A how-to on protecting your electronic information (and thereby telling you
how to discover others). Practical uses of encryption. Legal issues.
- Davis, Donald M. The nature and power of mathematics. Princeton, N.J., Princeton University
Press. 1993. Contains a short, elementary section on cryptology.
- Klugerman, Ira H. and Dan Rose. Cracking the code. Lexington, Mass., COMAP. 1993.
Instructional videotape.
- Garfinkel, Simson PGP: pretty good privacy. Sebastopol, CA, O’Reilly & Associates. 1995.
How-to book on how to use the most popular personal encryption software available.
- Lewand, Robert. Cryptological mathematics. Washington, DC, Mathematical Society of
America. 2000. Written for an audience of high school students, this might be the runner-up
for the mathematical text for this course.
- Sinkov, Abraham. Elementary cryptanalysis : a mathematical approach. Washington, D.C.,
Mathematical Association of America. 1980. High-school level, classical techniques only.
- Smith, Laurence Dwight. Cryptography, the science of secret writing. New York, W. W.
Norton. 1943. Dated. Only covers techniques for classical methods.
Texts -- Advanced
- Bauer, Friedrich Ludwig. Decrypted secrets: methods and maxims of cryptology New York,
Springer. 2000. An advanced textbook. Lots of detail on classical methods, and good photos.
- Biham, Eli. Differential cryptanalysis of the data encryption standard. New York,
Springer-Verlag. 1993. Detailed mathematical treatment of the first successful application of
differential cryptanalysis.
- Bouwmeester, Dirk and Artur Ekert and Anton Zeilinger, Eds. The physics of quantum
information : quantum cryptography, quantum teleportation, quantum computation. New
York, Springer. 2000. Good account of possibilities for quantum computing in cryptographic
applications.
- Brassard, Gilles. Modern cryptology: a tutorial. New York, Springer-Verlag. 1988. Very short,
very advanced.
- Electronic Frontier Foundation. Cracking DES : secrets of encryption research, wiretap
politics & chip design. Sebastopal, CA, O’Reilly & Associates, Inc. 1998. Fantastic break of
DES with cheap hardware, with this report prepared for distribution simultaneous with the
announcement of the break.
- Friedman, William F. The Riverbank publications. Laguna Hills, Calif., Aegean Park Press.
1979. A bit odd, but written by one of the key figures in the history of American
cryptanalysis.
- Garrett, Paul. Making, breaking codes: an introduction to cryptography Upper Saddle River,
NJ, Prentice Hall. 2001. An upper-division textbook.
- Goldreich, Oded. Foundations of cryptography: basic tools. Cambridge University Press. 2001.
- Koblitz, Neal. Algebraic aspects of cryptography. New York, Springer. 1998. Beginning
graduate level text.
- Koblitz, Neal. A course in number theory and cryptography. New York , Springer-Verlag.
1994. An advanced textbook, with heavy doses of number theory.
- Kullback, Solomon. Statistical methods in cryptanalysis. Laguna Hills, Calif., Aegean Park
Press. 1976. Serious applications of statistics in the service of cryptanalysis.
- Menezes, A. J. and Paul van Oorschot and Scott Vanstone. Handbook of applied cryptography.
Boca Raton, FL, CRC Press. 1997. Reference work of choice for professionals.
- Patterson, Wayne, 1945- Mathematical cryptology for computer scientists
and mathematicians. Totowa, N.J., Rowman & Littlefield. 1987. A very nice upper-division
text, but quickly becoming outdated.
- Schneier, Bruce. Applied cryptography : protocols, algorithms, and source code in C. New
York, Wiley. 1996. The most popular technical reference on the topic. Includes mathematics,
algorithms and protocols.
- Stallings, William. Cryptography and network security: principles and practice. Upper Saddle
River, N.J., Prentice Hall. 1999. Very good textbook for an upper-division audience.
- Stinson, Douglas R. Cryptography: theory and practice. Boca Raton, CRC Press. 1995. A
good choice for an upper-division text.
- Wayner, Peter. Disappearing Cryptography. Morgan Kaufmann. 2002. How-to on
steganography, watermarking, mimicry, etc.
- Williams, Colin P. Explorations in quantum computing. Santa Clara, Calif., TELOS. 1998.
Public Policy
-
Agre, Philip E. and Marc Rotenberg, Eds. Technology and privacy: the new landscape.
Cambridge, Mass., MIT Press. 1997. Essays from a variety of perspectives about privacy
with regard to technological changes (such as progress in cryptology).
- Bamford, James. The puzzle palace : a report on America’s most secret agency. Boston,
Houghton Mifflin. 1982. A classic history of the National Security Agency.
- Bamford, James. Body of secrets: anatomy of the ultra-secret National Security Agency. New
York, Doubleday. 2001. An updated critique of the National Security Agency.
- Dam, Kenneth W. and Herbert S. Lin, eds. Cryptography’s role in securing the information
society. Washington, DC, National Academy Press. 1996. A report of the National Research
Council’s Computer Science and Telecommunications Board’s Committee to Study National
Cryptography Policy.
- Diffie, Whitfield and Susan Landau. Privacy on the line: the politics of wiretapping and
encryption. Boston, MIT Press. 1998. Public policy, as viewed by one of the pioneers of
public-key cryptography (Diffie), and one of today’s leading industrial cryptologists (Landau).
- Hoffman, Lance J., ed. Building in big brother: the cryptographic policy debate. New York,
Springer-Verlag. 1995. Fifty-four essays on a variety of topics. An excellent source of a wide
range of opinions, though some of it is now out of date.
- Lessig, Lawrence. Code and other laws of cyberspace. Basic Books. 2000. Lessig writes on
the interplay of networks, encryption, copyrights and the law.
- Lessig, Lawrence. The future of ideas : the fate of the commons in a connected world. Vintage.
2002. Lessig writes on the interplay of networks, encryption, copyrights and the law.
- Lessig, Lawrence. Free culture: how big media uses technology and the law to lock down culture
and control creativity. Penguin Books. 2000. Lessig writes on the interplay of networks,
encryption, copyrights and the law.
Cryptologic Puzzle Books
- Chronicle Books. Mensa Secret Codes for Kids Chronicle Books. 2001.
- Fowler, Mark and Sarah Dixon and Radhi Parekh. The Usborne Book of Superpuzzles Usborne
Publishing Limited, London. 1994. A collection containing Codes and Ciphers by Mark
Fowler, with numerous puzzles based on historical codes and ciphers.
Miscellaneous
- Brown, Dan. Digital Fortress: A Thriller. St. Martin’s Griffin, 2000. A novel about the NSA’s
head cryptographer, Susan Fletcher, “a brilliant, beautiful mathematician.”
- Brown, Dan. The Da Vinci Code. Doubleday, 2003. Bestseller with a main character (Sophie
Neveu) who is a cryptanalyst. Contains a few simple puzzles of a cryptographic nature.
- Budd, Louis J. and Edwin H. Cady, Eds. On Poe. Durham, Duke University Press. 1993.
Essay on pages 40-54 by Friedman details Poe as a cryptologist.
- Friedman, William F. The Shakespearean ciphers examined. Cambridge, Cambridge
University Press. 1957. A hobby of one of the key figures in the history of American
cryptanalysis.
- Harris, Robert Enigma Ivy Books. 1996. A novel set at Bletchly Park in 1943.
- Stephenson, Neal. Cryptonomicon. New York, Avon Press. 1999. A novel whose settings
alternate between WWII cryptography and modern-day Internet cryptography. Includes the
Solitaire algorithm, which uses a deck of playing cards for its keystream.