CR410 - Crittografia I

A.A. 2012/2013 - II Semestre - Crediti 7



Informazioni Generali

Docenti Francesco Pappalardi
RicevimentoMercoledý 11 - 13
Ufficio 209
Telefono 06 57338243
E-mail pappa at mat.uniroma3.it
Lezioni:
Martedý 16 - 18(Aula F)
Mercoledý16 - 18(Aula G)
Mercoledý16 - 18(Aula F)



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

Avvisi:

  • [10/01/2014] Lo scritto dell'appello C Ŕ stato spostato a Lunedý 3 Febbraio 2014 alle ore 11:00.

  • [15/09/13] Le prove orali e la verbalizzazione dell'appello X si svolgera alle ore 11 il 16 Settembre nella stanza 209. Le prove orali per gli studenti che hanno superato le prove in itinere si terranno contestualmente allo svolgimento dello scritto dell'Appello A.
  • [02/05/13] Tutti i quesiti di esame per corso di CR410 dell'AA 2011/12
  • [02/05/13] La lezione del 7 Maggio ├Ę annullata a causa di un impedimento del docente
  • [22/04/13] La seconda prova in itinere Ŕ fissata per il 28 Maggio alle ore 10:00 in aula G.
  • [14/03/12] La lezione prevista per oggi alle 16:00 ├Ę annullata.
  • [14/03/13] L'orario di ricevumento settimanale ├Ę stato spostato al mercoled├Č dalle 11 alle 13.
  • [26/02/13] La lezione prevista per oggi alle ore 16:00 ├Ę annullata.
  • [21/02/13] Il ricevimento del giorno 25 Febbraio 2013 Ŕ annullato.
  • [20/02/13] In data odierna la lezione comincia alle ore 17:00.
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma Esoneri/Esami

    Esoneri/Esami:

  • Appello C 3 Febbraio 2014
  • Appello X 13 Settembre 2013
    RISULTATI SCRITTI APPELLO X
    Matricola 1 2 3 4 5 6 7 8 9 10 TOT NORM
    417570 3 2 3 3 3 3 3 3 0 3 26 30
    427834 NA
    406074 3 3 3 0 3 3 3 3 3 3 27 30
    416840 3 3 3 3 3 3 1 3 1 3 26 30
    416639 3 3 3 3 2 3 2 0 3 3 25 28
    416961 3 2 3 0 3 3 1 1 0 3 19 24
  • Appello B 1 Luglio 2013
  • Appello A 7 Giugno 2013
  • Seconda Prova in Itinere 28 Maggio 2013
    RISULTATI ESAME DI FINE SEMESTRE
    MATRICOLA 1 2 3 4 5 6 7 8 TOT NORM FINAL
    427468 4,5 4,5 4,5 4,5 4,5 4,5 4,5 4,5 36 28 32
    418319 3,5 4,5 4,5 4,5 0 4,5 2,5 2,5 26,5 30 28
    438217 3,5 4,5 0 4,5 2,5 2,5 4,5 4 26 27 27
    427463 3,5 3,5 0 4,5 4,5 3,5 3 3 25,5 28 27
    440694 2,5 3,5 2 4,5 4,5 2,5 4 2,5 26 23 25
    271622 4 4,5 2 4,5 0 2,5 0 3,5 21 22 22
    246023 1,5 3 0 4,5 1,5 4 0 3 17,5 20 19
    406074 ASS 25 NA
    417570 ASS 22 NA
    415716 ASS 20 NA
    416639 ASS 20 NA
    418564 ASS 18 NA
  • Prima Prova in Itinere 3 Aprile 2013
    RISULTATI ESAME DI META' SEMESTRE
    MATRICOLA 1 2 3 4 5 6 7 8 9 10 TOT NORM
    418319 3 3 2 3 3 3 3 3 0 3 26 30
    427463 3 3 3 2 3 2 3 3 0 2 24 28
    427468 3 2 3 3 3 2 3 3 0 2 24 28
    438217 3 3 3 0 3 2 3 0 3 3 23 27
    406074 3 3 1 3 1 2 3 3 1 2 22 25
    440694 3 2 0 3 3 3 3 1 0 2 20 23
    271622 3 2 1 0 0 3 3 2 3 2 19 22
    417570 3 3 0 3 3 0 3 1 0 3 19 22
    246023 2 3 2 2 3 0 1 0 2 2 17 20
    415716 3 0 0 3 3 0 3 3 0 2 17 20
    416639 3 2 0 3 2 2 3 0 0 2 17 20
    418564 3 2 0 0 3 3 2 0 1 2 16 18
    415715 2 0 0 0 3 2 2 0 0 0 9 INS



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

    Diario delle Lezioni:

    1. Lezione [19/02/13] 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. Lezione [20/02/13] La nozione di operazione bit. La complessitÓ di somma, sottrazione, prodotto e divisione. La notazione "O grande". Esempi vari.
    3. Lezioni [21/02/13] Esempi e esercizi sul calcolo delle complessitÓ: Il fattoriale, il prodotto e somma di polinomi, Moltiplicazione alla Karatsuba e analisi della sua complessitÓ. Cambio di base.
    4. Lezioni [27/02/13] Algoritmi con complessitÓ polinomiale, esponenziale e subesponenziale. Algoritmo per il calcolo della parte intera della radice quadrata. divisibilitÓ di interi. distribuzione dei numeri primi. Inizio Algorimo di Euclide Algoritmo di Euclide binario. Esempi
    5. Lezioni [28/02/13] Analisi dell'Algoritmo di Euclide. Algoritmo di Euclide esteso. Calcolo dei coefficienti di Bezout mediante formule ricorsive. Esempi.
    6. Lezioni [05/03/13] Ultimi commenti sull'algoritmo di Euclide. Stime per i coefficienti di Bezout. Numeri coprimi. Funzione di Eulero. ProprietÓ ed esempi. Algoritmo dei quadrati successivi. Pseudo codice per l'algoritmo dei quadrati successivi e analsi dell'algoritmo.
    7. Lezioni [06/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
    8. Lezioni [07/03/13] Soluzione di congruenze lineari, Teorema Cinese dei resti e applicazioni. Piccolo Teorema di Fermat e Teorema di Eulero. L'algoritma RSA. Esempi. L'ipotesi RSA.
    9. Lezioni [12/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
    10. Lezioni [13/03/13] Rsa didattico. Generazione di numeri primi. Algoritmi probabilistici Las Vegas Distribuzione dei numeri primi e applicazione all'analisi di algoritmi Las Vegas.
    11. Lezioni [19/03/13] Inizio dei test di primalità. Probabili primi e pseudo primi. Pesudo primi di Fermat. Infinità degli pseudo primi di Fermat for ogni fissata base. Numeri di Carmichael e loro proprietà.
    12. Lezioni [20/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
    13. Lezioni [21/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
    14. Lezioni [03/04/13] PRIMA PROVA IN ITINERE
    15. Lezioni [09/04/13] Basi forti e pseudo primi forti. Numerazione delle basi forti per numeri dispari composti. Esempi.
    16. Lezioni [10/04/13] Test di primalitÓ di Miller Rabin. Test di primalitÓ probabilistici.
    17. Lezioni [16/04/13] Metodi di fattorizzazione con complessitÓ esponenziale. Fattorizzazione alla Fermat. Fattorizzazione alla Lehman. Metodo di Pollard (inizio). Il paradosso del compleanno.
    18. Lezioni [17/04/13] Metodi di fattorizzazione con complessitÓ esponenziale. Il metodo di Pollard (fine). Certificazione di primalitÓ: Certificazione alla Lucas, Criterio di Pepin, Teorema di Pocklington. Esempi.
    19. Lezioni [18/04/13] I simboli di Legendre e metodi per calcolarli. Applicazioni dei simboli di Legendre in Crittografia - Pseudo primi di Eulero.
    20. Lezioni [23/04/13] Fine Solovay - Strassen. Inizio Campi finiti.
    21. Lezioni [24/04/13] Campi Finiti. La cardinalit´┐Ż di un campo finito. ciclcit├á del gruppo moltiplicativo. Esistenza e unicit├. Propriet├á fondamentali e esempi. Struttura dl reticolo dei i sottocampi.
    22. Lezioni [30/04/13] Campi Finiti. Esempi. Ancora propriet├. Enumerazione dei polinomi irriducibili. Radici dei polinomi.
    23. Lezioni [02/05/13] Test di irriducibilità. Enumerazione polinomi primitivi.complessità delle operazioni nei campi finiti. Esercizi sui campi finiti dagli anni passati.
    24. Lezioni [08/05/13] Esercizi sui campi finiti dagli anni passati. campi con 125 elementi
    25. Lezioni [09/05/13] Applicazioni dei campi finiti in crittografia. Il protocollo dello scambio chiavi di Diffie Hellmann. Il crittosistema Massey Omura. Il crittosistema ElGamal,
    26. Lezioni [14/05/13] Esempi con GP-Pari al computer. Algoritmi per il calcolo di logaritmi discreti: Forza Bruta e BabyStepGiantStep
    27. Lezioni [15/05/13] Ancora sui logaritmi discreti. Esempi con BSGS Algoritmo Silver-Polhig-Hellman. Esempi. Analisi dell'Algoritmo Pohlig - Hellman. Curve ellittiche sui campi finiti.
    28. Lezioni [16/05/13] GeneralitÓ sulle curve ellittiche sui campi finiti. Somma di punti e punto all'infinito. La struttura di gruppo nell'insieme dei punti razionali. Formule per la somma e la duplicazione. Esempi. Equazioni di Weierstass (generali e in caratteristica maggiore di 3). Le formule per la somma.
    29. Lezioni [21/04/13] Curve ellittiche. Curve ellittiche in caratteristica 2. Enunciato del Teorema di Hasse e del Teorema di Struttura per il gruppo dei punti razionali.
    30. Lezioni [22/04/13] Ancora sulle curve ellittiche. Curve definite sui sottocampi. Calcolo dell'ordine del gruppo. Il metodo Baby Step Giant Step per calcolare il numero dei punti. Esempi e esercizi.
    31. Lezioni [23/04/13] Problemi vari sulle curve ellittiche dai testi di esame degli anni passati.
    32. Lezioni [28/05/13] SECONDA PROVA IN ITINERE

    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati Programma 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.