CR1 - Crittografia a Chiave Pubblica

A.A. 2007/2008 - II Semestre - Crediti 7,5.

Informazioni Generali

Docenti Valerio Talamanca Francesco Pappalardi
Ricevimento TBA Lunedì 11 - 13
UfficioTBA209
Telefono TBA 06 57338243
E-mail valerio at mat.uniroma3.it pappa at mat.uniroma3.it
TUTORE Alfonso Pesiri
Lezioni:
Lunedì16 - 18(Esercitazioni Aula F)
Martedì9 - 11(Aula G)
Venerdì11 - 13(Aula 100)
Giovedì16 - 18(Aula 009 - TUTORATO)
DESCRIZIONE DEL CORSO

Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami

Avvisi:

  • [05/06/08] Il primo appello avrà luogo il 9 giugno alle ore 10:00
  • [04/06/08] L'esame di fine semestre è spostato a giovedì 5 giugno alle ore 09:00.
  • [15/05/08] Il prossimo tutorato avrà  luogo giovedì 22 Maggio.
  • [15/05/08] L'esercitazione del 19 Maggio non avrà  luogo.
  • [15/05/08] L'esame di fine semestre è fissato per mercoledì 4 giugno alle ore 11:00
  • [03/04/08] L'orario del primo esonero è stato spostato alle 14:00 di Mercoledì 9 Aprile.
  • [17/03/08] La terza sessione di Tutorato si terrà mercoledì 19 marzo alle 16:00 in aula da destinarsi.
  • [10/03/08] Il primo esonero è fissato per Mercoledì 9 Aprile alle ore 11.
  • [25/02/08] Le lezioni iniziano il 25 Febbraio alle 16:00
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami

    Diario delle Lezioni:

    1. Lezioni 1 e 2 [25/02/08] Presentazione del corso, informazioni varie. Espansione binaria, numero delle cifre. La nozione di operazione bit tipo somma. Tempo di calcolo per una funzione (o complessità).
    2. Lezioni 3 e 4 [26/02/08] La nozione di operazione bit. La complessità di somma, sottrazione, prodotto e divisione. La notazione "O grande". Esempi vari.
    3. Lezioni 5 e 6 [29/02/08] Esempi e esercizi sul calcolo delle complessità: Il fattoriale, il prodotto e somma di polinomi, coefficienti binomiali. Moltiplicazione alla Karatsuba e analisi della sua complessità. Cambio di base.
    4. Esercitazioni 7 e 8 [03/03/08] Algoritmo per il calcolo della parte intera della radice quadrata di un numero binario e analisi della sua complessità. Esercizi e esempi vari.
    5. Lezioni 9 e 10 [04/03/08] Richiami sulla nozione di divisibilità, sui numeri primi. Enunciato del Teorema dei numeri primi e del Teorema di Chebichev. Valutazioni p-adiche e proprietà. Massimo comun divisore. Algoritmo di Euclide e sua analisi. L'algoritmo "binario" di Stein per il calcolo del Massimo comun divisore e sua analisi.
    6. Lezioni 11 e 12 [07/03/08] Coefficienti di Bezout. Algoritmo per l'estrazione dei coefficienti di Bezout dai quozienti prodotti dall'algoritmo di Euclide e sua analisi. Esempi. La funzione φ di Eulero e sue proprietà. Moduli RSA. Fattorizzare un modulo RSA è polinomialmente equivalente a conoscerne il valore della funzione di Eulero. Sotto stima "facile" per φ.
    7. Lezioni/Esercitazioni 13 e 14 [10/03/08] Esercizi e Esempi sul calcolo del massimo comun divisore e l'identità di Bezout. L'aritmetica in Z/mZ e sua complessità. Somme, prodotti e inversi. Aritmetica nell'anello dei polinomi Z/mZ[x] e sua complessità. L'algoritmo dei quadrati successivi.
    8. Lezioni 15 e 16 [11/03/08] Equazioni lineari in Z/mZ e complessità del calcolo delle soluzioni, Piccolo Teorema di Fermat, Esempi. Teorema Cinese dei resti e cimplessità per il calcolo delle soluzioni. Piccolo Teorema di Fermat, esempi e applicazioni.
    9. Lezioni 17 e 18 [14/03/08] Il crittosistema RSA. Generalità. Selezione della chiave, cifratura e decifratura. Verifica che è un crittosistema. Esempi e Applicazioni. Possibili attacchi a RSA. Il problema dell'oracolo.
    10. Lezioni/Esercitazioni 19 e 20 [17/03/08] RSA didattico. Esempi e applicazioni. Confronto tra dimensione dello spazio del testo in chiaro e scelta del modulo RSA. Esempo PKCSS1. Come produrre numeri primo "grandi". Algoritmi probabilistici e analisi del loro errore. Esempi.
    11. Esercitazioni 21 e 22 [18/03/08] Esercizi vari sul calcolo delle complessità. Esercizi sulle implementazioni di RSA e RSA didattico.
    12. Lezioni 23 e 24 [28/03/08] Ancora sul problema di produrre numeri primi random. Differenza tra numeri primi successivi. La Congettura di Cramér. La nozione di pseudo primo. Esempi e controesempi. Numeri di Carmichael. Proprietà dei numeri di Carmichael con dimostrazioni. I numeri di Carmichael sono infiniti. Simboli di Legendre e prime proprietà.
    13. Lezioni 25 e 26 [31/03/08] Simboli di Legendre e Simboli di Jacobi. Proprietà fondamentali, Algoritmi per il calcolo e loro analisi. La nozione di psudo primo di Eulero ed esempi.
    14. Lezioni/Esercitazioni 27 e 28 [01/04/08] La nozione di algoritmo probabilistico Montecarlo con probabilità di errore δ. Il test di primalità di Solovay Strassen, la sua analisi e la sua probabilità di errore. Esercizi vari sui numeri di Carmichael, i simboli di Jacobi e gli pseudo primi di Eulero.
    15. Esercitazioni 29 e 30 [04/04/08] Esercizi di preparazione all'esame di metà  semestre sui seguenti argomenti: Analisi degli algoritmi, soluzioni delle congruenze polinomiali attraverso il Teorema Cinese dei resti, Pseudo primi, calcolo della probabilità di errore degli algoritmi Montecarlo. Successione di Miller Rabin.
    16. ESAME DI META' SEMESTRE[09/04/08]
    17. Lezioni 31 e 32 [14/04/08] Ancora sulle successioni di Miller Rabin. Esempi e Esercizi. La nozione di Pseudo Primo forte. L'insieme delle basi forti e la stima per la sua cardinalità.
    18. Lezioni 33 e 34 [15/04/08] Ancora sulle basi forti. Il testi di primalità di Miller Rabin. Esempi
    19. Lezioni 35 e 36 [18/04/08] Numeri di Fibonacci. Proprietà dei numeri di Fibonacci. La nozione di pseudo primo di Fibonacci. Esempi. Certificazioni di primalità. Il Teorema di Lucas. Corollari.
    20. Lezioni 37 e 38 [21/04/08] Teorema di Pocklington, Ancora sui certificati di primalità. Fattorizzazione. Metodo della forza bruta, fattorizzazione alla Fermat. Metodo ρ di Pollard (Inizio)
    21. Lezioni 39 e 40 [22/04/08] Metodo ρ di Pollard (continua), paradosso del compleanno, analisi del metodo di Pollard, Esempi vari.
    22. Lezioni 41 e 42 [25/04/08] Esercizi e fine del metodo ρ di Pollardi. Campi Finiti. Richiami delle proprietà di base. La cardinalità di un campo finito. Esempi
    23. Lezioni 43 e 44 [29/04/08] Campi Finiti. Esempi di Campi finiti. complessità delle operazioni nei campi finiti. Struttura del gruppo moltiplicativo di un campi finito. Esempi e esercizi.
    24. Lezioni 45 e 46 [09/05/08] Campi finiti. Esistenza e unicità dei campi finiti. La formula sbagliata. Esempi. Il gruppo degli automorfismi. Automosfismo di Frobenius. Struttura del reticolo dei sottocampi. Enumerazione dei Polinomi irriducibili. Test di irriducibilità e loro analisi. Esempi
    25. Esercitazioni 47 e 48 [12/05/08] Campi finiti: Dimostrazioni delle formule per l'enumerazione dei polinomi irriducibili. Esercizi vari: fattorizzazioni di polinomi su campi finiti, costruzione di radici primitive su campi finiti. etc.
    26. Esercitazioni 49 e 50 [13/05/08] Campi finiti: Polinomi primitivi. Enumerazione dei polinomi primitivi. Calcoli vari su campi finiti con 125 e 32 elementi.
    27. Lezioni 51 e 52 [16/05/08] Analisi della complessità  dei test di irriducibilità  dei polinomi a coefficienti su un campo finito. Applicazini dei campi finiti in crittografia. Il protocollo dello scambio chiavi di Diffie Hellmann, Il crittosistema ElGamal, Il crittosistema Massey Omura.
    28. Lezioni 53 e 54 [20/05/08] Ancora sui crittosistemi basati sui logaritmi discreti. Algoritmo Pohlig - Hellman. Esempi. Analisi dell'Algoritmo Pohlig - Hellman. Baby Step Giant Step - inizio.
    29. Lezioni 55 e 56 [23/05/08] Baby Step Giant Step Fine. Esempi. Sistemi di firma digitale Definizioni, Esempi. Il sistema DSS.
    30. Lezioni 57 e 58 [26/05/08] Generalità sulle curve ellittiche sui campi finiti. Somma di punti. La struttura di gruppo nell'insieme dei punti razionali. Enunciato del Teorema di Hasse e del Teorema di Struttura per il gruppo dei punti razionali. Esempi e esercizi.
    31. ESAME DI FINE SEMESTRE[05/06/08]
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami

    Tutorato/Esercizi:

    1. Giovedì 6 Marzo
    2. Giovedì 13 Marzo
    3. Mercoledì 19 Marzo
    4. Giovedì 3 Aprile
    5. Giovedì 24 Aprile
    6. Mercoledì 30 Aprile
    7. Giovedì 22 Maggio

    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami

    Esoneri/Esami:

  • Esame di metà semestre 9 Aprile
  • Esame di fine semestre 5 Giugno
    RISULTATI:
    MATRICOLA I II III IV V VI VII VIII IX TOT Primo Esame Media
    604 0 1 0 2 1 1 0 0 4 9 22 15.5
    20786 0 2 3 3 1 2 0 0 2 13 20 16.5
    271174 4 2 2 3 0 3 0 0 2 16 22 19
    245111 0 3 3 4 2 1 0 3 1 17 21 19
    271110 1 1 4 4 2 2 0 0 4 18 33 25.5
    268593 0 1 2 4 2 3 1 2 4 19 29 24
    270585 0 4 2 4 3 2 2 0 4 21 28 24.5
    202020 3 2 2 4 2 2 2 2 4 23 24 23.5
    259980 0 2 4 4 4 4 0 3 4 25 22 23.5
    251520 1 4 4 4 2 0 4 4 4 27 23 25
    258934 0 3 3 4 3 2 4 4 4 27 34 30.5
    274535 4 3 4 4 2 2 1 4 4 28 28 28
    267990 4 3 2 4 4 1 4 2 4 28 31 29.5
    245814 0 3 4 4 2 4 4 4 4 29 27 28
    259248 0 4 4 4 4 4 3 3 4 30 34 32
    260327 4 4 1 4 3 3 4 4 4 31 24 27.5
    260413 1 4 4 4 4 4 4 4 4 33 32 32.5
    260088 4 4 4 4 4 4 4 4 4 36 35 35.5
    280285 4 4 4 4 4 4 4 4 4 36 36 36
  • Appello A 9 Giugno
    RISULTATI:
    MATRICOLA I II III IV V VI VII VIII IX TOT
    246732 4 0 2 0 1 0 3 2 2 14
    604 2 0 2 0 0 3 2 2 2 13
    20786 4 0 4 0 1 0 4 2 2 17
  • Appello B 9 Luglio
  • Appello X 16 Settembre
  • Appello C 13 Febbraio 2009
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami

    Testi consigliati:


  • F. Pappalardi NOTE DI CRITTOGRAFIA A CHIAVE PUBBLICA Fascicolo 1. Prerequisiti di Matematica 2003.
  • D. Stinson. Cryptography. Theory and Practice - Second Edition. February 2002, by CRC Press, Inc.
  • N. Koblitz. A Course in Number Theory and Cryptography, 2nd ed., Springer-Verlag (1994).
  • R. Crandall and C. Pomerance. Prime Numbers. A computational perspective. Springer 2001.
  • Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Tutorato/Esercizi proposti Esoneri/Esami