CR410 - Crittografia I

1. Lezione [20/02/12] 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 [21/02/12] La nozione di operazione bit. La complessità di somma, sottrazione, prodotto e divisione. La notazione "O grande". Esempi vari.
3. Lezioni [22/02/12] 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. Lezioni [27/02/12] 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 [28/02/12] Richiami sulla nozione di divisibilità, sui numeri primi. Enunciato del Teorema dei numeri primi e del Teorema di Chebichev. 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 [29/02/12] 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 [05/03/12] L'algoritmo dei quadrati successivi. 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.
8. Lezioni [06/03/12] ESERCIZI VARI SULLA COMPLESSITA' E SUI PRIMI ALGORITMI
9. Lezioni [07/03/12] 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 (cioè l'ipotesi RSA).
10. Lezioni [12/03/12] Etnomatematica: sistemi di numerazione posizionali e non, rappresentazioni dei numeri in basi diverse. Complessità computazionale: notazione "O-grande" e funzioni asintotiche, test di primalità di Wilson, crivello di Eratostene, algoritmo di Ruffini-Horner. Il teorema dei numeri primi: formulazioni equivalenti ed applicazioni. Densità dei numeri primi: il teorema di Euler. Esercizi
11. Lezioni [14/03/12] Richiami di teoria elementare dei numeri. Complessità computazionale su insiemi numerici finiti. Crittosistema RSA: codifica e decodifica. RSA didattico. Esercizi
12. Lezioni [19/03/12] Come produrre numeri primo "grandi". Algoritmi probabilistici e analisi del loro errore. Esempi. Ancora sul problema di produrre numeri primi random. Differenza tra numeri primi successivi. La Congettura di Cramér.
13. Lezioni [20/03/12] 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à.
14. Lezioni [21/03/12] 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.
15. Lezioni [26/03/12] 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.
16. Lezioni [27/03/12] Pseudo primi forti, calcolo della probabilità di errore degli algoritmi Montecarlo. Successione di Miller Rabin. 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à.
17. Lezioni [28/03/12] Ancora sulle basi forti. Il testi di primalità di Miller Rabin. Esempi ed Esercizi dai vecchi compiti.
    
    ESAME DI META' SEMESTRE[04/04/12]
    

    Lezioni [16/04/12] Certificazione di primalità. Teorema di Pocklington, Ancora sui certificati di primalità. Fattorizzazione. Metodo della forza bruta, fattorizzazione alla Fermat. Metodo ρ di Pollard (Inizio)

    Lezioni [17/04/12] Metodo ρ di Pollard (continua), paradosso del compleanno, analisi del metodo di Pollard, Esempi vari.

    Lezioni [18/04/12] fine del metodo ρ di Pollardi. Campi Finiti. Richiami delle proprietà di base. La cardinalità di un campo finito. Esempi. Teorema di esistenza e unicità del campo di spezzamento.

    Lezioni [23/04/12] Campi finiti: Esempi di Campi finiti. complessità delle operazioni nei campi finiti. Esistenza e unicità dei campi finiti. La formula sbagliata. Dimostrazioni delle formule per l'enumerazione dei polinomi irriducibili.

    Lezioni [24/04/12] Campi finiti: Struttura del reticolo dei sottocampi. Il gruppo moltiplicativo è ciclico. Radici di un polinomio irriducibile. Ordine di un polinomio. Polinomi primitivi.

    Lezioni [02/05/12] Enumerazione dei polinomi primitivi. Calcoli vari su campi finiti con 125 e 32 elementi. Analisi della complessità  dei test di irriducibilità  dei polinomi a coefficienti su un campo finito. Applicazioni dei campi finiti in crittografia. Il protocollo dello scambio chiavi di Diffie Hellmann. Il crittosistema Massey Omura.

    Lezioni [07/05/12] Il crittosistema ElGamal, Ancora sui crittosistemi basati sui logaritmi discreti. Baby Step Giant Step.

    Lezioni [08/05/12] Algoritmo Pohlig - Hellman. Esempi. Analisi dell'Algoritmo Pohlig - Hellman. Esempi di implementazioe su PARI di crittosistemi basati su logaritmi discreti su un campi con 2¹⁰⁰ elementi. Inizio svolgimento del compito di fine semestre per il corso dell'AA 2007/08.

    Lezioni [09/05/12] Fine svolgimento del compito di fine semestre per il corso dell'AA 2007/08. Sistemi di firma digitale Definizioni, Esempi. Il sistema DSS (inizio).

    Lezioni [14/05/12] LEZIONE ANNULLATA CAUSA INDISPONIBILITA' DEL DOCENTE

    Lezioni [15/05/12] 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 e esercizi.

    Lezioni [16/05/12] Equazione di Weierstrass Generale. Curve ellittiche in caratteristica 2. Enunciato del Teorema di Hasse e del Teorema di Struttura per il gruppo dei punti razionali.

    Lezioni [21/05/12] 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.

    Lezioni [22/05/12] Problemi vari dai testi di esame degli anni passati. Il sistema DSS (fine).

    
    ESAME DI FINE SEMESTRE[28/05/08]
    

Testi consigliati: