Crittografia
e Teoria dei codici- a.a.
2011/2012
Docente: Teo Mora
(email: theomora@disi.unige.it)
Programma
Prima parte (in comune con ICTC)
svolta nel primo semestre - Richiami
di algebra
- Gruppi, monoidi, sottogruppi
- Anelli e corpi
- Omomorfismi, immagini omomorfe, corpo quoziente,
nucleo
- Cosets e gruppo quoziente, gruppi ciclici, ideali,
domini a ideali principali.
- Radici e fattorizzazione dei polinomi
Testo - Algoritmo
Euclideo e Teorema del Resto
Cinese
- Algoritmi euclidei: Algoritmo di divisione;
algoritmo
euclideo; identitˆ di Bezout.
- Teorema del resto cinese: teorema del resto cinese su
Z e k[X]; teorema del resto cinese su un dominio ad ideale
principali.
- Algoritmi di Newton e di Lagrange. Interpolazione di
Lagrange
- Molteplicitˆ delle radici: caratteristica, corpi
finiti, derivate, moltiplicitˆ
- Corpi perfetti e separabilitˆ (cenni)
- Funzioni di Eulero e di Carmichael
Testo Materiale aggiuntivo - RSA
e sua implementazione
- Introduzione a RSA
- Test di primalitˆ (1): teorema di Fermat; esempio di
Lucas, teorema di Lucas, numeri di Carmichael;
- Test di primalitˆ (2): teorema di Eulero, residui
quadratici, simboli di Legendre e di Jacobi e loro calcolo, test di
Solovay--Strassen;
- Test di primalitˆ (3): test di Miller--Rabin; numero
di Jaeschke; test di Davenport;
- Test di primalitˆ (4): primality certificate,teorema
di Pocklington;
- Attacchi contro RSA; bits di RSA
- Algoritmi per l'esponenziazione; signed digit
representation and non-adjacent forms.
- Aritmetica effettiva in Zn, n intero
dispari
- Aritmetica di Montgomery
- Karatsuba multiplication
Testo
- Neal Koblitz A Course in Number Theory and
Cryptography (1987) (ch. IV 2, V 1)
CSBMI:11-1987-16
CSBMI:11-1994-15
- J. H. Davenport,
Primality Testing Revisited,Proc. ISSAC
'92, ACM
Press, 1992, 123--129
pdf
ps
- A. Salomaa, Public-key Cryptography
(1990) (ch.4) CSBMI:68-1990-85
- D. Boneh, Twenty
Years of Attacks on the RSA Cryptosystem,Notices of
the AMS 46 (1999) 203--213
pdf
ps
- Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic
Curves in Cryptography (ch. 2.1, 4.2) CSBMI:14-1999-04
- 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 Montgomery Arithmetics
Materiale aggiuntivo
- Montgomery P.,
Modular
Multiplication Without Trial Division,
Math. Computation, vol. 44, pp. 519--521, 1985.
- Cryptoanalisi
di RSA
- Estazione di radici quadrate.
- Struttura delle radici quadratiche modulo il prodotto di due
primi. Numeri di Blum e di Williams
- Crittografia di Rabin ed equivalenza alla fattorizzazione;
generazione di numeri random e produzione di One Time Pads; cenni alla crittografia di Williams
- Test indiano di primality
- Crivello quadratico e sua complessitˆ. Cenni al number field
sieve
- Cenni sull'algoritmo di Weideman per risolvere equazioni
lineari. Macchina di Bernstein per risolvere equazioni lineari
- Twinkle e Twirl
Testo Materiale aggiuntivo
- M.C.Rabin, Digitalized
signatures and pubic-key functions as intractable as factorization
M.Z.T. Lab. for Computer Science, Tech. Rep. LCS/TR-212, 1979.
pdf
- H.C.Williams,
Modification
of the RSA Public-Key Encryption Procedure,
IEEE Trans. on Inf. Th. 26 (1980), 726-729.
- M. Agrawal, N. Kayal, N. Saxena,
Primes
is in P(Original preprint 6-8-2002)
pdf
ps
- M. Agrawal, N. Kayal, N. Saxena,
Primes is in P, Ann. Math 160(2000),
781--793
pdf
- A. K. Lenstra,H. W. Lenstra, Jr. , M. S. Manasse,
J. M.
Pollard,
The
number field
sieve
Proceedings of the twenty-second annual ACM symposium on Theory of
computing (1990) ACM 564 - 572 pdf
- A.K.Lenstra, H.W. Lenstra, Jr., The development of
the number field
sieve (1993) CSBMI:11-1993-06
- D.H.Wiedemann,
Solving
Sparse Linear Equations over Finite Fields,
IEEE Trans. on Inf. Th. 32 (1986), 54-62.
- E. Kaltofen, B.D.Saunders On
Weidemann
Methoid of Solving Space Linear Systems LNCS 539
(1991) 29--38
pdf
- Kranakis, E. Primality and cryptography
(1986) CSBMI:11-1986-10
- Crittografia
3: Curve ellittiche
- Calcolo del logaritmo discreto su un corpo finito:
algoritmo
di Silver-Pohlig-Hellman
- Calcolo del logaritmo discreto su un corpo finito: algoritmo
di Coppersmith-Davanport
- Funzioni simmetriche e Teorema Fondamentale. Discriminante
- Introduzione alle curve ellittiche. Espressione di
Weierstrass. Determinante. Punti sigolari: nodi e cuspidi
- Accenno al piano proiettivo. Studio delle curve ellittiche
sui i reali. Aritmetica dei punti di una curva ellittica
- Proprietˆ dell'invariante.
- Formula della somma di punti
- Pairing. Algoritmo di Menezes-Vanstone-Okomoto per il calcolo
del logaritmi discreto sul gruppo dei punti di una curva ellittica
Testo
Materiale aggiuntivo
- J. SilvermanThe Arithmetic of Elliptic Curves
(1986)
CSBMI:14-1986-10;14-1992-18
- Ian Blake, Gadiel Seroussi, Nigel Smart, Elliptic
Curves in Cryptography (ch. 3.1--5, 4.1) CSBMI:14-1999-04
- H.
Cohen, G. Frey et al.
Handbook of Elliptic and Hyperelliptic Curve Cryptography
(2006)
Seconda
parte svolta nel
secondo semestre
- Aritmetica
dei Corpi Finiti
- 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. Cenni su 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
Testo
- Teo Mora Solving
Polynomial Equation Systems (1999) (ch.
3,4.5-6,5,7.1-4,8)
- 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
- Introduzione
alla teoria dei codici
- 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 calcolo e suo uso nell'analisi
probabilistica di un codice
Testo
- H.J. van Lint Coding theory L.N.M.201,
Springer (1971)
(ch.1,
2.1--2) CSBMI:94-1971-5
- Berlekamp, E. R. Algebraic coding theory
(1968) (Ch.1.1--3) CSBMI:94-1968-01
- M. Sala (Ed.) Gröbner Bases, Coding, and
Cryptography (2009) (ppg.47--68)
CSBMI:68-2009-07
Materiale aggiuntivo
- Lucidi
sui codici: prima parte
- W.W.
Peterson, E.J. Weldon, Jr. Error-Correcting Codes
(Second Edition) M.I.T. Press (1996)
- F.J. Mac Williams, N.J.A. Sloane, The Theory of
Error-Correcting Codes North-Holland (1997)
- Codici
ciclici
- 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}.
- Rappresentazione ed aritmetica dei corpi finiti
- Struttura delle radici primitivi dell'unita`
- Nilpotenti, idempotenti; struttura
dei quozienti dei domini a ideali principali.
- Calcolo di idempotenti e fattorizzazione dei polinomi
ciclotomici su GF(2)
- Polinomi ciclotomici e loro calcolo
- Aritmetica effettiva in GF(pn)
- Squarefree decomposition; Algoritmo di Berlekamp per la
fattorizzazione in GF(q)[X]
Testo
- Berlekamp, E. R. Algebraic coding theory
(1968) (Ch.1.4, 5.1--6)
CSBMI:94-1968-01
- H.J. van Lint Coding theory L.N.M.201,
Springer (1971) (ch.3.1--3,4.1) CSBMI:94-1971-5
- M. Sala (Ed.) Gröbner Bases, Coding, and
Cryptography (2009) (ppg.47--68) CSBMI:68-2009-07
- Teo Mora
Solving
Polynomial Equation Systems, (1999) (ch. 2.4--7,
7.4--7, 4.7, 17.1)
- Addenda: pdf
- Lucidi
sui codici ciclici: prima parte
- Lucidi
sui codici ciclici: seconda parte
- Lucidi
sui codici ciclici: terzaa parte
- Lucidi
sui circuiti e l'aritmetica effettiva: prima parte
- Lucidi
sui circuiti e l'aritmetica effettiva: seconda parte
- Codici
BCM e Algoritmo
di Berlekamp-Massey.
- Codici BCH.
- Funzioni simmetriche e Teorema di Newton. Traccia; norma;
discriminante
- Algoritmo di Petersen-Gorenstein-Zierler per la decodifica
dei codici BCH.
- Uso della serie delle sindrome per la loro decodifica: la key
equation.
- Linear feadback shift register. Algoritmo di Berlekamp-Massey.
- Algoritmo euclideo e funzioni continue: Algoritmo giapponese
Testo
Materiale aggiuntivo
- W. L. Eastman,
Euclidean
Decodes for BCH Codes,
RADC-TR-88-44 (1988), Rome Air Development Center.
pdf
- W. W.
Peterson,
Encoding and error-correction procedures for the Bose-Chaudhuri codes,
IRE Trans. on Inf. Th. 6 (1960), 459-470.
- G. D. Forney,
On
decoding BCH codes, IEEE Trans. on
Inf. Th. 11 (1965), 549-557.
- Massey, J. L.,
Shift-register synthesis and BCH decoding,
IEEE Trans. Information Theory IT-15 (1) (1969): 122--127
pdf