Indice

Crittografia

Indice

Software

Link

Errata

Indice

Introduzione alla Crittografia, Alessandro Languasco & Alessandro Zaccagnini, Ulrico Hoepli Editore, Milano, 2004.

Alcuni dei nostri Lettori ci hanno contattato perché hanno incontrato difficoltà superiori a quelle che si aspettavano avendo letto la quarta di copertina, nella quale affermiamo che sono sufficienti le quattro operazioni delle scuole elementari per capire quasi tutto il nostro libro. Se da una parte siamo sempre convinti della bontà di quella affermazione, dall'altra vogliamo qui offrire una guida alla lettura, sperando di essere di aiuto. Per par condicio, altri lettori ci hanno rimproverato di aver scritto un testo superficiale…

Per prima cosa dobbiamo dire che il nostro non è un libro di divulgazione. Non è nostra intenzione denigrare tali tipologie di pubblicazioni (che peraltro anche noi scriviamo) ma i molti recenti lavori divulgativi usciti sull'argomento della Crittografia tendono (e probabilmente non possono fare diversamente) a “sorvolare” sugli aspetti matematici che consentono di capirne il funzionamento. Alla fine di tali letture, invariabilmente, il funzionamento intimo dei crittosistemi rimane una “scatola nera”.

Siccome siamo convinti che non si possa fare a meno della Matematica per capire come e perché la Crittografia funziona, abbiamo tentato di sviluppare quella che riteniamo necessaria a tale scopo in modo da offrire un testo il più possibile autocontenuto. Fortunatamente tutti i metodi classici e molti di quelli moderni possono essere spiegati con della Matematica elementare; il che non significa che essa sia semplice, che sia parte del curriculum di studi di una scuola superiore o che non richieda uno sforzo da parte del Lettore che vuole davvero entrare nella “scatola nera”. Questo pensiamo che sia il maggiore equivoco indotto nei Lettori da parte di molte pubblicazioni divulgative.

Peraltro molti altri metodi moderni richiederebbero lo sviluppo di argomenti di Matematica più avanzati che abbiamo ritenuto non essere adatti ad un libro introduttivo all'argomento; infatti essi richiedono perlomeno la preparazione della Laurea Triennale in Matematica.

In un certo senso, il problema principale sta nel fatto che si tende a leggere i libri come se fossero dei romanzi, cominciando dalla prima pagina e andando avanti: per questo motivo, nella nostra “Nota degli Autori” a pagina 10 abbiamo consigliato di saltare alcune parti, almeno in una prima lettura, perché potrebbero risultare ostiche.

Un percorso relativamente semplice nel nostro materiale può essere il seguente: provate a leggere i primi 2 paragrafi del Capitolo 2, svolgendo anche una buona parte degli esercizi, e poi passate ai primi 2 o 3 paragrafi del Capitolo 3, anche qui svolgendo gli esercizi. In questi paragrafi è letteralmente vero che sono sufficienti le quattro operazioni. Questo dovrebbe fornire le basi matematiche ed il linguaggio della Crittografia moderna, senza però introdurre concetti particolarmente astratti, tranne forse quello di ordine di un elemento di un gruppo. Ci permettiamo di insistere sugli esercizi: per capire davvero è necessario “sporcarsi le mani” risolvendone molti. Per la maggior parte, è sufficiente una calcolatrice tascabile e un po' di pazienza.

A questo punto si può cercare di consolidare la preparazione matematica leggendo anche i primi due paragrafi del Capitolo 1, e magari rileggando rapidamente le parti già studiate alla luce del Capitolo 1, oppure passare alla Crittografia vera e propria, cominciando per esempio dai paragrafi 1, 2, 3, 6, 7, 8, 9 del Capitolo 5. Anche il Capitolo 6, ed in particolare i paragrafi 2, 3, 4 (e in parte anche il 5) dovrebbe essere abbordabile, mentre l'intero Capitolo 7 può essere letto senza troppe difficoltà se si conoscono le nozioni preliminari indicate qui sopra.

Questo è un percorso in cui inizialmente si trascurano gli aspetti piú astratti (Capitolo 1; Capitolo 2, paragrafo 3; Capitolo 3, paragrafi 4-8, Capitolo 4) o formali (Capitolo 5, paragrafi 4-5; Capitolo 6, paragrafo 1). Per completezza abbiamo incluso anche tutti questi aspetti, che sono in un certo senso le fondamenta su cui è basata la Crittografia, sia quella moderna in senso stretto, sia quella sviluppata nell'Antichità. Anche se quest'ultima è stata descritta inizialmente senza alcun riferimento a concetti matematici, uno degli scopi del nostro libro è quello di fornire una visione unificata (per mezzo della Matematica) dei problemi della Crittografia moderna e di quella classica.

