Lecture Schedule / News and Updates
- Final Exam scores: Out of 42 total (6pts per problem). Approximate letter grade ranges are
A: 90-100%,
B: 80-89%,
C: 60-79%.Who 1 2 3 4 5 6 7 Tot rabidllama 6 6 5 3 4 5 4 33 j3nlf492a 6 6 6 3 1 4 1 27 aaaaabbbbb 6 6 4 5 6 5 6 38 f9aT2m0r 6 6 6 4 6 4 5 37 xd91rjwf 6 6 5 4 6 6 6 39 idh2h3lkd5 6 6 2 4 6 6 2 32 1029384756 6 6 5 4 2 6 3 32 t5aq1fjo 6 6 5 5 6 6 6 40 1q2w3e4r5t 6 6 6 5 6 6 3 38 9j5zbox5 6 5 6 5 5 6 5 38 oiepruwmb 6 6 6 4 2 5 2 31 V9RMVOW4 6 6 6 5 6 6 6 41 s3d4wk255 6 6 6 5 6 6 2 37 81479057 6 6 5 5 6 6 3 37 - Final Exam: Download the final exam here.
- Due by 5pm on Tuesday, Dec. 13 in 303 Kassar. Slide it under the door if I'm not around (I will be proctoring a calculus exam from 2-5). Note that the Kassar building closes at 5pm!
- You may use the textbook as well as a computer algebra system such as Wolfram alpha, but no other resources, either online or offline.
- Besides the use of a computer algebra system, you may not write computer code to solve the problems.
- You must complete the final on your own -- no collaboration is allowed.
- Please sign the statement on the first page of the exam and submit it with your exam.
- Feel free to email me if you have any questions or need clarification.
- Wed. 12/7: Homomorphic encryption.
- Mon. 12/5: LLL algorithm. Ch. 6.12.
Beware of the following typos in the textbook regarding the LLL algorithm:
p. 409: equation (6.56) the v_(i-1)^* norms should be squared.
p. 410: the equation in the middle of the page should begin with the norm of v_1, not v_i
p. 410: the last equation should have b_j^2, not b_j^*
p. 411: in step 6 of the algorithm it should be v_j, not v_j^* - Fri. 12/2: Gaussian lattice reduction and LLL. Ch. 6.12.
- Wed. 11/30: NTRU as a lattice problem,
lattice reduction algorithms. Ch. 6.11,6.12. - Mon. 11/28: The NTRU cryptosystem. Ch. 6.10
- Thanksgiving break Wed 11/23 and Fri 11/25: No class.
- Mon. 11/21: Convolution polynomial rings
and NTRU. Ch. 6.9,6.10. - Fri. 11/18: Babai's Closest Vertex Algorithm and GGH cryptosystem. Ch. 6.6-6.8.
- Wed. 11/16: Gaussian Heuristic. Ch. 6.5.
- Mon. 11/14: Short vectors in lattices. Ch. 6.5.
- Fri. 11/11: Lattices. Ch. 6.4.
- Wed. 11/9: Vector spaces and lattices. Ch. 6.3, 6.4.
- Mon. 11/7: A subset sum based cryptosystem. Ch. 6.2
- Fri. 11/4: Pollard's rho method continued, P and NP. Ch. 4.5, 4.7.
From xkcd
- Wed. 11/2: Collision algorithms, and Pollard's rho method. Ch. 4.4, 4.5.
- Mon. 10/31: Discrete probability, conditional probability and Bayes's formula. Ch. 4.3.1-4.3.3
- Mon-Fri. 10/23-27: Elliptic curves and cryptography with Prof. Viray. Ch. 5.1-5.6.
- Fri. 10/21: Midterm Exam in class
Exam 1 with solutions.Topics list:
- Basic tools:
- Modular arithmetic
- fast powering
- multiplicative inverses via extended Euclidean algorithm
- Order notation f = O(g), f = \Omega(g)
- Basic number theory:
- gcd, \phi(n)
- Fermat's Little Theorm/Euler's formula a^\phi(n) = 1 ( mod n)
- Chinese Remainder Theorem
- Smooth numbers
- Cryptosystems:
- Diffie-Hellman key exchange
- ElGamal
- RSA
- Algorithms:
- Baby step, Giant step
- Pohlig-Hellman
- Miller-Rabin
- Pollard p - 1
- Quadratic Sieve
- Not on the exam: Distribution of primes, \pi(N), distribution of smooth numbers \psi(N,B), little o notation, L(N), Carmichael numbers, Mersenne primes, that extra algorithm for improving the DLP when the order is a power of a prime, index calculus, quadratic reciprocity, abstract groups.
- Basic tools:
- Wed. 10/19: Quadratic reciprocity and exam review. Ch. 3.9.
- Mon. 10/17: Index calculus. Ch. 3.8
- Fri. 10/14: The quadratic sieve. Ch. 3.7.2.
In class I stated that the quadratic sieve was used to factor the number RSA-129:
114381625757888867669235779976146612010218296721242362562561842935
706935245733897830597123563958705058989075147599290026879543541
into its prime factors
3490529510847650949147849619903898133417764638493387843990820577 and
32769132993266709549961988190834461413177642967992942539798288533.This was actually not part of the original set of RSA numbers, but appeared as a challenge posed by the RSA creators in Martin Gardner's "Mathematical Games" column in Scientific American. They encrypted a message with RSA using this number as a modulus. 1977 predated the invention of the quadratic sieve (due to Pomerance in 1981) and the general number field sieve, and at the time Ron Rivest believed it would not be broken in the forseeable future. It was factored in 1994 to reveal the plaintext "The Magic Words are Squeamish Ossifrage."
- Wed. 10/12: Smooth numbers, the quadratic sieve and relation building. Ch. 3.7.1, 3.7.2.
- Mon. 10/10: No class - Fall Weekend.
- Fri. 10/7: Factorization by difference of squares. Ch. 3.6
- Wed. 10/5: Pollard's p-1 factorization algorithm. Ch. 3.5
- Mon. 10/3: Primality testing, Miller-Rabin, distribution of primes. Ch. 3.4
- Fri. 9/30: Euler's formula and roots modulo pq, RSA. Ch. 3.1, 3.2, 3.3
- Wed. 9/28: Prime power DLP reduction algorithm, DLP example. Ch. 2.9
- Mon. 9/26: Chinese Remainder Theorem, Pohlig-Hellman Algorithm. Ch. 2.8, 2.9
- Fri. 9/24: Order notation, Baby-step Giant-step algorithm,
Chinese Remainder Theorem. Ch. 2.6, 2.7,2.8 - Wed. 9/22: ElGamal cryptosystem, groups,
order notation. Ch. 2.4, 2.5,2.6. - Mon. 9/19: Asymmetric ciphers, the Discrete Logarithm Problem and Diffie-Hellman key exchange. Ch. 2.1, 2.2, 2.3.
- Fri. 9/16: Order and primitive roots. Symmetric
and asymmetricciphers. Ch. 1.5 (end), 1.6, 1.7. - Wed. 9/14: Prime numbers, unique factorization and
finite fields. Fermat's little theorem,
order and primitive roots. Ch. 1.4, 1.5. - Mon. 9/12: Modular arithmetic, group of units, fast powering algorithm. Ch. 1.3
- Fri. 9/9: GCD, extended Euclidean algorithm. If time, intro. to modular arithmetic. Ch. 1.2
- Wed. 9/7: Introduction and syllabus. Shift and substitution ciphers, GCD. Ch. 1.1, 1.2