You are here: Home » Study Plan » Subject

Sciences

Subject: ALGORITMI DI CRITTOGRAFIA (A.A. 2020/2021)

master degree course in COMPUTER SCIENCE

Course year 1
CFU 6
Teaching units Unit Algoritmi di crittografia
Related or Additional Studies (lesson)
  • TAF: Supplementary compulsory subjects SSD: INF/01 CFU: 6
Teachers: Mauro LEONCINI
Exam type oral
Evaluation final vote
Teaching language Italiano
Contents download pdf download

Teachers

Mauro LEONCINI

Overview

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).

Admission requirements

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.

Course contents

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

Teaching methods

Lectures and exercises in the computer lab

Assessment methods

Oral exam.

Learning outcomes

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.

Communication skills
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.

Learning ability
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.

Readings

Materiale fornito dal docente (notes given by the teacher)
(Per consultazione) J.P. Aumasson. Serious Cryptography. No Starch Press, San Francisco 2018