Equazioni e aritmetica
1. L'equazione zⁿ = 1
  - Radici quadrate
2. Il gruppo Z_n
3. Gruppi: Definizioni e Teoremi fondamentali
  - Omomorfismi ed isomorfismi
  - Prodotti diretti
Le congruenze
1. Aritmetica modulo n
  - Proprietà delle congruenze
2. L'Algoritmo di Euclide
3. Anelli: Definizioni e Teoremi fondamentali
Proprietà aritmetiche dei numeri primi
1. Definizioni e prime proprietà
2. Il Teorema di Fermat e le sue conseguenze
3. Il Teorema di Gauss
  - Applicazione: Numeri pseudo-casuali
  - Problemi
4. Pseudoprimi e numeri di Carmichael
5. La funzione φ di Eulero
6. Dimostrazione del Teorema di Gauss
7. La legge di reciprocità quadratica
8. Altre condizioni necessarie per la primalità
  - Pseudoprimalità di Eulero
  - Pseudoprimalità Forte
  - Verifica della primalità in insiemi finiti
Campi
1. Definizioni generali
2. Come costruire campi finiti
3. Costruzione di F₄ e di F₈
4. Costruzione di F₂₇
5. Campi finiti
6. Un campo particolarmente interessante
7. Campi algebricamente chiusi
  - Formula dell'equazione di secondo grado
Crittografia
1. Introduzione
2. Crittosistema
3. Cenni storici
4. Teoria di Shannon
  - Cifrario perfetto (one-time pad)
5. Crittanalisi: cenni
6. Crittografia classica
  - Crittosistemi a pacchetto
    - Metodo ECB
    - Metodo CBC
    - Metodo CFB
    - Metodo OFB
  - Crittosistemi a flusso
  - Crittosistemi affini
  - Crittosistema Feistel
  - DES (Data Encryption Standard)
    - Chiave del DES
    - Cifratura del DES
    - Permutazione π
    - Chiave di ciclo
    - Funzioni E, S e P
    - Decifratura del DES
    - Considerazioni finali
  - AES (Rijndael)
    - Una descrizione di alto livello
    - Funzione S
    - Stato s
    - Funzione SR
    - Funzione MC
    - Funzione E: definizione delle chiavi di ciclo
    - Decifratura di AES
    - Considerazioni finali
7. Crittografia a chiave pubblica
8. Lo scambio di chiavi nel crittosistema di Diffie ed Hellman
9. Il crittosistema RSA di Rivest, Shamir e Adleman
  - Attacchi a RSA
    - Un attacco a RSA di tipo chosen-ciphertext
    - Attacchi elementari
    - Punti fissi
    - Cycling attack
    - Attacco causato da una chiave privata troppo "piccola"
    - Attacco a partire da una conoscenza parziale della chiave privata (e "piccolo")
    - Cifre esposte della chiave privata (e "piccolo")
    - Attacco ad una trasmissione a molti (e "piccolo")
    - Attacco a messaggi collegati in modo noto ("e piccolo")
    - Attacco a messaggi collegati in modo parzialmente casuale ("e piccolo")
  - Attacchi all'implementazione di RSA
    - Timing attacks
    - Random Faults
    - Bleichenbacher's attack
  - Esempio pratico di codifica con RSA
10. Il crittosistema di Rabin
  - Sicurezza del sistema Rabin
11. Il crittosistema di ElGamal
12. Il crittosistema di Massey-Omura
13. Firma digitale
  - Schema generale di firma digitale
  - Firma digitale: certificazione dell'identità con RSA
  - Firma digitale: certificazione dell'identità con ElGamal
14. Vantaggi della crittografia a chiave pubblica
15. Crittografia e curve ellittiche
Algoritmi
1. Aritmetica in base b e Complessità Computazionale
  - Numeri in base b
  - Operazioni Elementari, Complessità della somma di interi
  - Complessità del prodotto di interi
  - Cambiamento di base, Radice quadrata intera binaria
2. L'algoritmo di Euclide
  - Complessità dell'Algoritmo di Euclide
  - Soluzione dei sistemi di congruenze lineari
3. Il crivello di Eratostene
4. Criteri di primalità
  - Certificati di primalità succinti
