George J. Schaeffer
Cryptography (Math 116) Summer 2012

Course information

Basic information about the course is contained in the following pdf file.

Accessing the textbook electronically

If you are on the UC Berkeley campus network, individual chapters of the textbook can be downloaded here (click the "Download PDF" link above the textbook reader).
If you aren't currently on the network and need the textbook, email me (gschaeff@math.berkeley.edu).

Textbook errata

Unavoidably, the textbook contains some small errors. A list of known errata can be found here. If you think you've found another error, please let me and/or the authors know!

Syllabus

Week 1: We will cover all of Chapter 1 and parts of Chapter 2, up to and including Section 2.3.

Week 2: Sections 2.3–2.9.

Week 3: Review of Chapter 3 and Sections 3.1–3.2.

Week 4: Sections 3.3–3.7.2 and extra material on RSA attacks (see PDF below).

Week 5: Sections 3.8–3.10.

Week 6: Material on finite fields (similar but not as exhaustive as Section 2.10), sections 5.1–5.4, Schoof's algorithm.

Week 7: Sections 5.5, 5.9.1, 5.9.2, 5.10.1, and 7.1–7.3. A brief introduction to cryptographic hashing functions.

Week 8: Security recommendations and standards. Review for the final exam.

Homework

Assignment 1, due Thursday, June 21st.

• (Part A.) Read Sections 1.2 and 1.3 (pp. 10–26) and do problems 1.9, 1.10, 1.11, 1.16, and 1.18. Optional problems: 1.20 and 1.21.
  Come prepared to discuss these problems on Tuesday, June 19th.
• (Part B.) Read Sections 1.4 and 1.5 (pp. 26–34) and do problems 1.26, 1.30, 1.32d, and 1.36.

Assignment 2, due Monday, June 25th.

• Read Section 1.7 (pp. 36–47) and Sections 2.1–2.2 (pp. 59–65), and do problems 1.45, 1.46, 2.3, 2.4, and 2.5.
• Work through the example computations (and try some of your own!) in the SAGE worksheet (link below).

Assignment 3, due Thursday, June 28th.

• Read Sections 2.3–2.8 (pp. 65–86) and do problems 2.6, 2.8, 2.9, 2.12, 2.17a, and 2.25. Doing problems 2.6 and 2.8 will require SAGE or something similar!

Selected solutions to assignments 1–3.

Assignment 4, due Monday, July 9th.

• Read Sections 3.1–3.2 (pp. 113–122) and do problems 3.1, 3.4, 3.6, 3.9ab, and 3.10.

Assignment 5, due Thursday, July 12th.

• Read Sections 3.3–3.6 (pp. 122–145) and do problems 3.12, 3.14ab, 3.21, 3.22e, 3.23ab.

Assignment 6, due Tuesday, July 17th.

• Read Sections 3.7 (pp. 145–162) and do problem 3.27.

Assignment 7, due Thursday, July 19th.

• Read Sections 3.9–3.10 (pp. 165–175) and do problems 3.36, 3.37, 3.40, and 3.42.

Selected solutions to assignments 4–7.

Assignment 8, due Thursday, July 26th.

• Read Sections 5.1–5.2 (pp. 279–290) and do problems 2.36, 2.39, 5.2, 5.3, 5.6a, 5.7.

Assignment 9, due Tuesday, July 31st.

• Read Sections 5.3–5.4 (pp. 290–298) and do problem 5.15a. Also, read and complete the exercises in the worksheet on Schoof's algorithm below.

Assignment 10, due Thursday, August 2nd.

• Read Sections 5.5, 5.9.1, 5.9.2, and 5.10.1 (pp. 325–330 and pp. 334–336) and do problems 5.16a, 5.34, 5.35, and 5.43.

Assignment 11, due Monday, August 6th.

• Read Sections 7.1–7.3 (pp. 436–447) and do problem 7.8.

Assignment 12, due Tuesday, August 7th.

• Bring review questions to class!

Selected solutions to assignments 8–11.

Worksheets and Other Stuff

Modular arithmetic (6/20): worksheet, solutions.

SAGE (6/21): worksheet. Link to SAGE!

A relatively elementary proof that ζ(2) = π²/6 (7/11).

Some additional attacks on RSA.

Wiener's attack and quadratic reciprocity (7/17): worksheet, solutions.

Schoof's algorithm for counting points on elliptic curves (7/26): worksheet, solutions.

Exams

Midterm 1, Tuesday, July 3rd. The exam and solutions.

• Chapter 1, except for sections 1.1 and 1.6.
• Chapter 2, except for sections 2.1 and 2.10. For section 2.9, you are only responsible for knowing the runtime improvement given by the Pohlig–Hellman algorithm over BS–GS.

Midterm 2, Monday, July 23rd. The exam and solutions.

• Everything in sections 3.1–3.6, 3.7.2, 3.9, and 3.10.
• Section 3.7.1: I do not expect you to know this section in detail, just the definition of L(X) and the approximate value for B.
  You also do not have to know any of the order notations (big-Omega, little-O, etc.) aside from big-O.
• The exam will also contain material on some basic attacks on RSA, namely those in Section 3.3 of the book and in the PDF on attacks under "Worksheets and Other Stuff" above.
• Finally, old material covered by Midterm 1 could show up on Midterm 2.

Final, Thursday, August 9th. The exam with solutions.

• All material from Midterms 1 and 2.
• Working knowledge of finite fields: Quotients of F_p[X] by irreducible polynomials, arithmetic, the Frobenius.
• Sections 5.1–5.5, 5.9.1, 5.9.2, and 5.10.1. Also be sure to know the more general version of Hasse's theorem for F_q, Theorem 5.26.
• For the Weil pairing, you should know Theorem 5.38 (properties of the Weil pairing). Remark 5.39 provides our working description of the Weil pairing, and also know that there is an efficient algorithm for computing the pairing (Miller's algorithm—this is the subject of Section 5.8.4, but you don't need to know the specifics).
• Sections 7.1–7.3 (you do not have to memorize the DSA).
• As for material not in the book, be sure you remember that E(F_q) is isomorphic to Z/mZ × Z/mnZ for some m not divisible by p. You should also be familiar with the material on Schoof's algorithm and some desirable properties of cryptographic hashing functions (e.g., collision resistance and preimage resistance).