Programma del Corso di Crittografia
Università degli Studi di Parma
Dipartimento di Scienze Matematiche, Fisiche e Informatiche
Corso di Laurea Magistrale in Matematica
Anno Accademico 2023–2024
Corso di Crittografia
Docente: Alessandro Zaccagnini
Durata, Prerequisiti e Orario
-
Il corso vale 6 crediti ed è
collocato nel primo semestre; consiste di 4 ore di lezione
settimanali, per un totale di circa 48 ore.
-
I prerequisiti sono Analisi Matematica 1 ed Algebra.
- Gli studenti frequentanti possono scegliere fra varie
modalità per la prova d'esame: l'esame frontale tradizionale,
un seminario su un argomento crittografico concordato con il docente,
oppure un piccolo progetto di sviluppo di software di rilevanza
crittografica.
Per gli studenti non frequentanti l'esame sarà di tipo tradizionale.
-
Videoregistrazioni: il corso sarà reso interamente disponibile in una
playlist su YouTube; la playlist sarà aggiornata ogni settimana
fino alla fine del corso.
Programma per l'A. A. 2023–2024
-
Richiami alla teoria dei gruppi e dei campi finiti
-
Teoremi di Fermat, Eulero e Wilson, struttura dell'anello
Z/pZ, p primo.
-
Teorema di Gauss: esistenza delle radici primitive (generatori) dei
gruppi (Z/pZ)*, p primo.
-
Condizioni necessarie e sufficienti per la primalità.
Pseudoprimi di Fermat, di Eulero, pseudoprimi forti.
-
Cenni al Teorema di Agrawal, Kayal, Saxena.
-
Algoritmi fondamentali
-
Algoritmo di Euclide, crivello di Eratostene, criteri di
primalità.
-
Algoritmi di fattorizzazione esponenziali: divisione per tentativi,
metodo di Lehman, metodo ρ di Pollard, metodo p − 1
di Pollard.
-
Algoritmi di fattorizzazione subesponenziali: crivello quadratico.
-
Algoritmo di Gauss per la determinazione delle radici primitive.
-
Logaritmo discreto: algoritmo di Silver–Pohlig–Hellman,
algoritmo di Shanks.
-
Applicazioni alla crittografia
-
Cenni alla crittografia classica.
-
Crittografia a chiave pubblica: i crittosistemi Diffie–Hellman, RSA,
Massey–Omura, ElGamal, Rabin.
-
Firma digitale.
-
Protocolli crittografici (cenni).
Testi consigliati
-
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.
Program in English
-
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.
Go to top of page — Torna su
© Alessandro Zaccagnini