5. Fattorizzazione: algoritmi esponenziali
  - Divisione per tentativi
  - Fattorizzazione "alla Fermat" (Algoritmo di Lehman)
  - Fattorizzazione e crivello
  - Il metodo ρ di Pollard
  - Metodo p − 1 di Pollard
6. Fattorizzazione: algoritmi subesponenziali
  - Il crivello quadratico di Pomerance
  - Esempio numerico
    - Scelta della "base di fattori"
    - Fattorizzazione completa sulla base di fattori
    - Algebra lineare: eliminazione di Gauss
  - Il crivello con i campi di numeri
7. Ricerca di un generatore in Z_p^*
8. Logaritmo discreto
  - L'algoritmo di Shanks: baby steps, giant steps
9. Algoritmi ausiliari
  - Calcolo di prodotti modulo n
  - Calcolo di potenze modulo n
  - Calcolo di potenze di polinomi modulo n e un polinomio
  - L'Algoritmo della Divisione con Resto
Alcuni protocolli crittografici
1. Introduzione
2. Protocolli di base
  - Scambio delle chiavi
    - Metodo di Diffie-Hellman con tre o piú persone
    - Scambio chiavi in tre passi
  - Autenticazione
    - Autenticazione con scambio delle chiavi
  - Secret Splitting
  - Secret Sharing
  - Secret Broadcasting
3. Protocolli intermedi
  - Marcatura Temporale di un documento (Timestamping)
  - Canali subliminali
  - Firma di gruppo
  - Testa o Croce?
  - Poker mentale
  - Bit Commitment
4. Protocolli avanzati
  - Dimostrazioni a conoscenza nulla
    - Dimostrazione a conoscenza nulla del logaritmo discreto
  - Identificazione a conoscenza nulla
    - Protocollo di Fiat e Shamir
    - Protocollo di Schnorr
  - Firma cieca
  - ANDOS
  - Trasferimento privo di memoria (Oblivious Transfer)
  - Firma simultanea
  - Posta certificata
  - Elezioni elettroniche
  - Cena dei Crittografi
  - Denaro elettronico
    - Protocollo di prelevamento
    - Protocollo di pagamento
    - Protocollo di deposito
Distribuzione dei numeri primi
1. Euristica
2. Risultati quantitativi
3. Numeri senza fattori primi grandi
4. Formule per i numeri primi
5. Pseudoprimi e numeri di Carmichael
Introduzione a PARI/Gp
1. Introduzione
2. Alcuni strumenti di calcolo
3. Primi passi con PARI/Gp
  - Documentazione
  - Primi passi
  - Help in PARI/Gp
4. Programmare in PARI/Gp: alcuni comandi di base
  - Leggere un file
  - Argomenti di funzioni e loro passaggio
  - Variabili locali
  - Come inserire i dati
  - Scrivere in un file
5. Alcune famose asserzioni sui primi
6. Esempi in PARI/Gp
  - Distribuzione dei primi
  - Calcoli riguardanti RSA in PARI/Gp
  - Altri esempi in PARI/Gp
  - Alcuni Esercizi
Letture ulteriori
1. Strutture algebriche
2. Struttura di Z_n e di Z_n^*
3. Algoritmo di Euclide
4. Polinomi e Congruenze
5. Pseudoprimi e numeri di Carmichael
6. Criteri di primalità
7. Algoritmi di fattorizzazione
8. Algoritmi per il logaritmo discreto
9. Altri algoritmi
10. Curve ellittiche
11. Crittografia
12. Teoria di Galois
13. Il Teorema dei Numeri Primi
14. Altri risultati sulla distribuzione dei numeri primi
15. Ipotesi di Riemann
16. Altri riferimenti
Appendice. Complementi
1. Classi di Complessità dei problemi di decisione
  - La classe P
  - La classe NP
  - Problemi NP-completi
  - Altre classi: BPP, RP, ZPP
  - Relazioni tra le classi
2. Il principio dei cassetti
3. Funzioni aritmetiche
4. Relazioni di equivalenza
5. La Notazione di Bachmann-Landau
6. La Formula di Stirling
7. Il paradosso dei compleanni
8. Frazioni continue
9. Alcuni cenni di Algebra lineare
  - Matrici
  - Determinante di una matrice
  - Matrici Elementari
Bibliografia
Indice analitico

Ultimo aggiornamento: 15.12.2010: 12:55:00.

Crittografia

Indice

Software

Link

Errata