Math 335: Introduction to Cryptology

Course Home Page
Instructor:
Edward Swartz
Office: 592 Malott Hall
Phone : 255-1443
Email: ebs@math.cornell.edu
Office Hours: Mondays 3:30-4:30, Wednesdays 1:20-2:20, Thursdays 2:45 Extra office hour Thursday 4/15: 1:45 - 3:45.  Also, by appointment.
Finals week: 3-5 pm beginning Wed. 5/12


Teaching Assistant:
André Allavena

Office: 421 Rhodes
Office hours: Tues. 1:30 - 2:30, Thurs. 1:30-2:30
Text:
CRYPTOGRAPHY: Theory and Practice, 2nd ed.
D. Stinson
Course description:
The goal of this course is to introduce students to the algorithmic and mathematical concepts in modern cryptanalysis.  The mathematical prerequisites are completion of one of the calculus sequences through Math 222 or Math 294.  We also require CS 100 or its equivalent. At a minimum, the topics will include the following.

 
    Security vs. feasibility and the different types of crytographic attack as seen through codes from "pre-computer" times. 
   
    Elementary probability such as random variables, conditional probability and independence notions. 
   
    Number theory: primality tests, Euclidean algorithm, Chinese remainder theorem, finite fields, quadratic residues, factoring algorithms.
   
    Cryptograhic hash functions in general and in the contexts below.
   
     Secret key cryptography (including Advanced Encryption Standard).
    
     Public key methods.  Both implementation and attacks of RSA,  ElGamal, and  various signature schemes.
    
Grading: HW: 30%, Prelim 1: 20%, Prelim 2: 20%, Final exam: 30%

Prelim 1: Monday March 1.  No calculators or notes.  Several formulas for entropy will be provided if necessary.
  This prelim will cover Chapters 1 and 2 in the text that were covered in class.  It will also cover the material on the Euclidean algorithm, extended Euclidean algorithm and multiplicative inverses in Zn  and finite fields that was discussed in class.  Some, but not all, of this material can be found in sections 5.2 and 6.4 of the text.  

Prelim 2 - April 16 - Includes up to HW 8. This includes (but is not limited to): Finite fields, Lagrange's Theorem - especially Little Fermat's thm, Mobius inversion, primitive elements of finite fields, RSA, Rabin cryptosystem,Square and Multiply, Quadratic residues (including Euler's criterion), factoring by finding non-trivial square roots, Chinese Remainder Theorem, Continued Fractions. Familiarity (but not memorization) with more complicated algorithms such as Miller-Rabin primality testing or p-1 method of factoring.

Final Exam - Available in class 5/7 or online later that day. Will be due 5/18 5:30 pm. Final Exam
(NOTE: The separation into groups of 5 in problem number 1 is for convenience only. It has no relation to the actual word grouping or length of any potential key. ).

Most recent lecture topics:

2/23 and 2/25 - Detailed description of AES. (Section 3.6 of text)
2/27 - HW 4 solutions
3/3 - Solutions to Prelim 1 and Chinese Remainder Theorem (Section 5.2.2 of text)
3/5 - Lagrange's Theorem
3/8 - RSA
3/10 - Mobius Inversion. Primitive elements of fields
3/12 - Miller-Rabin algorithm (pg. 179-180). Intro. to Quadratic residues
3/15 - Euler's criterion (pg. 174), Section 5.7.2
3/17 - Factoring
3/19 - Wiener's low decryption attack.
3/29 - Rabin Crypto system (sect. 5.8), Application to zero-knowledge proof
3/31 - ElGamal (Sections 6.1,6.2.1)
4/2 - Pohlig-Hellman and Bit security of Disc. Log (Sections 6.2.3 and 6.7.1)
4/5 - Index Calculus (Section 6.2.4), RSA Signature Scheme (Sect. 7.1)
4/7 - Intro. to Crptographic Hash functions.
4/9 - Random Oracle model
4/12 - Iterated hash functions, SHA-1
4/14 - El Gamal signature scheme
4/19 - 4/21 - Security of El Gamal Signature Scheme (Section 7.3)
4/23 - 4/28 - Schnorr Signature Scheme (section 7.4.1) and Undeniable Signatures (Section 7.6)
4/30 - Secret Sharing (not in text)
5/3 and 5/5 - Intro to Elliptic curves. (Section 6.5-6.5.3 in text)

Homework:
HW1     Comments
HW2     Comments
HW3     Abbreviated solutions   Corrected 5:30 pm 2/27- Graded HW will be available Sat. 2/28 10 am outside Malott 592
HW4   Comments
HW5
HW6   Comments
HW7   Comments
HW8 Comments
HW9   Problem 6.9 in Text should reference Problem 5.12, not 5.6.   Comments
HW10  Comments
Note: Problem 4.1 c in text should read 2S + N - N^2/M
No more HW!