Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2008-2009
T e o r i a E l e m e nt are d e i
N u m e r i
C r i t t o g r a f i a (parte 1)
Docente:
Laura Geatti
CORSO CHIUSO
ORARIO
Laurea Specialistica, anno 1, crediti 5.
Primo semestre (secondo emisemestre): 24 novembre 2008 - 31 gennaio 2009.
Questo e' un corso da 5 crediti che puo' essere seguito da solo oppure in abbinamento ai primi 5 crediti del corso "Sicurezza dei sistemi informatici", tenuto nel secondo semestre dal Prof. G. Italiano
PROGRAMMA (approssimativo)
Primalita' e fattorizzazione: complessita' a confronto, criptosistema RSA, test di primalita' di Miller-Rabin;
Algoritmi per fattorizzare numeri: Metodo ρ di Pollard, metodo p–1, metodo delle curve ellittiche, crivello
quadratico;
Logaritmo discreto: Baby-step-Giant-Step, calcolo dell'indice.
Programma settimanale
Prerequisiti: Corso Elementi di Algebra e Logica (Laurea Triennale in Ing. Informatica) EAL2008
Progetti (gruppi di due persone al massimo)
(più stelle = più difficile)
- Metodo delle curve ellittiche (prima fase, seconda fase).
- Logaritmo discreto (calcolo dell'indice).
- Crivello quadratico.
ESAMI
L'esame consiste in un compito scritto e in un progetto.
Per presentare il progetto è necessario aver fatto un compito
scritto sufficiente (con voto almeno 18). Il voto del compito vale fino al 30 settembre 2009.
Per gli studenti di Crittografia (parte 1 e parte 2):
Gli esami sulla parte 1 (corso di 'Teoria Elementare dei Numeri") e sulla parte 2 ( i primi 5 crediti del corso "Sicurezza dei sistemi informatici" ) possono essere sostenuti in modo indipendente. Anche chi non ha superato la parte 1 puo' accedere alla parte 2.
Il voto finale e' dato dalla media dei voti ottenuti nella parte 1 e nella parte 2.
Un voto sufficiente nella parte 1 o nella parte 2 viene conservato fino al 30 settembre 2009: se l'esame completo non viene superato entro tale data, il voto decade.
Per partecipare agli scritti, è necessario iscriversi mediante il MODULO predisposto
di volta in volta su questo sito.
Portare un documento di riconoscimento.
Non sono consentiti libri o appunti.
Non è consentito uscire durante il compito.
- Appello 1: Soluzioni pdf
- Appello 2: Soluzioni pdf
- Appello 3: Soluzioni pdf
ESERCIZI
- Esercizi1 (complessita') pdf Soluzioni pdf
- Esercizi2 (numeri primi, numeri B-smooth) pdf Soluzioni pdf
- Esercizi3 (gruppi, anelli, campi) pdf (vedi anche pdf e soluzioni pdf )
- Esercizi4 (esercizi con PARI/GP, in aggiornamento...) pdf
- Esercizi5 (curve ellittiche) pdf
Soluzioni pdf
- Esercizi6 (logaritmo discreto in Z*p) pdf
Soluzioni pdf
MATERIALE
Software
Testi
Articoli di carattere espositorio, conferenze
- Ronald van Luijk: Number theory in cryptography
Presentazione, Universidad de los Andes, Bogota, settembre 2006.
- Joe Malkevitch: Mathematics and internet security, Feature column of Am. Math. Soc., April 2006 link
- R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica,
Didattica delle Scienze 137 (1988), 48–54.
(pdf)
- L. Adleman :
conferenza all'ACM per il premio Turing 2002.
-
Victor Miller : Elliptic curve cryptography. Presentazione,
24 maggio 2007.
Note
- nota1 Aritmetica sui numeri interi.
- nota2 Gruppi, anelli, campi e applicazioni.
- Nota sulla funzione φ di Eulero
(versione aggiornata).
- Nota
sulle radici primitive modulo p (versione aggiornata).
- Nota
sui gruppi abeliani finiti.
- Espansioni decimali di 1/n
(1 pagina).
- Nota sulla sommatoria Σ 1/p
- Nota sull'algoritmo di Shanks-Tonelli
- Nota sulle radici quadrate modulo p e modulo pk
Materiale per argomenti
- Fattorizzazione
- Pollard ρ
- Pollard ρ in
Wikipedia.
-
Pollard ρ web pages.
- Nota sull'algoritmo Pollard ρ.
- J. Pollard and R. Brent:
Factorization of the eighth Fermat number, Math. Comp. 36
(1980). (pdf, 4 p.)
- BirthdayGrapher (solo per Mac) link
- John Pollard's
home page.
- Metodo delle curve ellittiche
- Curve Ellittiche in
Wikipedia
- Corso di Curve Ellittiche di Jim Milne.
- Metodo delle curve ellittiche in
Wikipedia.
- Elliptic curve method web pages.
- Nota sul metodo delle curve ellittiche.
- Elliptic Curve Tutorial di certicom link
- Ecmnet.
- R. Brent:
Factorization of the tenth Fermat number, Math. Comp. 68
(1999) 429–451. (pdf)
- H. Lenstra:
Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf (l'introduzione e' chiara e accessibile)
- P. Zimmerman:
Miglioramenti del metodo delle curve ellittiche. (April 2003)pdf
- Foto di Hendrik Lenstra.
- Foto di Peter Montgomery.
- Il crivello quadratico
- Il crivello quadratico in
Wikipedia.
-
Esempio di fattorizzazione usando il crivello quadratico txt
- Un altro esempio pdf
- La fattorizzazione di RSA129 (1994)
txt.
- Carl Pomerance, Smooth numbers and the quadratic sieve, pdf.
- Carl Pomerance, A tale of two sieves, pdf (La favola dei due crivelli).
- Radici quadrate modulo p. Algoritmo di Tonelli
txt.
- L'algoritmo di Shanks-Tonelli in Wikipedia.
- Il Lemma di Hensel in Wikipedia.
- Da evitare: l'articolo di Landquist.
- Foto di Carl Pomerance
- Logaritmo discreto
- Il logaritmo discreto in Wikipedia.
- Discrete logarithm web pages.
- Baby-step-Giant-step method in Wikipedia.
- Diffie-Hellman-Merkle key exchange in Wikipedia.
- El Gamal
encryption in Wikipedia.
- J. Pollard:
Monte Carlo methods for index computation (mod p), Math. Comp. 32
(1978). (Canguri, pdf, 7 p.).
- Chris Studholme, The discrete log problem, june 2002,
pdf
- Esempio di calcolo di un logaritmo discreto
(usando il metodo del calcolo dell'indice)txt.
- Il logaritmo discreto sulle curve ellittiche
CerticomTutorial
- Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
- Foto di Dan Shanks jpg
- Foto di Taher ElGamal jpg
- Foto di Ralph Merkle, Martin Hellman, Whit Diffie jpg
NUMEROLOGIA & VARIE
Il corso di Teoria Elementare dei Numeri
Altro
- L'associazione BEST
per la promozione della mobilità degli studenti di Ingegneria
in Europa.
