Copertina
Autore Andrea Sgarro
Titolo Crittografia
SottotitoloTecniche di protezione dei dati riservati
EdizioneMuzzio, Padova, 1993 [1985], Biblioteca , pag. 132, dim. 140x210x10 mm , Isbn 88-7021-640-3
Classe informatica , matematica
PrimaPagina


per l'acquisto

 

| << |  <  |  >  | >> |

Indice


Presentazione                          pag. VII

Prefazione alla seconda edizione              X

1 Cifrari manuali
  1 Messaggi e crittogrammi                   1
  2 Sostituzioni e trasposizioni              4
  3 Cifrari a sostituzione monoalfabetica     6
  4 Crittografia tattica e crittografia
    strategica                                9
  5 Cifrari a sostituzione polialfabetica    11
  6 Cifrari a trasposizione                  14

2 Crittanalisi statistica
  1 Struttura statistica dell'italiano
    scritto                                  19
  2 Un esempio di decrittazione
    semiautomatica                           23
  3 Crittanalisi dei cifrari polialfabetici  28
  4 Note consuntive sui cifrari manuali      34

3 Cifrari a rotore
  1 Macchine per cifrare                     37
  2 Alcune massime del buon crittografo      39

4 Il Data Encryption Standard
  1 Cifrari composti                         41
  2 La nuova crittografia                    43
  3 Dati binari, codici e cifrari            44
  4 Un po' di matematica binaria             47
  5 L'algoritmo di cifratura e decifrazione
    del DES                                  49
  6 Critiche rivolte al DES                  60

5 Un cifrario perfetto
  1 Un risultato sorprendente                63
  2 Un modello matematico delle sorgenti     64
    d'informazione
  3 Il cifrario a chiave non riutilizzabile  67
  4 Prestazioni del cifrario a chiave non
    riutilizzabile                           69
  5 Una digressione sulle aritmetiche
    circolari                                72
  6 L'alto prezzo della perfezione           73
  7 Cifre casuali e pseudocasuali            75

6 Alla ricerca della perfezion perduta
  1 Registri a scorrimento con retroazione
    lineare                                  77
  2 Registri a periodo massimo               80
  3 Proprietà di casualità                   83
  4 Uso crittografico dei registri lineari   85
  5 Attacchi crittanalitici con testo
    in chiaro                                86
  6 Uno sguardo nel buio: i registri
    non lineari                              88
  7 Cifrari a blocco e cifrari a flusso      90

7 Crittografia a chiave pubblica
  1 Chiave segreta e chiave pubblica         93
  2 Le funzioni unidirezionali e il
    logaritmo finito                         94
  3 Il logaritmo finito e la distribuzione
    delle chiavi                             98
  4 Il problema del fusto                   100
  5 Il cifrario del fusto                   103
  6 Il teorema di Fermat-Eulero             107
  7 Generazione di numeri primi elevati     109
  8 Il cifrario RSA                         114
  9 Autenticazione e firme numeriche        118
 10 Osservazioni critiche                   120
 11 Prospettive future                      123

Bibliografia                                127

Glossarietto crittografico inglese-italiano 131

 

| << |  <  |  >  | >> |

Pagina 1

1 Cifrari manuali

1 Messaggi e crittogrammi

Alcuni dei cifrati di cui parleremo in questo capitolo sono spesso adoperati sui banchi di scuola da ingegnosi ragazzetti che vogliono proteggere i loro messaggi riservati (si fa per dire!) dalle intercettazioni di un'arcigna maestra. Ciò non implica affatto che vogliamo iniziare il nostro dialogo partendo dalla crittografia ricreativa: i cifrari che descriveremo, sia pure ridotti al rango di comportamenti di sistemi complessi, sono assai importanti ancor'oggi: per convincersene basterà aspettare fino al capitolo 4.

In un sistema crittografico il testo in chiaro, o il messaggio, viene trasformato secondo certe regole nel testo in cifra, o crittogramma; tale operazione si chiama cifratura. Il crittogramma viene quindi spedito a destinazione tramite un opportuno canale di trasmissione, per esempio via radio o, più romanticamente, legandolo alla zampetta di un piccione viaggiatore. Del canale di trasmissione non ci si può tuttavia fidare: lungo il percorso è appostata una spia la quale può intercettare il crittogramma e tentare di decifrarlo. Anche il destinatario legittimo decifra il crittogramma e riottiene il testo in chiaro: se il sistema di cifra, o cifrario, è ben congegnato l'operazione di decifrazione o decifratura deve risultare piuttosto semplice al destinatario legittimo, ma di complessità proibitiva alla spia. Ciò è possibile perché il destinatario legittimo conosce certe informazioni che devono rimanere del tutto inaccessibili alla spia e che perciò non devono venire affidate al canale poco sicuro usato per trasmettere i crittogrammi. Tali informazioni costituiscono la chiave del cifrario.

