Combinatorics and cryptography
- Unit Coordinator: Roberto Civino
- ECTS Credits: 6
- Semester: 2
- Year: 1
- Campus: University of L'Aquila
- Language: English
- Aims:
Learning Objectives.
The aim of the course is to provide an introduction to modern public and private key cryptography, with particular attention to:
- algebraic computational problems on which cryptosystems are based,
- modeling and analysis of possible attack scenarios,
- security definitions from the context of provable security,in order to provide an insight into the key ingredients of a complex cryptographic protocol.
These objectives are part of the educational aims of the course of study, as the internal coherence of the master's degree course in Mathematical Engineering was verified at the time of the planning of the program.
Learning Outcomes.
Upon successful completion of the course, the candidate
- masters the basic concepts of arithmetic and theory of groups and rings necessary for cryptographic applications;
- knows the different definitions of security and the relationships between them;
- can describe encryption algorithms and can prove their correctness;
- is able to discuss the security of a cipher and the corresponding cryptanalysis methodologies;
- is able to discuss the computational complexity of cryptanalysis techniques;
- knows how to implement the studied algorithms;
- is able to design computer-aided cryptanalysis techniques against test ciphers. - Content:
MODULAR ARITHMETIC
Division with remainder. Greatest common divisor: algorithms and complexity. Prime numbers. Congruences. Integers modulo n. Modular multiplicative inverse. Phi of Euler.FINITE GROUPS
Group notion and examples. Subgroups. Order of a group and of an element. Lagrange's Theorem. Fermat's little Theorem. Euler's Theorem. Cyclic groups. Primitive elements. Isomorphism between groups. Chinese remainder theorem. Discrete logarithm and isomorphism with Zn.PUBLIC-KEY CRYPTOGRAPHY
Diffie-Hellman key exchange. Computational and decisional Diffie-Hellman problems. Relationship with the discrete logarithm problem. Pohlig-Hellman reduction. Collision methods: Pollard's Rho and baby-step/giant-step. Birthday paradox. Pohlig-Hellman exponentiation cipher. Definition of public-key cryptosystem. Chosen-plaintext attacks and indistinguishability. RSA - textbook version. The integer factorization problem. RSA textbook security and vulnerabilities. Security against chosen-ciphertext attacks. RSA with padding. ElGamal cryptosystem. Relationship with the Diffie-Hellman problem. Digital signature. RSA-FDH and DSA.PRIVATE-KEY CRYPTOGRAPHY
Definition of private-key cryptosystem. One-time-pad. Cryptanalysis of a substitution cipher. SPN and Feistel networks. Elementary notions of finite fields. Elementary notions of differential cryptanalysis. PRESENT. AES. GOST. Hash functions. Collision resistance. Merkle-Damgård construction. Attack scenarios: Security against CPA, CCA, and indistinguishability. Standard modes of operation of a block cipher. Authenticated encryption: Galois counter mode - Pre-requisites:
The course is presented in a self-contained manner and provides, in the initial stages, a review of the elementary notions of algebra on which the entire course system is structured. These contents are essential prerequisites for passing the course. The course will also cover programming topics using the languaga Magma, focused on the implementation of cryptographic schemes and their attacks. It will be assumed that students who enroll in this course have basic programming skills, as instruction on how to code will not be provided.
- Reading list:
Students are advised to rely on lecture notes as the main source of educational material. Lecture note contents are based on the following textbooks, each of which can be considered alone a textbook for this introductory course in cryptography.
- Katz J. and Lindell Y. (2020). Introduction to Modern Cryptography - CRC Press.
- Smart, P. Nigel. (2006). Cryptography made simple - Springer.
- Hoffstein J., Pipher J. and Silverman J.H. (2008). An introduction to mathematical cryptography - Springer.
