## Math 295A/395A: Cryptography

### Fall 2008

**Course Info:**

**Course:**Cryptography**Lectures:**Monday, Wednesday, Friday, 1:25 - 2:15 p.m.**Dates:**Wednesday, 3 September - Wednesday, 10 December 2008**Room:**Lafayette L102 (*New room will accommodate a larger class!*)**Instructor:**John Voight**Office:**16 Colchester Ave, Room 207C**Phone:**(802) 656-2271**E-mail:**jvoight@gmail.com**Office hours:**Mondays, 11:00 a.m. - 12 noon, 2:30 p.m. - 3:30 p.m.; Wednesdays, 11:00 a.m. - 12 noon; or please make an appointment!**Course Web Page:**http://www.cems.uvm.edu/~voight/295/**Instructor's Web Page:**http://www.cems.uvm.edu/~voight/**Prerequisites:**Math 52 (or Math 54) or Math 124 or permission.**Required Text:**Wade Trappe and Lawrence C. Washington,*Introduction to Cryptography with Coding Theory*, second edition, Prentice Hall, 2005.**Recommended Text (295A):**Johannes Buchmann,*Introduction to Cryptography*(Undergraduate Texts in Mathematics), second edition, Springer, 2004.**Recommended Text (395A):**Jeffrey Hoffstein, Jill Pipher, J.H. Silverman,*An Introduction to Mathematical Cryptography*(Undergraduate Texts in Mathematics), Springer, 2008, and its homepage.

**Syllabus:**

[**PDF**]
**Syllabus**

We live an information age, with technology increasingly integrated into our daily lives. As a result, the security of our information is of the utmost concern, even as the interconnectedness of the Internet makes our data more vulnerable to attack. The ability to encrypt secrets and to conduct a trusted exchange of digital information, once a subject of interest primarily to governments and the military, is now a matter of necessity for us all.

At the end of the day, the foundation of modern cryptography relies upon the difficulty of solving certain mathematical problems; this course is intended to address them from both a mathematical and algorithmic point of view. We will cover some subset of the following topics: conventional encryption techniques, the Hill cipher, DES and SDES, RSA, the Rijndael cipher, discrete logarithms and the Diffie-Hellman key exchange, and elliptic curve cryptography.

All mathematical objects will be defined, so the prerequisites are minimal: Math 52 or 124, or permission should suffice. The course will be offered at a 295 level intended for undergraduates with a minimal background and at a 395 level for graduate students or others who are seeking a challenge. Computationally-minded individuals are especially welcome! The class will be driven by applications and examples.

[**PDF**]
**Course Advertisement**

**Homework:**

Homework is due on Wednesdays. Be sure to show your work and explain how you got your answer. Correct but incomplete answers will only receive partial credit.

Some of the problems may require you to consult the text---this is an intentional effort to encourage you to read the required and recommended books throughout the course.

Cooperation on homework is permitted (and encouraged), but if you work together, do not take any paper away with you---in other words, you can share your thoughts (say on a blackboard), but you have to walk away with only your understanding. In particular, write the solution up on your own.

Certain problems will be computational in nature and the use of computer algebra packages such as Mathematica or Sage is encouraged. Please print out and attach your work. The use of computers is permitted on other problems, but should not take the place of practice and conceptual understanding.

Solutions are available upon request!

[**PDF**]
**Homework #1 (due September 10)**

[**PDF**]
**Homework #2 (due September 17)**

[**PDF**]
**Homework #3 (due September 24)**

[**PDF**]
**Homework #4 (due October 1)**

[**PDF**]
**Homework #5 (due October 8, updated September 30)**

[**PDF**]
**Homework #6 (due October 15)**

[**PDF**]
**Homework #7 (due October 22)**

[**PDF**]
**Homework #8 (due October 29; modified October 20)**

[**PDF**]
**Homework #9 (due November 5)**

[**PDF**]
**Homework #10 (due November 12)**

[**PDF**]
**Homework #11 (due November 19; modified November 17)**

[**PDF**]
**Homework #12 (due December 10)**

**Computational Resources:**

Sage is free software for algebra and number theory. See the download instructions to install it on your machine.

Alternatively, you can open a Sage worksheet by connecting to chaka.uvm.edu (link will only work on campus or on a machine with a VPN client installed); or just go to the Sage notebook, which is hosted by William Stein at the University of Washington.

Mathematica can be download and installed here.

**Final Cipher Challenge:**

There will be no exams in the course. In place of a final exam, there will be a final cipher challenge.

**Links:**

- SDES Key Creation Simulator by Eric Fikus and Jedidiah Crandall.
- Enigma simulator by Dirk Rijmenant for Windows.
- Enigma simulator by Terry Long for Mac OS X (untested).
- Goodbye, passwords! from the New York Times.
- A list of additional reading for some of the topics we will cover, assembled by Menezes.
- Just one example of a failed cryptosystem in real life.
- PGP, IBM help Bletchley Park raise funds
- The Few Milliseconds of an HTTPS Connection
- Photos of the Enigma Machine
- Cat and Mouse
- Petition for Alan Turing