Mathematical cryptography
Schedule of lectures
Please, read handouts and recommended chapters of Shoup's book before coming to a lesson.
- 18 Feb - Introduction to cryptography and cryptanalysis. A brief history of cryptography.
Sing: The Code Book. Handout 0 and its printable version.
- 25 Feb - Counting in Z and in Zn.
Shoup: A Computational Introduction, 1.1-3, 2.1-3, 2.5, 4.1-2; Handout 1 and its printable version.
Tutorial 1 with optional homework.
- 4 Mar - Counting in Zn. The complexity of arithmetic operations in Zn.
Shoup: A Computational Introduction, 2.4-7, 3.1-4, 4.1-4; Handout 2 and its printable version.
Tutorial 2 with optional homework.
- 18 Mar - RSA cryptosystem. Attacks on the RSA protocol.
Shoup: A Computational Introduction, 4.7; Boneh: Twenty Years of Attacks on RSA;
Handout 3 and its printable version.
Tutorial 3 with optional homework. Tutorial 4 with optional homework.
- 25 Mar - Abelian groups.
Shoup: A Computational Introduction, 6.1-4; Handout 4 and its printable version.
Tutorial 5 with optional homework.
- 1 Apr - Order of elements, cyclic groups.
Shoup: A Computational Introduction, 6.5; Handout 5 and its printable version.
Tutorial 6 with optional homework.
- 8 Apr - Structure of Zn* groups.
Shoup: A Computational Introduction, 6.5, 7.5; Handout 6 and its printable version.
Tutorial 7 with optional homework.
- 15 Apr - Discrete logarithm, Diffie-Hellman protocol.
Shoup: A Computational Introduction, chapter 11; Handout 7 and its printable version.
Tutorial 8 with optional homework. Tutorial 9 with optional homework.
- 22 Apr - Elliptic curves and the discrete logarithm problem.
Handout 13 and its printable version.
Tutorial 10 with optional homework.
- 29 Apr - Generating random primes and probabilistic algorithms.
Shoup: A Computational Introduction, chapters 5 and 9; Handout 8 and its printable version.
- 29 Apr - Primality testing. Carmichael numbers.
Shoup: A Computational Introduction, chapter 10; Handout 9 and its printable version.
Tutorial 11 with optional homework.
- 6 May - Factorising n by phi(n). (Optional bonus.)
Shoup: A Computational Introduction, chapter 10; Handout 10 and its printable version.
- 13 May - Subexponential-time algorithm for discrete logarithm.
Shoup: A Computational Introduction, chapter 15; Handout 11 and its printable version.
- 20 May - Subexponential-time algorithm for factoring, quadratic sieve.
Shoup: A Computational Introduction, chapter 15; Handout 12 and its printable version.
- Security of cryptosystems in the light of quantum computing.
Literature
- V.Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2008. The book is freely available, we use version 2.
- D.Boneh, Twenty Years of Attacks on the RSA Cryptosystem.
- D.Hankerson, A.J.Menezes, S.Vanstone, Guide to elliptic curve cryptography, Springer, 2004.
- V.Shoup, D.Boneh, A Graduate Course of Applied Cryptography, 2020.
- S.Singh, The Code Book, Random House, 2000.
- J.Hekrdla: Collection of solved exercises (in Czech)
Assessment and Exam
- A test is going to be written in the 9th or 10th week of the semester. To obtain an assessment, one should write it at least 50% correctly. In case of failure, one make-up attempt is possible. The test will contain knowledge of the first half of the semester, see Handouts 1-7.
- In addition, active participation in at least in 70% of tutorials is required to receive an assessment. Attending lectures is strongly recommended too.
- Only students who have received an assessment may take the examination.
- An exam has a written and an oral part, both parts are obligatory.
- The written part takes 120 minutes. Calculators are allowed for addition, multiplication and exponentiation modulo n, other calculations must be done step by step.
- A student will be admitted to the oral exam only if he/she writes the written exam at least 50% correctly. Otherwise, the student will fail the exam.
- The exam contents of the material covered in lectures and tutorials.
- Sample written exam (in English)