Two exam review sessions will be scheduled
before exams to compensate for the skipped lectures Jan 6,8.

Week 1.  Jan 11,13,15
Review of algebra, Euclidean algorithm, modular arithmetic,
prime numbers, factorization, finite fields
IMC, Sections 1.1-1.4.

Week 2. Jan 20,22
From algebra to cryptosystems, algorithms for finite fields, powers by squaring, primitive roots,
historical introduction to early cryptosystems, symmetric and asymmetric ciphers
IMC, Sections 1.5-1.7

Week 3. Jan 25,27,29
Diffie-Hellman, the birth of public key cryptography, discrete logarithms, El Gamal cipher
IMC, Sections 2.1-2.4

Week 4. Feb 1,3,5
Basic computational complexity, counting bit operations, polynomial time algorithms, Fermat’s little theorem and Euler’s formula, the RSA cryptosystem,
IMC, Sections 2.6, 3.1, 3.2,

Week 5. Feb 8,10,12
Complexity of the discrete log problem, survey lecture on quantum computing and future implications, RSA attacks and countermeasures, primality testing
IMC, Sections 3.3-3.4, 5.7, 8.11

Week 6. Feb 15,17,19
Integer factorization, Pollard’s p-1 algorithm, factorization by differences of squares, cryptographic applications,
quadratic reciprocity and Goldwasser-Macali cryptosystem (optional)
IMC, Sections 3.5, 3.6, (3.9)

Week 7. Feb 22,24,26
digital signatures, RSA signatures
IMC, Sections 4.1, 4.2, 4.3
** midterm exam **

Week 8. Mar 0,2,4
Basic probability, review of counting problems, Bayes’s theorem
IMC, Sections 5.1-5.3

Week 9. Mar 14,16,18
Information theory, basic definitions from Shannon, entropy with examples, applications to one-time pads, perfect secrecy, and password entropy
IMC, Section 5.6

Week 10. Mar 21,23,25
elliptic curves, curves over finite fields, addition law, EC discrete logs
IMC, Sections 6.1, 6.2, 6.3

Week 11. Mar 28,30,32
more elliptic curve cryptography, Lenstra’s elliptic curve factorization algorithm
IMC, Sections 6.4, 6.5, 6.6

Week 12. Apr 4,6,8
Hash functions, pseudorandomness, bitcoin
IMC, Sections 8.1, 8.2, 8.8

Week 13. Apr 11,13,15
Zero Knowledge Proofs, further applications to cryptography
IMC, Sections 8.3, 8.4

Week 14 Apr 18,20,22
more applications of cryptography as time permits such as obfuscation, homomorphic encryption,
IMC, Section 8.9


Final: Wednesday April 27, 2016, 2:00-3:50pm.