- Docente: Davide Aliffi
- Credits: 6
- SSD: MAT/02
- Language: Italian
- Teaching Mode: Traditional lectures
- 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 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