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 Z_n.
  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 Z_n. The complexity of arithmetic operations in Z_n.
  Shoup: A Computational Introduction, 2.4-7, 3.1-4, 4.1-4; Handout 2 and its printable version.
  Tutorial 2 with optional homework.
• 11 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.
• 18 Mar - Abelian groups.
  Shoup: A Computational Introduction, 6.1-4; Handout 4 and its printable version.
  
• 25 Mar - Order of elements, cyclic groups.
  Shoup: A Computational Introduction, 6.5; Handout 5 and its printable version.
  
• 1 Apr - Structure of Z_n* groups.
  Shoup: A Computational Introduction, 6.5, 7.5; Handout 6 and its printable version.
  
• 8 Apr - Discrete logarithm, Diffie-Hellman protocol.
  Shoup: A Computational Introduction, chapter 11; Handout 7 and its printable version.
  
• 15 Apr - Elliptic curves and the discrete logarithm problem.
  Handout 13 and its printable version.
  
• 22 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.
  
• 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)

 

---