CRYPTOGRAPHY
cod. 1005700

Academic year 2023/24
1° year of course - First semester
Professor
Alessandro ZACCAGNINI
Academic discipline
Analisi matematica (MAT/05)
Field
Attività formative affini o integrative
Type of training activity
Related/supplementary
48 hours
of face-to-face activities
6 credits
hub:
course unit
in ITALIAN

Learning objectives


The theory behind cryptography and some applications

Prerequisites


Basic calculus, basic algebra

Course unit content


Overview of the theory of finite groups and finite fields
Fundamental algorithms
Applications to cryptography
Cryptographic protocols.

Full programme


Overview of the theory of finite groups and finite fields
Theorems of Fermat, Euler and Wilson, structure of the ring Z/pZ, p prime.
Gauss's Theorem: existence of primitive roots (generators) in the groups (Z/pZ)*, p prime.
Necessary and sufficient conditions for primality. Fermat, Euler, and strong pseudoprimes.
Sketch of the proof of the Theorem of Agrawal, Kayal, Saxena.
Fundamental algorithms
Euclid's algorithm, Eratosthenes' sieve, primality tests.
Exponential factorization algorithms: trial division, Lehman's method, Pollard's ρ method, Pollard's p − 1 method.
Subexponential factorization algorithms: the quadratic sieve.
Gauss's algorithm for the computation of primitive roots.
Discrete logarithm: the Silver–Pohlig–Hellman algorithm, the Shanks algorithm (“baby steps, giant steps”).
Applications to cryptography
Some remarks on classical cryptography.
Public key cryptography: the Diffie–Hellman, RSA, Massey–Omura, ElGamal, Rabin cryptosystems.
Digital signature.
Cryptographic protocols.

Bibliography


R. CRANDALL & C. POMERANCE, Prime numbers. A computational perspective, Springer, New York, 2001.
G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, quinta edizione, Oxford Science Publications, Oxford, 1979.
N. KOBLITZ, A Course in Number Theory and Cryptography, seconda edizione, Springer, 1994.
A. LANGUASCO & A. ZACCAGNINI, Manuale di crittografia, Ulrico Hoepli Editore, Milano, 2015.

Teaching methods


Traditional lectures

Assessment methods and criteria


Lecture given by the student on a topic agrred upon with the lecturer

Other information

- - -

2030 agenda goals for sustainable development

- - -