| << |  <  |  >  | >> |

Pagina 41

4 Il Data Encryption Standard

1 Cifrari composti

Alla fme del capitolo 2 abbiamo accennato alle strade che la crittografia classica sembrava lasciare aperte a possibili sviluppi; nel capitolo 3 abbiamo visto come una di queste strade sia stata percorsa all'incirca fino alla metà di questo secolo. La situazione oggi è completamente cambiata per una ragione molto ovvia: è comparso il calcolatore, che è dotato di una capacità assai apprezzata dai crittografi e dai crittanalisti, quella di eseguire un numero sorprendente di operazioni ripetitive senza stancarsi mai. Ormai i rotori sono entrati nei musei della scienza; certi procedimenti di cifratura/decifrazione e certe tecniche crittanalitiche di complessità un tempo proibitiva sono oggidì alla portata di tutti.

Fra le strade lasciate aperte dalla crittografia classica c'è quella dei cifrari composti, cui abbiamo già accennato di sfuggita. Si tratta di un'idea feconda e insieme semplice che permette di rafforzare un sistema di cifra senza doverlo fare a spese di una crescita "esplosiva" (esponenziale) della complessità delle operazioni (legittime) di cifratura/decifrazione: si fa ricorso a strutture di tipo seriale, nelle quali tale complessità cresce in modo più o meno proporzionale al numero dei cifrari "elementari" che le compongono. Si pensi ad esempio al sistema rappresentato nella figura 4.1: il messaggio m viene cifrato dal cifrario a rotazione R1; il crittogramma c1 risultante funge da "messaggio" di ingresso per il secondo blocco costituente, un cifrario a trasposizione T1 che produce un nuovo crittogramma provvisorio c2; c2 viene cifrato dal cifrario a rotazione R2 che lo trasforma in c3; c3 viene finalmente trasposto da un cifrario a trasposizione T2 che produce il vero crittogramma, c4.

