- Docente: Davide Aliffi
- Credits: 6
- SSD: MAT/02
- Language: Italian
- Teaching Mode: In-person learning (entirely or partially)
- Campus: Bologna
- Corso: First cycle degree programme (L) in Mathematics (cod. 8010)
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