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