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 algorithm. Generating prime numbers: the division method and the sieve of Eratostene. The theorems of Fermat, Euler and Wilson. The structure of integers modulo m. Primitive roots. Pseudoprimes and Carmichael numbers. Some primality tests. The probabilistic Miller-Rabin test. Rabin's theorem. Factorization algorithms: Pollard's method, the p-1 method, Fermat's method, factor bases.

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 and permutation ciphers. The Vernam cipher and information-theoretic security. Shannon's theorem.
Private key systems and block ciphers. The Advanced Encription Standard. Modes of opration of a block. cipher.
Public key systems. RSA, description and security. Some attacks to RSA.  The discrete logarithm problem. Diffie-Hellmann protocol. ElGamal system.
Hash functions and Message Authentication Codes. Semantic security and Random Oracles.
Digital signatures: systems based on RSA. The DSA standard. PKI and certification authorities.
 

Readings/Bibliography

First part:
Course notes.
Baldoni, Ciliberto, Piacentini Cattaneo; Aritmetica, Crittografia e Codici, Springer-Verlag, Milano, 2006
Kobliz; A Course in Number Theory and Cryptography, Springer, New York, 1987.

Second part:
W.Trappe, L.C.Washington, Crittografia con elementi di teoria dei codici, Pearson-Pentice Hall, 2009.

Further readings:
D. Stinson, Criptography, Theory and Practice, Third Edition, CRC Press, 2005.
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. 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