l'insieme {0,1,2,
,n-1} dei possibili resti della divisione di un intero per n.CRITTOGRAFIA
1 giugno 2000
Umberto Cerruti
Università di Torino
La crittografia si occupa dei metodi atti a trasformare un testo dato in una lingua corrente, comprensibile a tutti quelli che la conoscono, detto testo in chiaro, in un documento comprensibile soltanto a coloro che hanno diritto ad accedere all'informazione in esso contenuta, detto testo cifrato.
La necessità della crittografia è, al giorno d'oggi, evidente: una parte della comunicazione che avviene tra enti e individui deve essere riservata; si pensi per esempio a comunicazioni bancarie o militari. Inoltre la crittografia serve a proteggere il copyright di testi, software, o immagini per i quali si desidera mantenere il diritto d'autore.
Fin dall'antichità, anche se gli strumenti matematici necessari non erano ancora noti in modo esplicito, la crittografia ha utilizzato metodi basati sull'aritmetica modulare.
1 - L'aritmetica modulo n (I).
Nel seguito N e Z denotano rispettivamente l'insieme dei numeri naturali {0,1,2, } e l'insieme degli interi relativi { -2,-1,0,1,2, }.
Dati a, b in Z ed n > 1 in N, diciamo che a è congruo a b modulo n se a e b divisi per n danno lo stesso resto; in questo caso scriviamo a = b mod n. La relazione di congruenza è una relazione di equivalenza.
Per esempio: 0 = 7 mod 7, n = 0 mod n, 13 = 3 mod 10, -6 = 7 mod 13, 2 = 5 mod 3.
Ovviamente a = b mod n se e solo se a = b + kn con k in Z.
Fissato un numero naturale n, esistono n possibili resti della divisione di un intero a per n: 0,1,..,n-1.
Esiste infatti l'algoritmo della divisione per cui dati a ed n, esistono e sono unici il quoziente q ed il resto r (compreso tra 0 ed n-1) per cui n = aq + r.
Denotiamo con l'insieme {0,1,2,
,n-1} dei possibili resti della divisione di un intero per n.
In sono possibili la somma, la differenza e la moltiplicazione modulo n.
Per esempio 2+3 = 0 mod 5, 2* 3 = 1 mod 5, 14 + 5 = 4 mod 15, 2 7 = 8 mod 13, 7* 7 = 0 mod 49.
Semplicemente si calcola il risultato u dell'operazione algebrica in Z, e si sostituisce u con u mod n, cioè si sostituisce u con il resto della divisione di u per n.
2 - La sostituzione monoalfabetica.
Uno dei primi codici crittografici conosciuti è il codice di Giulio Cesare.
Consideriamo per il momento l'alfabeto A={a,b, ,z} formato dalle 21 lettere minuscole della lingua italiana.
Un testo T è una successione finita di elementi di A. L'idea di Cesare era quella di sostituire ogni lettera in T con la lettera che la segue in A a tre passi di distanza; Immaginiamo che A sia scritto in cerchio: a un passo da z c'è a, a due passi da z c'è b, a tre passi c'è c
Otteniamo così la seguente tavola di sostituzione:
Tavola A
|
a |
b |
c |
d |
e |
f |
g |
h |
i |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
z |
|
d |
e |
f |
g |
h |
i |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
z |
a |
b |
c |
In base a questa tavola il testo T = "domani parto" diventa C = "grpdqn sduzr".
T è il testo in chiaro e C è il testo cifrato.
Nella Tavola A viene creata una corrispondenza biunivoca tra l'alfabeto A e A stesso. Poiché A è finito, questo equivale a dire che a lettere diverse corrispondono lettere diverse.
La matematica ora interviene in modo fondamentale nel dare un modello aritmetico di questa idea importante: modello che si rivelerà capace di notevoli e utili generalizzazioni.
Ragioniamo ora modulo 21 (il numero dei simboli in A). Possiamo dare una corrispondenza biunivoca tra l'insieme delle 21 lettere e l'insieme Z20 = {0,1,2, ,20}:
Tavola B
|
a |
b |
c |
d |
e |
f |
g |
h |
i |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
z |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
Sostituendo i numeri alle lettere nella Tavola A otteniamo la Tavola C:
Tavola C
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
0 |
1 |
2 |
Ora ogni lettera è un numero. Chiamiamo 
la funzione di codificazione:
la tavola C si esprime semplicemente, in aritmetica modulare, così:
= h+3 mod 21
L'indice in basso (il numero 3) è la chiave segreta.
Chi riceve il messaggio e conosce la chiave segreta, applica la funzione di decodifica
= h-3 mod 21
La procedura per mettere in cifra un messaggio è allora la seguente:
Si prende il testo da inviare (per esempio "se lo sognano").
Si sceglie una chiave k, cioè un intero compreso tra 1 e 20 (per esempio k = 5).
Si trasforma il messaggio in una lista di numeri con la tavola B (nell'esempio si ottiene 16 4 9 12 16 12 6 11 0 11 12).
Si applica ad ogni numero la funzione di codifica 
; questo equivale ad utilizzare una tavola come la C, con k al primo posto della seconda riga. (nell'esempio si somma 5 modulo 21 ad ogni intero che compone il messaggio e si ottiene il messaggio cifrato: 1 9 14 17 0 17 11 16 5 16 17).
[Domanda: vi siete chiesti perché la chiave 0 non viene considerata?]
Il problema di questo codice crittografico è che lo spazio delle chiavi è troppo piccolo: ci sono appena 20 chiavi utilizzabili. Chi intercetta il messaggio può facilmente decodificarlo provando tutte chiavi una dopo l'altra! Questo metodo di rottura del codice è detto ricerca esaustiva nello spazio delle chiavi; è un metodo di forza bruta che porta sempre al risultato voluto se lo spazio delle chiavi non è abbastanza grande. Ovviamente l'aggettivo "grande" ha significato molto diverso a seconda dei mezzi di calcolo di cui si dispone.
Una prima osservazione che si può fare è che la tavola C è semplicemente una permutazione dei ventuno numeri 0,1,2, ,20; è un loro particolare ordinamento. Per ottenere un codice di sostituzione monoalfabetica diverso dai 20 che abbiamo potremmo scrivere i numeri da 0 a 20 su ventuno carte, mescolarle ben bene, allinearle sulla tavola e poi scrivere la successione ottenuta nella seconda riga della tavola C. Ora la chiave è la tavola stessa. Per esempio una chiave può essere:
Tavola D
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
4 |
9 |
18 |
8 |
13 |
5 |
10 |
20 |
15 |
14 |
12 |
6 |
17 |
1 |
11 |
3 |
7 |
2 |
19 |
16 |
0 |
Le persone che intendono scambiarsi messaggi cifrati condividono la tavola D: la usano dall'alto in basso per cifrare e dal basso in alto per decifrare.
Esistono 21! (si legge ventuno fattoriale) permutazioni diverse su 21 lettere.
Il numero n! è uguale a 
. Dunque ci sono 21!=51.090.942.171.709.440.000 chiavi a disposizione: più di 51 miliardi di miliardi di chiavi! Se con un calcolatore impieghiamo un microsecondo per provare una chiave (eseguire cioè una permutazione) occorrerà più di un milione di anni per esaurire lo spazio delle chiavi!
Esistono però metodi statistici per rompere un codice di sostituzione monoalfabetica. Essi si basano sul fatto che ogni lettera appare in un certa lingua con una sua frequenza caratteristica. Per esempio la lettera più frequente in italiano è la 'a'; se nel messaggio intercettato si trova che il numero 4 appare con la maggiore frequenza si può provare a sostituirlo con la a. Così si fa con le altre lettere basandosi sulla frequenza con cui i simboli appaiono nel messaggio. Chi vuole capire bene questo metodo, divertendosi, può leggere il racconto di Edgar Allan Poe "Lo scarabeo d'oro", pubblicato nel 1843, nel quale Legrand scopre il tesoro del capitano Kidd decifrando un messaggio in codice trovato su duna pergamena.
Questo oceano di chiavi non serve dunque a nulla! Che fare?
3 Codici a sostituzione polialfabetica.
Un passo in avanti decisivo venne fatto da Blaise de Vigenère (1523 1596). La chiave è adesso una parola chiave. Supponiamo che la parola chiave (segreta e condivisa soltanto da coloro che vogliono comunicare) sia "voce" e il testo in chiaro sia "se lo sognano" (come nell'esempio precedente). Si trasformano il testo e la chiave in sequenze di numeri, come prima:
"se lo sognano" = 16 4 9 12 16 12 6 11 0 11 12
"voce" = 19 12 2 4
Poi si ripete la chiave sotto il messaggio, quante volte basta:
|
16 |
4 |
9 |
12 |
16 |
12 |
6 |
11 |
0 |
11 |
12 |
|
19 |
12 |
2 |
4 |
19 |
12 |
2 |
4 |
19 |
12 |
2 |
Poi si somma modulo 21 ottenendo 14 16 11 16 14 3 8 15 19 2 14
Ritornando alle lettere si ha la sostituzione:
|
chiaro |
S |
E |
L |
O |
S |
O |
G |
N |
A |
N |
O |
|
cifrato |
Q |
S |
N |
S |
Q |
D |
I |
R |
V |
C |
Q |
Osserviamo che accadono due cose fondamentali:
E' evidente che questo tende a distruggere la corrispondenza tra le frequenze relative delle lettere nel testo in chiaro e quelle dei simboli nel messaggio cifrato (corrispondenza che era proprio il punto debole dei codici monoalfabetici).
Questa corrispondenza sarà tanto più debole quanto più lunga e casuale è la parola chiave. Nel caso in cui la parola chiave sia composte di lettere (o numeri) estratte a caso e sia lunga come il testo in chiaro, il messaggio cifrato apparirà completamente casuale, e nessun tipo di indagine effettuata su di esso riuscirà a far affiorare il messaggio originale.
Facciamo un esempio.
Consideriamo il testo in chiaro precedente "se lo sognano" = 16 4 9 12 16 12 6 11 0 11 12.
Costruiamo una parola chiave casuale lunga come il messaggio (11 lettere) estraendo 11 interi casuali compresi tra 0 e 20. Io ho ottenuto 17 12 14 0 4 20 15 6 14 2 3.
Sommiamo modulo 21 la chiave al testo in chiaro. Otteniamo:
|
chiaro |
16 |
4 |
9 |
12 |
16 |
12 |
6 |
11 |
0 |
11 |
12 |
|
chiave |
17 |
12 |
14 |
0 |
4 |
20 |
15 |
6 |
14 |
2 |
3 |
|
cifrato |
12 |
16 |
2 |
12 |
20 |
11 |
0 |
17 |
14 |
13 |
15 |
In lettere:
|
chiaro |
S |
E |
L |
O |
S |
O |
G |
N |
A |
N |
O |
|
chiave |
T |
O |
Q |
A |
E |
Z |
R |
G |
Q |
C |
D |
|
cifrato |
O |
S |
C |
O |
Z |
N |
A |
T |
Q |
P |
R |
Chi intercetta il testo cifrato "oscoznatqpr" non potrà mai risalire al messaggio originale "selosognano" perché, visto che la parola chiave è casuale, qualsiasi testo di 11 lettere ha la stessa probabilità di divenire il codice "oscoznatqpr".
I codici di Vigenère con parola chiave casuale lunga quanto il messaggio sono perfetti: chi legge il messaggio cifrato e non possiede nessuna informazione aggiuntiva non può in nessun modo ricostruire il testo in chiaro.
Osserviamo un punto debole: se la spia viene a sapere che il messaggio originale era "selosognano", può ricavare la parola chiave mediante differenza:
chiave = testo cifrato testo in chiaro mod 21.
Affinché il codice sia inviolabile è dunque necessario e sufficiente cambiare la parola chiave ogni volta che si invia un messaggio.
[Domanda: visto che questi codici sono inviolabili, perché non consideriamo chiuso il discorso e ci limitiamo a usare questi?]
Il cifrario di Vigenère con parola chiave più corta del messaggio non è invece inattaccabile.
Fu l'ufficiale prussiano Friedrich Kasiski (1805-1881) il primo trovare un metodo per romperlo. Se la parola chiave è lunga m e formiamo m righe, mettendo a turno in ognuna di esse le lettere del messaggio cifrato otteniamo m codici di sostituzione monoalfabetica che si possono attaccare con il metodo statistico sopra descritto.
Se per esempio la chiave è lunga 3 ed il messaggio cifrato è c1 c2 c3 c4 ..c1000 scriviamo:
riga 1 : c1 c4 c7 c10 c997 c1000
riga 2 : c2 c5 c8 c11 c998
riga 3 : c3 c6 c9 c12 c999
Le lettere nella riga 1 sono state ottenute tutte con la medesima sostituzione, data dalla prima lettera della chiave. Le lettere nella riga 2 sono state ottenute tutte con la medesima sostituzione, data dalla seconda lettera della chiave, etc.
Vi sono anche algoritmi, facilmente implementabili su un computer, per determinare la lunghezza della parola chiave, se il messaggio è abbastanza lungo.
Per maggiori dettagli si consulti la bibliografia.
Per trattare un poco di moderni e più potenti algoritmi crittografici, occorre apprendere altre nozioni di Aritmetica modulare.
4 L'aritmetica modulo n (II)
Dato l'intero n > 1 diciamo C(n) l'insieme degli interi compresi tra 1 ed n-1 che sono coprimi con n. In simboli: C (n) = {a : 1 £ a £ n-1 Ù MCD(a,n) = 1}, dove MCD(a,b) è il massimo comun divisore di a e b.
Per definizione j (n) è il numero degli elementi che stanno in C(n): j (n) = |C(n)|; la funzione j è detta funzione di Eulero.
Per esempio C(15) = {1, 2, 4, 7, 8, 11, 13, 14} e j (15) = 8.
Evidentemente se p è primo j (p) = p-1. Inoltre se MCD(a,b)=1 allora j (ab) = j (a)j (b).
Vale l'importante Teorema di Eulero:
Se a appartiene a C(n) allora:
aj (n) = 1 mod n
equivalentemente:
n divide ( aj (n) - 1)
In particolare se p è primo:
p divide (ap-1 - 1).
Il caso particolare di p primo, cioè ap-1 = 1 mod n viene detto Piccolo Teorema di Fermat, perché venne scoperto da Fermat, che però non lo dimostrò. La dimostrazione venne data da Eulero.
Per esempio:
n = 15, j (n) = 8, a = 11, 118 - 1 = 214358880 = 15 ΄ 14290592
p = 13, j (p) = 12, a = 2, 212 - 1 = 4095 = 13 ΄ 315
Inoltre si prova che dato qualsiasi a in C(n) esiste sempre un unico b in C(n) tale che
a* b = 1 (mod n)
b si dice inverso di a modulo n.
Vediamo due esempi:
per n = 15 si ha:
|
a |
1 |
2 |
4 |
7 |
8 |
11 |
13 |
14 |
|
inverso |
1 |
8 |
4 |
13 |
2 |
11 |
7 |
14 |
per n = 13 si ha:
|
a |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
inv. |
1 |
7 |
9 |
10 |
8 |
11 |
2 |
5 |
3 |
4 |
6 |
12 |
Questo è quanto ci occorre per la crittografia a chiave pubblica.
5 Crittografia a chiave pubblica
La crittografia a chiave pubblica è così strutturata:
Vi sono gli utenti: A, B, C,
Ogni utente dispone di una funzione di codifica EA, EB, EC, che è resa pubblica.
Ogni utente ha una funzione segreta di decodifica DA, DB, DC,
Un testo in chiaro T è diviso in blocchi; ogni blocco viene trasformato in un numero M che lo rappresenta esattamente. Il problema si riduce dunque a quello di inviare i numeri M.
Le funzioni EA, EB, EC, e le funzioni DA, DB, DC, sono calcolate in modo da soddisfare la relazione DB(EB(M)) = M per ogni possibile M; in altre parole la funzione di decodifica D è la inversa della funzione di codifica E.
Chi desidera inviare un messaggio M all'utente B, utilizza la funzione pubblica EB e invia a B il numero EB(M). L'utente B usa la sua funzione segreta DB e calcola DB(EB(M)) = M.
Le funzioni EA, EB, EC, sono molto particolari: vengono dette funzioni trappola a molla segreta. Come una trappola esse agiscono in una sola direzione: nessuno può calcolare M conoscendo EB(M), non si può tornare indietro, non si può calcolare la funzione inversa DB. Non servirebbero a nulla però se le DB fossero incomputabili in maniera assoluta; è qui che interviene la molla segreta: l'utente possiede una informazione segreta che gli permette di calcolare la DB.
Esistono funzioni così strane? Oggi se ne conoscono molte. Un esempio assai importante per la crittografia odierna è dato dal metodo RSA.
6 Il metodo RSA (Rivest, Shamir, Adleman)
L'utente A sceglie n = pq con p e q primi grandi distinti, p < q. L'aggettivo grande dipende dalla potenza di calcolo dell'avversario. Oggi p e q devono avere un centinaio di cifre.
Poi A sceglie e in C(j (n)) = C((p-1)(q-1)) e calcola il suo inverso d; sappiamo che d soddisfa alla:
ed = 1 mod j (n).
I numeri p, q, j (n) vengono cancellati.
I numeri e, n sono resi pubblici.
Il numero d è tenuto segreto.
I messaggi sono rappresentati da numeri M < p.
Sotto scriviamo la funzione trappola a molla segreta EA e la sua inversa DB.
EA(M) = Me mod n
DA(M) = Md mod n
La conoscenza segreta è data dai primi p e q senza i quali non è possibile calcolare d (l'inverso di e modulo j (n)). Infatti j (n) non si può calcolare senza conoscere i fattori di n. Si noti che questa conoscenza segreta è cancellata per sempre e non può essere recuperata.
Verifichiamo infine che vale davvero la relazione necessaria DB(EB(M)) = M per ogni possibile M.
Per definizione DA(EA(M)) = DA(Me mod n) = Med mod n.
Dal fatto che ed = 1 mod n segue che j (n) divide ed 1. Quindi ed - 1 = kj (n), e infine possiamo dire che ed = kj (n) + 1 per un certo intero k. Allora:
Med mod n = Mkj (n)+1 mod n = (per le usuali proprietà delle potenze)
(Mj (n))k Χ M mod n = 1k Χ M mod n = M mod n = M
Nell'ultima riga abbiamo usato il teorema di Eulero: Mj (n) = 1 mod n.
La sicurezza del sistema RSA (uno dei più sicuri attualmente) si fonda sulla differenza enorme esistente tra due tempi di calcolo. Mentre esistono algoritmi che permettono in pochi secondi di trovare numeri primi di centinaia di cifre, e quindi è facile e veloce costruire la funzione trappola E, occorrerebbero secoli di calcolo su migliaia di computers ultraveloci per fattorizzare un intero grande. Del resto se il malintenzionato non riesce a trovare i fattori di n, non può trovare il numero segreto d che è l'unico che permette di costruire la funzione di decodifica D.
BIBLIOGRAFIA