General Information (Catalog listing)
Applications of algebra and number theory to cryptography (encryption/decryption) and cryptanalysis (attacking encrypted messages). Topics include congruences, finite fields, finding large primes, pseudoprimes, and primality testing, as well as the Vigenere and Hill ciphers, the Data Encryption Standard, probabilistic, and trapdoor attacks on encrypted messages, and public key ciphers.
Prerequisites: 01:640:250 Linear Algebra; one of 01:640:300, 356, or 477, or permission of department.
This is an introduction to modern cryptology: making and breaking ciphers.
Topics to be covered include: Symmetric ciphers and how to break them, including DES and AES, Public Key/Private Key Ciphers and their weaknesses. The appropriate mathematical background will also be covered.
Text: Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman; An Introduction to Mathematical Cryptography;Springer, 2008 (523 pp.); (ISBN13: 978-0-387-77993-5)
Sections Taught This Semester:
- Spring 2013: Sec 01 Prof. Miller
- Spring 2012: Sec 01 Prof. Tunnell
- Spring 2011: Sec 01 Prof. Miller
- Spring 2009: Sec 01 Prof. Munshi
- Spring 2008: Sec 01. Prof. Weibel
- Spring 2007: Sec 01 Prof. Munshi
- Spring 2006: Sec 01 Prof. Miller
- Spring 2005: Sec 01 Prof. Tunnell
- Spring 2004: Sec 01 Prof. Weibel
- Fun facts from 2004
In May 2004, the US found out that Ahmed Chalabi had told Iran that the United States had broken the Iranian intelligence service's secret communications code. How? The Iranians didn't believe it, and cabled a report to Teheran using the broken cipher - which the US decrypted!
Fun Facts about Mersenne primes:
In 1644, a French monk named Marin Mersenne studied numbers of the form N=2p-1, where p is prime, and published a list of 11 such numbers he claimed were prime numbers. Such prime numbers are called Mersenne primes. (He got two wrong.) The first few Mersenne primes (p=2,3,5,7) are 3,7,31,127, and p=11 gives the non-prime 2047=23*89 (as was discovered in 1536 by Hudalricus Regius).
Not all numbers of the form 2p-1 are prime, as Regius' example 2047 (p=11) shows. The next few primes for which 2p-1 is not prime are p=23 and p=37 (discovered by Fermat in 1640), and p=29 (discovered by Euler in 1738). By the end of World War II, all 12 of the Mersenne primes with p<258 had been completely checked by hand.
Of course, after this point all calculations have been carried out by computers. For more details, see the Mersenne prime website. Over the next 50 years, the number of known Mersenne primes grew to 34, with the largest having almost 100,000 digits. Each Mersenne prime N=2p-1 has p log10(2) digits.
Starting in 1995, the Electronic Frontier Foundation (EFF) offered a $50,000 prize for the first known prime with over 10 million digits. If a Mersenne prime won its prime p would have to be over 33 million. The race was on.
As part of this race, the 40th Mersenne prime was discovered in 2003 by a 26-year-old graduate student in chemical engineering, Michael Shafer. The number is 2^p-1 with p=20,996,011, and is 6,320,430 digits long. At the time, it was only known to be the largest among all 40 known Mersenne primes. It took seven years (until July 2010) to confirm that this is the 40th Mersenne prime (i.e., there are only 39 smaller ones).
The race to win the EFF prize came down the wire in Summer 2008, as the 45th and 46th known Mersenne primes were discovered in within 2 weeks of each other by the UCLA Math Department (who won the prize) and an Electrical Engineer in Germany, respectively. The 45th known has 13 million digits and p=43,112,609; it is larger that the 46th known, which has only 11 million digits.
More recently, the 47th known Mersenne prime was discovered in April 2009 by a Norwegian named Odd Magner Stridmo, with p=42,643,801. Surprisingly, it is slightly smaller (by 141,000 digits) than the 45th Mersenne prime. For more information, check out the Mersenne prime.