46686 - Algorithms of the Theory of Numbers and Cryptography

Course Unit Page

  • Teacher Davide Aliffi

  • Credits 6

  • SSD MAT/02

  • Teaching Mode Traditional lectures

  • Language Italian

  • Course Timetable from Feb 20, 2019 to May 31, 2019

Academic Year 2018/2019

Learning outcomes

Basic knowledge about primality tests and factorization algorythms. Basic knowledge about public and private key cryptosystems.

Course contents

Introduction to Cryptography. Private-key and public-key systems. Historical systems: Caesar cipher and substitution cipher.  Notion of provable security.

Shannon theory. Shannon secrecy and perfect secrecy, their equivalence. One Time Pad. Shannon's theorem.

Computational hardness. Efficient computations and efficient adversaries. Computational number theory. Factoring-based and discrete-logarithm-based collections of one-way functions. RSA collection. One-way permutations. Trapdoor permutations. The Rabin collection. Introduction to Elliptic Curves and the related Discrete Logarithm Problem.

Computational indistinguishability. Pseudo-randomness. Pseudo-random generators. Hard-core bits. Secure symmetric encryption. Pseudo-random functions. AES: description and mathematical structure.

Public key encryption. The ElGamal scheme. The RSA scheme.

Message authentication. MAC. Digital signature schemes. Collision-resistant hash functions. RSA signature. The DSA and ECDSA standards.


Raphael Pass, Abhi Shelat: A Course in Cryptography. Publicy available on the Internet.

Further readings:

Katz, Lindell Introduction to Modern Cryptography, Chapman & Hall/CRC, 2008.
D. Stinson, Criptography, Theory and Practice, Third Edition, CRC Press, 2005.
A.Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997 Publicy available on the Internet.

Teaching methods

Class lectures. The course is 6 cfu and 48 lesson hours, and takes place in the second (Spring) semester. At the end there will be (usually) 4 lab hours using the Matlab symbolic computation system.

Assessment methods

Oral exam. Programs developed during the laboratory hours can be brought to the exam, and they will be discussed with the students.

Teaching tools

Matlab symbolic computing system.

Office hours

See the website of Davide Aliffi