The Mathematics of Cryptography, Spring 2010
New four-week spring-term course: The Mathematics of Cryptography.
We will have class eight hours a week, plus field trips,
along with office hours and the occasional movie night.
This class will be open to all students, majors and non-majors.
Even freshmen are welcome.
We will have one long day's field trip to
Washington DC to visit the Spy Museum and the NSA's Museum of Cryptography,
as well as a short field trip to VMI's Marshall Museum.
Grading will consist of daily homework problems and two exams... probably
50% homework and 25% per exam.
Tentative schedule for the course (as of October 2009; this is subject to change):
- Week One: Classical Cryptosystems.
- Day 1: Historical overview. Basic substitution codes.
Pinpoint codes,
templates, book codes, etc. How to design new codes. Private-key codes.
- Day 2: Converting from codes to plain text.
Breaking codes. Frequency analysis. More historical codes (Benedict Arnold,
Julius Caesar, etc).
- Day 3: Complex classical systems. Vigenere codes.
How frequency
analysis fails, and how it can be resurrected.
- Day 4: High-security classical systems. Playfair method. ADFGX method.
One-time
pad method. The VENONA code, the Rosenbergs, the KGB, and American
efforts (through 1980) to attack the code. Brief discussion of Enigma
machine in preparation for field trip to VMI.
- Out-of-class activities:
- Field trip to VMI's Marshall Museum (which contains
several code wheels, cipher machines, and an actual Enigma machine).
- Movie, "Heir to an Execution" (documentary), by the
granddaughter of Julius and Ethel Rosenberg. Their execution for espionage
was controversial at the time, but the decoded VENONA documents released 40
years after their death proved Julius' guilt...
- Movie, "Enigma" (starring Kate Winslet), a feature film about the
efforts to break the German code.
- Week Two: Number Theory I
- Day 1: Motivation on transitioning from private-key to
public-key methods. Basic modular arithmetic. Affine ciphers and
shift ciphers.
- Day 2: Prime numbers.
Division algorithm. GCD's. Euclidean algorithm.
- Day 3: Modular inverses. Breaking the affine and shift ciphers.
- Day 4: More on congruence applications. Check digits in ISBN codes.
Perpetual calendars. The Pollard Rho factoring method.
- Out-of-class activities:
- Movie, "Good Will Hunting" (starring Minnie Driver), for no
particular reason other than it portrays a mathematical genius in love.
- Movie, "Infinity" (starring Matthew Broderick), in which
Broderick plays physicist Richard Feynman, who in one delightful scene
uses an abacus to defeat a calculator in a math competition. It's interesting
to note that Feynman worked on the Manhattan Project, and Russian spies
used the VENONA code to report back to Moscow on the status of American
progress.
- Week Three: Number Theory II and Modern Cryptography.
- Day 1: More on primality testing. Fermat primes. Pseudoprimes.
- Day 2: Fermat's theorem, Euler's theorem, and primitive roots
- Day 3: Diffie-Hellman exponentiation system.
- Day 4: RSA cryptosystem. Uses and applications in signatures, identification,
and authentication. Uses in
the modern world. Security of RSA.
- Out-of-class activities:
- Movie, "Hard Problems: The Road to the World's Toughest Math Contest"
(documentary), about US high-school students at the International Mathematical
Olympiad.
- Movie, "N Is a Number: A Portrait of Paul Erdos"
(documentary), on the life of the famous mathematician.
- Week Four: Latest advances in Cryptography. Field Trip to DC.
- Day 1: Attacking the RSA system: theory and examples.
- Day 2: Preparation for field trip: discussion of Enigma machines and
Bletchley Park project of WW II, Alan Turing's role in early computing, the
use of human computers, and classroom demonstration of human-powered computing.
- Day 3: Field trip to NSA museum and spy museum. Special
attention to be paid
to the Zola Spy Restaurant (at the spy museum),
where scupltor Jim Sanborn has hidden clues for
his not-yet-solved Kryptos sculpture at CIA headquarters.
- Day 4: Review, overview, conclusions.
- Out-of-class activities:
- Field trip to Washington, DC (see above).
- Movie, "A Beautiful Mind" (starring Russell Crowe), about a
mathematician's descent into madness.
- Movie, "U-571" (starring Matthew McConaughey), about the capture of
an Enigma machine from a German submarine during WW II.
The highlights will be our field trips to
the Marshall Museum here in Lexington and the NSA Museum in Washington, DC.
Both museums have extensive collections of
cryptographic materials and artifacts.
A picture from 10 years ago of us at VMI's Marshall Muesum with a WW II Enigma machine ...
Some pictures from the NSA museum in DC:
A few assignments in code:
Exams will also be written in code. Here's an example from a previous class ...
These will start out as simple substitution codes, but will get progressively more difficult as
we advance through the course.
Naturally, you'll have to decode the exam before you can even begin!