COMBINATORICS AND CRIPTOGRAPHY

Prerequisites

Basics of Algebra

Contents

Topics of the module include:
Overview of Cryptography and attack scenarios.
Elementary arithmetics: Integers, divisibility, prime numbers, Euclidean division and g.c.d., Bezout’s Identity, Eucledian Algorithm, Extended Eucledian Algorithm, Congruence classes, Chinese remainder theorem, cyclic and abelian
groups, Lagrange theorem, Fermat’s Little Theorem, Euler theorem, the structure of invertible classes mod N, Fields with p elements, Primitive Roots, polynomials, Euclidean division and g.c.d., Congruence classes of polynomials, Finite fields, primitive elements and polynomials.
Introduction to Probability. Probability and Ciphers, Introduction to Shannon Theory, Perfect secrecy, Shannon Theorem, one time pad, Substitution Ciphers.
Symmetric Cryptography, Feistel Networks, Substitution Permutation Networks, Advanced Encryption Standard – Rijandel.
Group generated by a round functions and Imprimitive attack.
Differential cryptanalysis, example of differential cryptanalysis on a small variant of PRESENT.
Public-key Cryptography, Discrete logarithms problem (DLP), Computational Diffie-Hellmann Problem (DHP), between DLP and DHP, Diffie-Helman Key exchange.
RSA Algorithm, Trial Division, Fermat’s test, Miller Rabin Test, AKS primality test, Factoring and factoring-related problems (SQRROOT and RSA Problem), Security of RSA, Coppersmith Theorem, Hastad Attack, Wiener Attack.
Hash function, Digital signatures, RSA signatures, Hashing and signing, DSA.
Error correcting codes, Binary block codes, distance and correction of errors, singleton bound, Hamming bound, Gilbert-Varshamov bound, linear codes, Syndrome decoding, dual codes, Hamming codes, Simplex codes,cyclic codes, Reed-Solomon codes.

Assessment methods

Pre-assessment: There is no formal pre-assessment, but fulfillment of the prescribed pre-requisites is verified by formative assessment.
Formative Assessment: The formative assessment is performed via interaction between teacher and students during lectures and exercises. Students are involved in questioning, in discussion and in proposing strategies to solve exercises, by means of open oral questions to the entire class.
Summative assessment: Oral examination and implementation project of a cryptographic primitive or attack in the MAGMA programming language. An optional mid-term written test will be also provided, which is meant to cover the part of the course concerning the notions of arithmetic and algebra. This test is not mandatory, but if it is not passed, before the oral exam the student will be asked to solve some exercises concerning the mathematical part of the course (arithmetic, modular arithmetic, polynomials, finite fields). Students who pass the intermediate test will be asked, during the oral exam, only the theoretical part of the program.
The oral exam lasts less than an hour and the questions cover all the topics of the program.
The evaluation criteria will be: the level of knowledge of the topics covered during the course, ability to apply them, the scientific language used, the clarity and completeness of the explanations.