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

Fattorizzato RSA-768.
Erasmus 2010-2011 come fare: doc

ORARIO

Laurea Specialistica, anno 1, crediti 5.
Primo semestre (secondo emisemestre): 30 novembre 2009 - 6 febbraio 2010.
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
 

	LUNEDI	MARTEDI	MERCOLEDI	GIOVEDI	VENERDI
9,30 - 11,15				Lezione Aula 17 Ed.Ind.
14 - 16	Lezione Aula 8 Ed.Did.		Lezione Aula 8 Ed.Did.

Ricevimento: il lunedi' dopo la lezione in aula, durante il corso.
Per e-mail oppure su appuntamento, dopo la fine del corso.

PROGRAMMA

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 dettagliato     Diario delle lezioni

Testo di riferimento principale: R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.

Prerequisiti: Corso Elementi di Algebra e Logica (Laurea Triennale in Ing. Informatica) EAL2008

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 2010.

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 2010: 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: martedi' 2 marzo 2010, ore 10-12, Aula T5, T6
• Appello 3: luglio 2010
• Appello 4: settembre 2010
• Appello 5: settembre 2010

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.

ESERCIZI

Esercizi vari

• Esercizi1-2009 (argomenti settimane 1,2,3) pdf
• Esercizi2-2009 (argomenti settimane 4,5,6) pdf
• Esercizi3-2009 (argomenti settimana 8 & mix finale) pdf
• MT1pdf      MT2pdf     MIXpdf

Esercizi svolti

• 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
• GMP software for long integer arithmetic.
• PARI/GP computer algebra system for doing fast computations in number theory. (version 2.2.11-α) or (version 2.03.01-β for Windows)
• PARI-DOC User's Guide to PARI/GP   GPTutorial1    GPTutorial2
• Alpertron Factorizaciòn usando curvas elípticas online
• Tuts4you msieve
Testi
• R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
• L. Washington: Elliptic Curves: Number Theory and and Cryptography, , Chapman and Hall /CRC 2003.
• A.K. Lenstra : Integer factoring, Designs, Codes and Cryptography, 19 (2000) 101-128.
• Dan Bernstein's Integer factorization. Lecture Notes AWS 2006 pdf (57 pagine) & Talk 1, Talk 2.
• A. Zaccagnini e A. Languasco: Introduzione alla crittografia, Hoepli 2004.
• D. Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.
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.
• Espansioni decimali di 1/n.
• Nota sulle radici primitive modulo p.
• Nota sui gruppi abeliani finiti.
• Nota sull'algoritmo Pollard &rho.
• Nota sul metodo p-1 di Pollard.
• Nota sul metodo delle curve ellittiche.
• Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
• Nota sulla sommatoria Σ 1/p
• Nota sull'algoritmo di Shanks-Tonelli.
• Nota sulle radici quadrate modulo p e modulo p^k.

Materiale per argomenti

• Primalità
  • Stime sulla distribuzione dei numeri primi link
  • The Prime pages.
  • Il test di primalita' di Miller– Rabin su Wikipedia.
  • Il test di primalita' di Agrawal-Kayal-Saxena in Wikipedia.
  • R. Schoof, Four primality testing algorithms, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, 101–126. (pdf)
    (Il test di Miller-Rabin si trova alle pp. 2–4).
  • Foto Agrawal, Kayal, Saxena (Palo Alto, primavera 2004)
• Fattorizzazione
  • Pollard ρ
    • Pollard ρ in Wikipedia.
    • Pollard ρ web pages.
    • 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 “p – 1 ”
    • p – 1 method in Wikipedia.
    • p – 1 method web pages.
  • Metodo delle curve ellittiche
    • Curve Ellittiche in Wikipedia
    • Metodo delle curve ellittiche in Wikipedia.
    • Elliptic curve method web pages.
    • Elliptic Curve Tutorial di certicom link
    • Ecmnet.
    • B. Poonen: Elliptic curves, Algorithmic Number Theory, MSRI Publications, 2008 pdf
    • 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 Spiegazione pdf
    • 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
  • Foto di Dan Shanks jpg
  • Foto di Taher ElGamal jpg
  • Foto di Ralph Merkle, Martin Hellman, Whit Diffie jpg

  NUMEROLOGIA & VARIE

  • News
    • 7 gennaio 2010: Fattorizzato RSA-768. Vedi annuncio e articolo
    • 29 settembre 2008: Scoperto un numero primo con circa 13.000.000 di cifre pdf.
    • 31 agosto 2007: Il numero N = (2⁴²⁷³⁷+1)/3 è primo.
    • 22 maggio 2007: È stato Fattorizzato il 1039-esimo numero di Mersenne 2¹⁰³⁹-1.
    • 26 settembre 2006: M₄₄ e' primo.
    • 2 novembre 2005: E` stato fattorizzato RSA640. Comunicato stampa RSA.
    • primo records
    • Records di primalita'
    • Records di fattorizzazione.
    • GIMPS
  • Numeri di Mersenne
    • Numeri di Mersenne
    • Numeri perfetti.
  • RSA
    • RSA
    • Fotos Rivest, Shamir, Adleman
  • Sito Ufficiale certicom (ECC elliptic curve criptography)
  • National Security Agency: The case for elliptic curve criptography link1 link2
  • Government Computer News: giugno 2007

  Il corso di Teoria Elementare dei Numeri

  • 2005-2006
  • 2006-2007
  • 2007-2008
  • 2008-2009
  • Criptography - University of California - Berkeley 2008-2009
  
  
  
  
  

  Altro

  • L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria in Europa.