Combinatorics and cryptography
- Unit Coordinator: Riccardo Aragona
- Programme: Double Degrees
- ECTS Credits: 6
- Semester: 2
- Year: 1
- Campus: University of L'Aquila
- Language: English
- Aims:
The course aims to provide the arithmetical and algebraic background and the basic techniques for symmetric cryptography, public-key cryptography and error correction coding. At the end of the course the student should be able to understand the fundamental concepts of modular arithmetic and Snite Selds and to be able to apply them to the study of basic cryptographic techniques and basic error correcting codes described during the course.
On successful completion of this course, the student should
1) have knowledge of the basic techniques of cryptography and error correction codes introduced;
2) understand the fundamental concepts of arithmetic and algebra and their interactions and be aware of their applications in cryptography and coding theory;
3) have knowledge of how to apply the notions of arithmetic and algebra to the study of cryptographic techniques and error correction codes;
4) understand and analyze the mathematical and application problems underlying the cryptographic schemes studied;
5) demonstrate skill in reasoning and arithmetic calculation and ability to understand the proofs of the theoretical and cryptographic results studied;
6) demonstrate ability to read and understand other scientiSc texts on related subjects. - Content:
- 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 Selds, 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 Diue-Hellmann Problem (DHP), between DLP and DHP, Diue-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.
- Pre-requisites:
Basics of Algebra
- Reading list:
1) Trappe and Washington, "Introduction to Cryptography with Coding Theory", second edition, Pearson Pretince Hall, 2006;
2) Smart, "Cryptography made simple", Information Security and Cryptography, Springer, 2016;
3) Heys, "A Tutorial on Linear and Differential Cryptanalysis"
