Subject: ALGORITMI DI CRITTOGRAFIA (A.A. 2020/2021)
Unit Algoritmi di crittografia
Related or Additional Studies (lesson)
Students will acquire in-depth knowledge about asymmetric encryption algorithms, secret information sharing and digital signature, as well as on the fundamental mathematical results that make these possible. They'll also develop some abilities to practice with cryptographic tools (such as PGP and OPENS-SSL) for personal use (email, file-protection).
Basic knowledge in the fields of the design and analysis of algorthms and programming (Python language will be used in class), basic knowledge of algebra. The requirements are automatically satisfied by students with a three-year degree in Computer Science / Computer Engineering or Mathematics.
Part I. Basic concepts and algorithms
1. Computational and complexity models for numerical problems
2. Probabilistic algorithms
2.1. Randomness as a computing resource
2.2. Monte Carlo and Las Vegas randomized algorithms, examples
3. Cryptographic hash functions
3.1. General information on hash functions
3.2. Requirements for a cryptographic hash function
3.3. Finding collisions: the birthday paradox and the rho method
3.4. Examples in Python and hints on command-line use
4. Modular arithmetic
4.1. Definitions and additive group Zn
4.2. Multiplicative inverse: Euclid's and extended Euclid's algorithms
4.3. The multiplicative group Zp *, p prime number
4.4. Chinese remainder theorem
5. Algorithms for some number theory problems
5.1. Density of prime numbers
5.2. Factorization of integers, classical algorithms and Pollard's ρ method
5.3. Modular exponentiation
5.4. Fermat's little theorem, pseudo-prime numbers, Carmichael numbers
5.5. Probabilistic methods for primality
5.6. Quadratic residues and the Soloway-Strassen algorithm
5.7. Rabin-Miller algorithm
5.8. Derandomization (using the extended Riemann hypothesis)
5.9. Outline of the AKS method
5.10. Algorithms for calculating the discrete logarithm
6. Generalities on elliptic curves
6.1. Elliptic curves over reals, Weierstrass form
6.2. Definition of an additive group on the points of the curve
6.3. Curves on finite fields
6.4. The problem of calculating the number of points, Hasse estimates and (hints to) Schoof's algorithm
Part II. Asymmetric encryption algorithms and protocols
7. The key exchange problem
7.1. Diffie and Hellman protocol over Zp*
7.2. Safe primes
7.3. Diffie and Hellman protocol over elliptic curves
7.4. Attack based on the "weak curve"
7.5. The choice of "safe" curves
8. RSA protocol
8.1. Key generation
8.2. Usage and proof of correctness
8.3. Attacks on the so-called "textbook RSA"
8.4. Real implementations
8.5. Digital signature
8.6. Certificates and certification authorities
9. Other asymmetric protocols
9.1. El Gamal encryption and digital signature
9.2. DSA algorithm for digital signature
9.3. Rabin's crypto-system
10. The PGP system, Pretty Good Privacy
10.1. The web-of-thrust approach
10.2. The GPG suite and keyring management
10.3. Examples of use
11. Distributed consensus and blockchain technology
Lectures and exercises in the computer lab
Knowledge and understanding
At the end of the course the student will have acquired knowledge about the main asymmetric cryptographic techniques and on a significant sample of algorithms used in various application scenarios.
Applying knowledge and understanding
The course has a significant practical component whose aim is both the development of prototypical algorhtms and the analysis of existing software. This activity aims to make the student develop the correct perception of the difficulty of translating the (good) cryptographic ideas studied in truly secure protocols. This awareness is the first but fundamental competence that characterizes a professional in this delicate field of Computer Science.
Autonomy of judgment
Although the field of cryptography is vast and very delicate, due to the possible consequences of wrong choices, the student will have the main skills that will enable him/her to make an informed choice of cryptographic tools to be used in various application contexts.
This course contributes to the general development of communication skills through the discussion, mainly during the oral examination but also during the laboratory activities, of the motivations that would lead the student to adopt certain solutions in possible application scenarios.
As for the communication skills, with regard to the cryptographic field, it is essential that the student be aware of the need to be constantly up to date both in terms of available solution techniques and in that of possible vulnerabilities that emerges from crypto-analytic investigations.
Materiale fornito dal docente (notes given by the teacher)
(Per consultazione) J.P. Aumasson. Serious Cryptography. No Starch Press, San Francisco 2018