PRESENTAZIONE

Le lezioni si tengono in lingua italiana.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Introdurre alle principali tecniche algebriche di base per le applicazioni informatiche in crittografia e teoria dei codici, con cenni sulla teoria classica dei codici e sulla crittografia a chiave pubblica.

MODALITA' DIDATTICHE

Tradizionale

PROGRAMMA/CONTENUTO

1. Crittografia: curve ellittiche [3cpu]
   • Introduzione alle curve ellittiche. Espressione di Weierstrass.
   • Determinante. Punti singolari: nodi e cuspidi.
   • Studio delle curve ellittiche sui reali.
   • Accenno al piano proiettivo. Cubiche proiettivie. Flessi. Cenni al Teorema di Bezout.
   • Parametrizzazione delle cubiche singolari.
   • Aritmetica dei punti non-singolari delle cubiche.
   • I punti di Y2+XY=X3-X-1 in GF(5).
   • Cenni sulla dimostrazione dell'associatività.
   • Proprietà dell'invariante.
   • Formula della somma di punti.
   • Invariante ed formule dell'aritmetica in caratteristica 2 e 3.
   • Algoritmi per i prodotti di un punto; signed digit representation and non-adjacent forms.
2. Aritmetica dei Corpi Finiti [1.5cpu]
   • Ideali principali, primi, massimali. Principal ideal domain, Unique factorization domain. Norma di Dedekind-Hesse.
   • Algoritmi euclidei: Algoritmo di divisione; algoritmo euclideo; identità di Bezout. Cenni alle frazioni continue.
   • Cenni sui corpi finiti. Caratteristica.Derivata.
   • Funzioni simmetriche e Teorema Fondamentale.Teorema di Newton.
   • Traccia e Norma. Discriminante. Risultante.
   • Radici di polinomi: risoluzione delle radici cubiche; il numero immaginario.
   • Cenni sul Teorema Fondamentale dell'Algebra e sul Teorema di Abel Ruffini.
   • Teoria di Kronecker: estensioni finite di corpi; numeri algebrici e trascendenti.
   • Splitting fields. Separabilità. Corpi perfetti.
   • Struttura dei corpi finiti: corpi di Galois, radici dei polinomi sui corpi finiti.
   • Radici dell'unità e radici primitive; tecniche per il loro calcolo.
   • Rappresentazione ed aritmetica dei corpi finiti.
   • Struttura delle radici primitivi dell'unità.
   • Polinomi ciclotomici e loro calcolo.
   • Teorema del resto cinese su un dominio ad ideali principali.
   • Algoritmi di Newton e di Lagrange. Interpolazione di Lagrange.
   • Nilpotenti, idempotenti; struttura dei quozienti dei domini a ideali principali.
   • Calcolo di idempotenti e fattorizzazione dei polinomi ciclotomici su GF(2).
   • Algoritmo di fattorizzazione di Berlekamp.
3. Introduzione alla teoria dei codici [1.5cpu]
   • Errore, rumore, tasso di informazione, probabilità; repetition code e parity check.
   • Distanza di Hamming. Maximum Likelihood Decoding. Teorema fondamentale di Shannon.
   • Codici linearli. Sindromi. Decodifica dei codici lineari. Step-by-step decoding.
   • Codici di Hammimg e codici perfetti.
   • Weight enumerator. Suo uso nell'analisi probabilistica di un codice.
   • Singleton Bound
   • Codici ciclici.
   • Usi delle radici per la decodifica.
   • Esempi dei codici di Hamming e del codice di Hamming esteso. Esempio di codici {1,3} e {1,-1}.
   • Codici BCH. BCH bound.
   • Algoritmo di Petersen-Gorenstein-Zierler per la decodifica dei codici BCH.
   • Uso della serie delle sindrome per la loro decodifica: la key equation.
4. Protocolli [1cpu] Non mutuato da Informatica
   • Digital Signature.
   • Key Exchange.
   • Authenticaltion.
   • Multiple-Key Public-Key Cryptography.
   • Secret splitting. Secret sharing. Timestemping Srvice
   • Subliminal Channel. Undeniable Digital Signature
   • Bit commtment. Fair coin flip. Mental Pocker
   • Fair cryptpsystem. All-or-nothing Disclosure of Shares. Zero-knowledge proofs. Blind Signature
   • Oblivious Transfer
   • Secure Election

TESTI/BIBLIOGRAFIA

1. Crittografia: curve ellittiche [3cpu]
   • A.W.Knapp,Elliptic curves Princeton University Press, 1992 CSBMI:11-1992-10
   • Informal notes on Elliptic Curves
   • Neal Koblitz, A Course in Number Theory and Cryptography (1987) (ppg. 98--102)) CSBMI:11-1987-16 CSBMI:11-1994-15
   • J. Tate, Algebraic Formulas in Arbitrary Characteristic in: S. Lang Elliptic Functions, Addislon-Wesley (1973) ppg. 299--306
   • Grimoire of Algebraic Lore
   • Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic Curves in Cryptography (ch.IV.2) CSBMI:14-1999-04
   • J. Silverman The Arithmetic of Elliptic Curves(1986) CSBMI:14-1986-10;14-1992-18
   • Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic Curves in Cryptography (ch. III.1--3, IV.1) CSBMI:14-1999-04
   • L.C.Washington Elliptic curves : number theory and cryptography, II Ed. (2008) CSBMI:11-2008-04
2. Aritmetica dei Corpi Finiti [1.5cpu]
   • Teo Mora Solving Polynomial Equation Systems (1999) (ch.1.1-4,2,3,4.1-6,5,6.2-6,7.1-2,7.4-7)
   • Addenda: pdf
   • Neal Koblitz A Course in Number Theory and Cryptography (1987) (ch. II 1) CSBMI:11-1987-16 CSBMI:11-1994-15
   • Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic Curves in Cryptography (ch. 2.2) CSBMI:14-1999-04
   • Notes on Montgomery Arithmetics
   • A. Menezes, P. van Oorsschot, S. Vanstone Handbook of Applied Cryptography (1997) (Ch.14.3.2;14.6.1(v)) CSBMI:69-1997-062
   • Notes on the Euclidean Algorithm
3. Introduzione alla teoria dei codici [1.5cpu]
   • H.J. van Lint Coding theory L.N.M.201, Springer (1971) (ch.1, 2.1--2,3.1--3,4.1) CSBMI:94-1971-5
   • Berlekamp, E. R. Algebraic coding theory (1968) (Ch.1, 5,7.1-4) CSBMI:94-1968-01
   • M. Sala (Ed.) Gröbner Bases, Coding, and Cryptography (2009) (ppg.47--68;69--91) CSBMI:68-2009-07
   • Lucidi sui codici: prima parte
   • Lucidi sui codici: seconda parte
   • Lucidi sui codici ciclici: prima parte
   • Lucidi sui codici ciclici: seconda parte
   • Lucidi sui codici ciclici: terza parte
4. Protocolli [1cpu] Non mutuato da Informatica
   • B.Schnrier Applied cryptography : protocols, algorithms, and source code in C (1994) CSBMI:68-1994-001

DOCENTI E COMMISSIONI

Commissione d'esame

FERDINANDO MORA (Presidente)

CHIARA MARTINENGO

MARIA EVELINA ROSSI

LEZIONI

INIZIO LEZIONI

In accordo con il calendario accademico approvato dal Consiglio di Corsi di Studi.

Orari delle lezioni

INTRODUCTION TO CRYPTOGRAPHY AND CODE THEORY

ESAMI

MODALITA' D'ESAME

Esame orale