46686 - Algorithms of the Theory of Numbers and Cryptography

Learning outcomes

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

Course contents

Time estimates for efficiency of algorythms: The "big-O" notation. Euclide's algorythm. Generating prime numbers: the division method and the sieve of Eratostene. The theorems by Fermat, Euler and Wilson. The structure of integers modulo m. Primitive roots. Pseudoprimes and Carmichael numbers. Some primality tests. The probabilistic Miller-Rabin test. The quadratic reciprocity law (fron Bressoud's test). Factorization algorythms: Pollard's method, the p-1 method, Fermat's method, the quadratic sieve.
Introduction to Cryptography. Symmetric and asymmetric cryptosystems. Attacks. Alphabets and words. Block ciphers. Affine and linear systems. Historical examples: Vigenere, Hill, permutation ciphers. Cryptoanalysis of affine ciphers.
Perfect secrecy and the Shannon Theorem. Vernam cipher.
Private key systems: AES.
Public key systems. RSA, description and security. The Rabin system. The discrete logarithm problem and the index calculus. Diffie-hellmann protocol. ElGmal system.
Hash functions and Message Authentication Codes.
Digital signatures: systems based on RSA and ElGamal.

Readings/Bibliography

Baldoni, Ciliberto, Piacentini Cattaneo; Aritmetica, Crittografia e Codici, Springer-Verlag, Milano, 2006
W.Trappe, L.C.Washington, Crittografia con elementi di teoria dei codici, Pearson-Pentice Hall, 2009.
W.Stallings, Crittografia e sicurezza delle reti, Apogeo, 2006.
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.

Assessment methods

Oral exam.

Office hours

See the website of Davide Aliffi