MAD6478 Cryptanalysis (Spring 2017)

Instructor:  Dr. Shi Bai
Office:  SE230 of Science & Engineering Bldg
Email:  sbai@fau.edu
Lecture time and location:  M W 5:30PM-6:50PM in FL404 (Fleming Hall).
Syllabus and outline (pdf)
Assignment 1 (due Feb 20)
Assignment 2 (due Apr 19)

Schedule

 
Lectures Dates Mon Literature
1 09/Jan Introduction and course organization; review of PKE scheme. [Gal12, Ch. 1]  
2 11/Jan Review of textbook RSA; security notions and attack models;
attacks for RSA. 		[Gal12, Ch. 1 and Ch. 24]
3 18/Jan Attacks on RSA parameters: Wiener attack etc. [Gal12, Ch. 24]
D. Boneh. Twenty years of attacks on the RSA cryptosystem
M. Wiener. Cryptanalysis of Short RSA Secret Exponents
4 23/Jan Attacks on RSA variants: CRT-RSA and attacks. [Gal12, Ch. 24]
D. Boneh. Twenty years of attacks on the RSA cryptosystem
5 25/Jan Lattices: definition, Gram-Schmidt, determinant,
minimum distance. 		[Gal12, Ch. 16]
D. Micciancio's Lecture 1
O. Regev's Lecture 1
6 30/Jan Lattices: Minkowski's theorems; lattice problems [Gal12, Ch. 16]
D. Micciancio's Lecture 1
O. Regev's Lecture 1
7 1/Feb Lattices: LLL algorithm. [Gal12, Ch. 17]
D. Micciancio's Lecture 3
O. Regev's Lecture 2
A. K. Lenstra, H. W. Lenstra, L. Lovász. Factoring polynomials with rational coefficients
8 6/Feb Coppersmith method and
more attacks on RSA parameters		 [Gal12, Ch. 17]
D. Micciancio's Lecture 8
O. Regev's Lecture 4
D. Coppersmith. Finding a Small Root of a Univariate Modular Equation
9 8/Feb Knapsack cryptosystem and lattice attack A. M. Odlyzko. The Rise and Fall of Knapsack Cryptosystems
A. M. Frieze. On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
10 13/Feb Composite tests: Fermat, Solovay-Strassen and Miller–Rabin tests. [CrP05, Ch. 3 (eBook FAU)]
11 15/Feb Primality tests: Lucas, Pépin, Proth and Pocklington-Brillhart-Lehmer-Selfridge tests. [CrP05, Ch. 3 (eBook FAU)]
C. Pomerance. Primality testing: variations on a theme of Lucas
12 20/Feb Introduction to elliptic curves [CrP05, Ch. 7 (eBook FAU)]
13 22/Feb ECPP primality tests: Goldwasser-Kilian and Atkin-Morain; ECM. [CrP05, Ch. 7 (eBook FAU)]
S. Goldwasser and J. Kilian. Primality Testing Using Elliptic Curves
H. W. Lenstra. Factoring integers with elliptic curves
14 27/Feb AKS primality test M. Agrawal, N. Kayal and N. Saxena.Primes is in P
15 01/Mar Integer factorization: trial division, sieving, Fermat's and Pollard's Rho method. [Gal12, Ch. 14]
J. M. Pollard. A Monte Carlo method for factorization
R. P. Brent. An improved Monte Carlo factorization algorithm
16/17 Spring Break
18 13/Mar Pollard's Rho method for DLP, Oorschot and Wiener's parallelization. [Gal12, Ch. 14]
J. M. Pollard. Monte Carlo Methods for Index Computation (mod p)
P. C. van Oorschot and M. J. Wiener. Parallel Collision Search with Cryptanalytic Applications
19 15/Mar Integer factorization: Pollard's p-1 method, Lenstra's elliptic curve method. [CrP05, Ch. 7 (eBook FAU)]
J. M. Pollard. Theorems of factorization and primality testing
H. W. Lenstra. Factoring integers with elliptic curves
20 20/Mar Integer factorization: analysis of ECM, Dixon's method. [CrP05, Ch. 7 (eBook FAU)]
A. Granville. Smooth numbers: computational number theory and beyond
J. D. Dixon. Asymptotically fast factorization of integers
C. Pomerance. Analysis and Comparison of Some Integer Factoring Algorithms
21 22/Mar Integer factorization: quadratic sieve. [CrP05, Ch. 6 (eBook FAU)]
C. Pomerance. Smooth numbers and the quadratic sieve
22 27/Mar Number field sieve for integer factorization and DLP. [CrP05, Ch. 6 (eBook FAU)]
A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard. The number field sieve
J. P. Buhler, H. W. Lenstra and C. Pomerance. Factoring integers with the number field sieve
23 29/Mar Parameters for RSA-based schemes;
Pohlig-Hellman algorithm and Baby-step Giant-step for DLP.		 [CrP05, Ch. 5 (eBook FAU)]
Digital Signature Standard: FIPS PUB 186-4
S. Pohlig and M. Hellman. An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance
24 03/Apr Pollard's kangaroo method for DLP;
Parameters for DLP-based schemes.		 J. M. Pollard. Monte Carlo Methods for Index Computation (mod p)
J. M. Pollard. Kangaroos, Monopoly and Discrete Logarithms
S. D. Galbraith, J. M. Pollard and R. S. Ruprai. Computing discrete logarithms in an interval
NIST Special Publication 800-56A Rev2. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography
25 05/Apr Block ciphers: security notions and attack models;
brute-force attacks; Diffie and Hellman's meet-in-the-middle for
multiple encryption; Hellman's tradeoff attack on block ciphers		 [YL14, Ch. 6]
W. Diffie and M. E. Hellman. Exhaustive Cryptanalysis of the NBS Data Encryption Standard
M. E. Hellman A cryptanalytic time-memory trade-off
26 10/Apr Design principles of block ciphers;
substitution-permutation network;
attacks for reduced-round simple SP-network 		[YL14, Ch. 6]
27 12/Apr Linear analysis of block ciphers; piling-up lemma; BKW for LPN [YL14, Ch. 6]
H. M. Heys. A Tutorial on Linear and Differential Cryptanalysis
M. Matsui. Linear Cryptanalysis Method for DES Cipher
28 17/Apr Introduction to quantum computing; quantum key distribution
29 19/Apr Quantum algorithms

List of articles
Each student choose one item in the list for the project. First arrived first served!