Cryptography — Mathematics 1580
Detailed Syllabus and Homework Assignments
Brown University — Fall, 2012
Professor Joe Silverman
Solutions are available for selected homework problems. Click on the highlighted links below the problem numbers.
Return to the Math 158 Home Page
| Class # | Date | Topic | Read | HW Assignment | HW Due |
|---|---|---|---|---|---|
| 1 | Weds, Sept 05, 2012 | Introduction to cryptology | § 1.1 (not § 1.1.1) | # 1.2(b), 1.3, 1.5(a) | Mon Sept 10 |
| 2 | Fri, Sept 07, 2012 | Divisibility and gcd | § 1.2 | # 1.6(c), 1.7(b), 1.8(b), 1.9(b,c), 1.10(c), 1.13 | Mon Sept 10 |
| 3 | Mon, Sept 10, 2012 | Modular arithmetic | § 1.3 | # 1.15(a,c), 1.16(b,e), 1.17(b,c), 1.18, 1.21(a), 1.23(a)
Solution to 1.18 |
Weds Sept 19 |
| 4 | Weds, Sept 12, 2012 | Primes, finite fields, primitive roots | § 1.4, 1.5 | # 1.26, 1.28, 1.29, 1.30(a), 1.32(a)
Solution to 1.29 |
Weds Sept 19 |
| 5 | Fri, Sept 14, 2012 | Brief history of cryptology Symmetric and asymmetric ciphers |
§ 1.6, 1.7 | # 1.39, 1.40, 1.43, 1.45, 1.46 | Weds Sept 19 |
| Mon, Sept 17, 2012 | No class - Rosh Hashanah | — | |||
| 6 | Weds, Sept 19, 2012 | Birth of public key crypto Discrete logarithm problem (DLP) Diffie-Hellman key exchange |
§ 2.1, 2.2, 2.3 | # 2.3, 2.4(a,c), 2.6, 2.7(a) | Mon Sept 24 |
| 7 | Fri, Sept 21, 2012 | Diffie-Hellman key exchange Elgamal public key cryptosystem |
§ 2.3, 2.4 | # 2.8, 2.9, 2.10 | Mon Sept 24 |
| 8 | Mon, Sept 24, 2012 | Groups / Difficulty of DLP | § 2.5, 2.6 | # 2.11, 2.12, 2.13, 2.14(a,c), 2.16(b,c,f) | Mon Oct 1 |
| Weds, Sept 26, 2012 | No class - Yom Kippur | — | |||
| 9 | Fri, Sept 28, 2012 | DLP collision algorithm Chinese remainder theorem |
§ 2.7, 2.8 | # 2.17(a), 2.18(a,b) | Mon Oct 1 |
| 10 | Mon, Oct 01, 2012 | Euler's formula | § 3.1 | # 3.1(b,c), 3.3, 3.4(a,b) | Weds Oct 10 |
| 11 | Weds, Oct 03, 2012 | RSA public key cryptosystem | § 3.2, 3.3 | # 3.6, 3.8(b), 3.9(a,b), 3.11(b)
Solution to 3.9 |
Weds Oct 10 |
| 12 | Fri, Oct 05, 2012 | Exam #1 — Chapters 1 & 2 | — | ||
| Mon, Oct 08, 2012 | No class - Brown holiday | — | |||
| 13 | Weds, Oct 10, 2012 | Digital signatures — RSA | § 7.1, 7.2 | # 7.1, 7.2 | Mon Oct 16 |
| 14 | Fri, Oct 12, 2012 | Digital signatures — Elgamal & DSA | § 7.3 | # 7.4, 7.5, 7.6, 7.7
Solution to 7.7 |
Mon Oct 16 |
| 15 | Mon, Oct 15, 2012 | Intro to Lattice Crypto (Hoffstein) | § 6.10–6.13 | # 6.27, 6.28, 6.49, (Extra Credit: 6.50)
Solutions to 6.27, 6.28, 6.49, 6.50 |
Mon Oct 22 |
| 16 | Weds, Oct 17, 2012 | Intro to Lattice Crypto (Hoffstein) | — | — | Mon Oct 22 |
| 17 | Fri, Oct 19, 2012 | Intro to Lattice Crypto (Hoffstein) | — | — | Mon Oct 22 |
| 18 | Mon, Oct 22, 2012 | Primality testing | § 3.4 | # 3.13(a,b-ii,c,d), 3.14(b,c), 3.18 Correction # 3.14(c) should be n = 294439. Solutions to 3.13, 3.18 |
Weds Oct 31 |
| 19 | Weds, Oct 24, 2012 | Pollard p-1 method
Factorization via x2 - y2 |
§ 3.5, 3.6 | # 3.21(a,b), 3.22(a,c,d,e,f), 3.23(a,b) | Weds Oct 31 |
| 20 | Fri, Oct 26, 2012 | Factorization via x2 - y2
Smooth numbers |
§ 3.6, 3.7 | # 3.24(b), 3.25(a,b), 3.26(a,b), 3.27(a,b,c) | Weds Oct 31 |
| Mon, Oct 29, 2012 | No Class. Brown closed due to weather | — | |||
| 21 | Weds, Oct 31, 2012 | Smooth numbers and sieves | § 3.7 | # 3.28, 3.29
Solutions to 3.28, 3.29 |
Mon Nov 5 |
| 22 | Fri, Nov 02, 2012 | Sieves | § 3.7 | # 3.33
Solution to 3.33 |
Mon Nov 5 |
| 23 | Mon, Nov 05, 2012 | Index calculus and DLP | § 3.8 | # 3.35 | Mon Nov 12 |
| 24 | Weds, Nov 07, 2012 | Quadratic reciprocity | § 3.9 | # 3.36, 3.38, 3.39 | Mon Nov 12 |
| 25 | Fri, Nov 09, 2012 | Exam #2: Chapter 3, Sections 3.1–3.7 Chapter 6, NTRU cryptosystem Chapter 7, Sections 7.1–7.3 | — | ||
| 26 | Mon, Nov 12, 2012 | Probabilistic encryption | § 3.10 | # 3.41, 3.42 | Mon Nov 19 |
| 27 | Weds, Nov 14, 2012 | Elliptic curves | § 5.1 | # 5.1, 5.2, 5.4 | Mon Nov 19 |
| 28 | Fri, Nov 16, 2012 | Elliptic curves over finite fields | § 5.2 | # 5.5(a,b), 5.6(b), 5.7(c,d) | Mon Nov 19 |
| 29 | Mon, Nov 19, 2012 | Elliptic curve discrete log problem and elliptic curve cryptography |
§ 5.3, 5.4 | # 5.8, 5.9, 5.10(a), 5.11(a,b), 5.13(a,b), 5.15 | Mon Nov 26 |
| Weds, Nov 21, 2012 | Special topic: Elliptic Curves | — | |||
| Fri, Nov 23, 2012 | No class — Thanksgiving | — | |||
| 30 | Mon, Nov 26, 2012 | Lenstra's elliptic curve factorization algorithm |
§ 5.6 | # 5.18(a,b) | Mon Dec 3 |
| 31 | Weds, Nov 28, 2012 | Combinatorics | § 4.1 | # 4.2, 4.3, 4.4(acb), 4.6(a,c), 4.7, 4.8 | Mon Dec 3 |
| 32 | Fri, Nov 30, 2012 | Probability theory I | § 4.3 | # 4.20(a,b,c), 4.21(a,b,c), 4.22, 4.23(a,b), 4.24, 4.25 | Mon Dec 3 |
| 33 | Mon, Dec 03, 2012 | Probability theory II | § 4.3 | # 4.27, 4.29, 4.30, 4.32(a,b) | Mon Dec 10 |
| 34 | Weds, Dec 05, 2012 | Collision algorithms | § 4.4 | # 4.34, 4.35, 4.36(a), 4.37 | Mon Dec 10 |
| 35 | Fri, Dec 07, 2012 | Pollard rho method | § 4.5 | # 4.38, 4.39 | Mon Dec 10 |
| 36 | Mon, Dec 10, 2012 | Information theory I | § 4.6 | # 4.42, 4.43, 4.44
Solutions to 4.42-4.44 |
Will not be collected. Do this HW and check against the posted solutions. |
| 37 | Weds, Dec 12, 2012 | Information theory II | § 4.6 | # 4.48, 4.49, 4.51(a), 4.53
Solutions to 4.48-4.53 |
Will not be collected. Do this HW and check against the posted solutions. |
| Wed, Dec 19, 2012 | Review and Q & A Session | 1:00–2:00pm — Barus-Holley 158 | |||
| Fri, Dec 21, 2012 | Final Exam | Wilson 302 — 2:00–5:00pm |
Return to the Math 158 Home Page