Beninteso la chiave del cifrario della figura è costituita dalle quattro chiavi dei cifrari componenti, R1, T1, R2 e T2, specificate nel loro giusto ordine. Non bisogna credere che i cifrari composti siano la panacea di tutti i mali: se non si presta sufficiente attenzione c'è il rischio che l'aumento di sicurezza sia del tutto illusorio. Ecco un paio di esempi ovvi: la concatenazione di due cifrari a rotazione è ancora un cifrario a rotazione, la concatenazione di due cifrari a trasposizione di periodo P è ancora un cifrario a trasposizione di periodo P; se i periodi sono Pl e P2 il risultato è un cifrario il cui periodo è pari al minimo comune multiplo di P1 e P2, per cui conviene che P1 e P2 siano numeri primi fra loro ecc. (l'ultima osservazione è utile a chi voglia attuare il cifrario di figura 4.1). L'analisi teorica dimostra soltanto che se si usano per i componenti della catena chiavi scelte indipendentemente l'una dall'altra le prestazioni del cifrario composto sono almeno pari a quelle del cifrario componente che nella catena è l'anello più solido: non viene garantito nessun guadagno, ma almeno si sa che non si può far peggio!

Il sistema illustrato in figura è un cifrario a sostituzioni e trasposizioni, proprio come il Data Encryption Standard, o DES, che è il protagonista di questo capitolo. Per ragioni di attuazione pratica i cifrari componenti in generale non sono completi (non lo sono nel DES: solo certe sostituzioni e certe permutazioni sono disponibili); questo ci ricorda che i problemi di complessità sopravvivono anche nell'epoca dei calcolatori elettronici: da quanto diremo nell'ultimo capitolo sembra perfino che siano oggi più importanti che mai.

| << |  <  |  >  | >> |

Pagina 63

5 Un cifrario perfetto

1 Un risultato sorprendente

Abbiamo appena visto come neppure il DES, che tuttavia è un cifrario piuttosto ponderoso, si salvi dalle critiche. Sembra dunque che l'ambizione secolare dei crittografi, quella di scoprire un cifrario perfetto, tale che il crittogramma, in mancanza della chiave, non fornisca nessuna informazione sul messaggio in chiaro, sia destinata a restare insoddisfatta. Ebbene, uno dei risultati più sorprendenti della crittologia moderna è che un tale cifrario in realtà esiste, come si può dimostrare con rigorose argomentazioni matematiche. Ciò sembra implicare che la crittologia abbia esaurito il suo compito e che le ricerche crittologiche siano ormai ridotte a uno sterile passatempo accademico.

Per fortuna, o per sfortuna, ciò non è affatto vero: vedremo infatti che i cifrari perfetti sono così farraginosi che il loro impiego nella maggioranza delle situazioni pratiche resta precluso; si è allora costretti a ripiegare su cifrari meno perfetti ma più realistici, come il DES. Anche questo risultato negativo non è una mera congettura, bensì un rigoroso teorema di matematica. Ora i teoremi di matematica non si applicano a concetti la cui definizione sia più o meno vaga: il primo passo che dobbiamo fare è dunque quello di fornire un modello adeguato e ben preciso dei sistemi crittografici di cui ci stiamo occupando.

Il processo di matematizzazione o di formalizzazione della crittografia è legato in maniera essenziale al nome di Claude Shannon e al suo già citato articolo "Communication theory of secrecy systems", pubblicato nel 1949: si è spesso affermato che solo dopo le ricerche di Shannon la crittologia è davvero diventata "scienza" (ciò non toglie che la fantasia e certe abilità "artigianali" rimangono ancor'oggi doti essenziali di un abile crittografo o crittanalista).

| << |  <  |  >  | >> |

Pagina 77

7 Crittografia a chiave pubblica

1 Chiave segreta e chiave pubblica

Già nel capitolo dedicato al Data Encryption Standard abbiamo visto che oggi la crittografia deve far fronte a esigenze completamente nuove legate all'impiego sempre più diffuso del calcolatore. Può destare meraviglia che le risposte che la crittografia ha saputo trovare, perlomeno quelle che abbiamo illustrato fino a questo punto, siano tutto sommato di tipo tradizionale. Ciò è vero per il DES, ma in una certa misura è anche vero per il cifrario a chiave non riutilizzabile e per le sue approssimazioni pseudoperfette: i cifrari polialfabetici basati su una parola-chiave, di cui i cifrari perfetti e pseudoperfetti sono i legittimi discendenti, erano già stati studiati dall'Alberti in pieno Rinascimento. (L'età veneranda delle soluzioni non implica affatto che oggi esse non siano più valide: i cifrari pseudoperfetti e i problemi connessi di generazione di cifre binarie pseudocasuali rappresentano probabilmente il punto nodale della crittografia contemporanea.)

Tutti i sistemi di cifra fin qui esposti presupponevano che la chiave di cifratura fosse tenuta rigorosamente segreta. In questo capitolo illustreremo dei sistemi che costituiscono un'innovazione radicale rispetto al passato: in essi la chiave di cifratura è un'informazione divulgata pubblicamente, ad esempio stampandola su una specie di elenco telefonico dove accanto al nome di ciascun utente è riportata la chiave che deve usare chi voglia trasmettergli un messaggio riservato.

In tal modo si supera un problema gravissimo della crittografia tradizionale, quello della distribuzione delle chiavi.

Quanto abbiamo detto sembra paradossale, ma non lo è: si possono escogitare sistemi crittografici in cui la chiave di cifratura e quella di decifrazione sono "essenzialmente" diverse, per cui basta tener segreta quest'ultima.

In tutti i sistemi crittografici classici, a chiave segreta, la chiave di cifratura e quella di decifrazione sono "essenzialmente" uguali, nel senso che, anche se non coincidono, la seconda può venire immediatamente ricavata dalla prima: per esempio in un cifrario a sostituzione le due chiavi si avvalgono della stessa permutazione, letta in un senso in cifratura e nell'altro in decifrazione.

Nei sistemi a chiave pubblica l'operazione di ricavare la chiave di decifrazione da quella di cifratura è troppo complessa per venire eseguita in pratica.

Ma stiamo anticipando: i principi generali saranno più chiari quando avremo esposto qualche esempio specifico.

Per non suscitare aspettative eccessive nel lettore diciamo subito che la crittografia a chiave pubblica non è esente da critiche: le speranze che in essa si ripongono sembrano tuttavia ben giustificate.

| << |  <  |