Readings are assigned from:

Hoffstein, Pipher, and Silverman: An introduction to Mathematical Cryptography

Here is a useful page for doing large integer computations:

http://www.wolframalpha.com/

Assignments will be posted one week in advance of their due date, so make sure you press Ctrl-R to reload!

	WEEK LECTURE TOPICS READING HOMEWORK Week 1 01/20, 01/23 Introduction Shift/substitution ciphers, frequency analysis 1.1-1.2, 1.6 1.1, 1.3, 1.4(a,b), 1.6 Due 1/30 Read about: Atbash Al-Kindi Mary, Queen of Scots Zimmermann Telegram News from a few days ago Week 2 01/27, 01/30 SNOW DAY 1/27 Division algorithm Euclidean algorithm Polynomial running time 1.2 1.7, 1.8, 1.9, 1.10 1.11 Due 2/03 Week 3 02/03, 02/06 2/06: QUIZ Modular arithmetic, Prime numbers, unique factorization Fermat's Little Theorem 1.3-1.4 1.11, 1.14, 1.15(c,d), 1.16(a,c,g), 1.17(c,d,e), 1.19, 1.20, 1.25(a), 1.28(c), 1.29(a) Read about: Fermat's Last Theorem Andrew Wiles News from a few days ago Due 2/10 Week 4 02/10, 02/13 Powers and primitive roots Discrete log, Diffie-Hellman 1.5,1.7, 2.1-2.3 1.30(a,b), 1.31, 1.32(a,c(i,ii),d), 1.33, 1.34(b(i-iii),c,d), 1.41, 1.42(a), 1.44(a,b), 1.48 Write out the power table mod 11. How many numbers have order 10? 5? 2? How does this compare to Gauss's theorem? Read about: P vs NP Arthur Scherbius Hans-Thilo Schmidt Marian Rejewski Alan Turing News from a few days ago Due 2/17 Week 5 02/17, 02/20 Extra Office Hours: Wed 2/18, 2-3 Fri 2/20, 2-3 Mon 2/23, 1-2 Public key, asymmetric ciphers, one-way functions, Diffie-Hellman 2.1-2.3 2.1 (write just one paragraph, and only for the side with which you agree), 2.3, 2.4(a,b), 2.5, 2.6 Watch: Rutgers Hack-a-thon Read about: The original Diffie-Hellman paper James Ellis Malcolm Williamson PGP Phil Zimmermann News from a few days ago News from a few days ago Due 2/20 Week 6 02/24, 02/27 2/24: MIDTERM 1 ElGamal, collision 2.4-2.7 2.8(a-c), 2.9, 2.17(a) Read: News from a few days ago Due 3/03 Week 7 03/03, 03/06 Chinese remainder, Pohlig-Hellman Quadratic residues 2.8-2.9 2.18(a,d,e), 2.19, 2.20 (note that `x=a+cn' should be 'x=a+cm'), 2.21, 2.23(a,c), 2.24(a,b,c,e), 2.28(a) Read about: Sun Tzu The Art of War Sophie Germain and her Primes The mathematician Sun Tzu, not to be confused (as in class) with the military theorist above Due 3/10 Week 8 03/10, 03/13 RSA Man-in-the-middle attacks Pollard p-1 3.1-3.3, 3.5 Note: You may now use Wolfram Alpha to compute modular powers but NOT to factor integers 3.1(a,b,c) (Hint: 97 and 541 are prime, and 1159=19x61), 3.3, 3.4, 3.5(a,b(i-ii)) (Hint: 77 divides 1463), 3.6, 3.8 (a,b), 3.9 (a,b,c), 3.11, 3.12, 3.21 Read about: The original RSA paper Clifford Cocks RSA patent fun RSA video News from a few days ago Kryptos Competition Due 3/24 Week 9 03/17, 03/20 SPRING BREAK Week 10 03/24, 03/27 Extra Office Hours: Wed 3/25, 3:15-4:45 in 425 Hill 3/27: QUIZ Primality testing Factorization via difference of squares Relation building with Smooth numbers 3.4, 3.6 3.13(a,b(i-ii)), 3.14(a,b,c - should be n = 294439), 3.23(a,b), 3.24(a,b), 3.25(a,b), and Problem (see 3.9/3.15): Alice publishes her RSA modulus N=38749709 and the encryption exponent e=10988423. An oracle gives you the decryption exponent d=16784693. Factor N. Read about: The Riemann Hypothesis Mathematica file from class (Right click to Save As) and the corresponding pdf file Due 3/31 Week 11 03/31, 04/03 Extra Office Hours: Thurs 4/02, 3:30-4:30 pm in 542 Hill Index calculus and discrete logs REVIEW 3.8 3.35, and Hand in corrections to all mistakes from Quiz 2 and all homeworks since Midterm 1 Here is the Mathematica file from class (Right click to Save As) and the corresponding pdf file Due 4/03 Week 12 04/07, 04/10 Extra Office Hours: Mon 4/06, 3-5 pm in 705 Hill 4/7: MIDTERM 2 Birthday ``paradox'' Collision attacks 4.4 4.26(a-d), 4.34(a-b), 4.35(a), and Hand in corrections to Midterm 2 Read about: Johnny Carson Birthday Paradox News from a few days ago Due 4/14 Week 13 04/14, 04/17 Meet-in-the-middle Pollard rho Vigenere cipher Kasiki attack Index of coincidence 4.2, 4.5 4.38, 4.39, 4.10, 4.11, 4.15(a), 4.16, 4.17 Extra credit: 4.18 Extra credit 2: Solve the "Cheryl Birthday" Paradox Read about: Leon Alberti Charles Babbage Friedrich Kasiski Civil war Vigenere William Friedman News from a few days ago News from a few days ago News from a few days ago Mathematica file from class Due 4/21 Week 14 04/21, 04/24 4/24: QUIZ Elliptic Curves Elliptic Curve Cryptography 5.1-5.5 5.1, 5.2, 5.3, 5.4(a,d), 5.5(a,b), 5.6(a), 5.8, 5.10(a), 5.13(a,b) Read about: The Congruent Number Problem News from a few days ago Mathematica file from class Due 4/28 Week 15 04/28, 05/01 REVIEW 1.1-5.5 A special presentation Week 16 05/06 REVIEW SESSION Wed May 6 11 am - 2 pm Hill 124 Mathematica file for Elliptic Curve Pollard Rho and the corresponding PDF file Mathematica file for Pollard Rho Factoring and the corresponding PDF file You might find this interesting You might find this interesting You might find this interesting News from today Week 17 05/13: FINAL EXAM: 5/13, 8 - 11 am