Matematica Discreta
Lezione del giorno 6 maggio 2010 Il problema dello scambio delle chiavi.
I sistemi crittografici fino ad ora illustrati (più o meno sicuri) sono sistemi a chiave simmetrica, nel senso che la chiave di cifratura e la chiave di decifratura coincidono.
Esistono anche sistemi sistemi a chiave asimmetrica (un esempio sarà il sistema RSA che esamineremo in seguito), in cui la chiave di cifratura e la chiave di decifratura sono diverse.
In entrambi i casi (chiave simmetrica o asimmetrica) vi è però un grande problema: quello dello scambio delle chiavi.
I 2 soggetti (mittente e destinatario) devono concordare sulle chiavi di cifratura e decifratura da usare, e (soprattutto se i 2 soggetti sono fisicamente distanti) la trasmissione di tali chiavi da un soggetto all’altro può comportare problemi di sicurezza (la trasmissione delle chiavi lungo un canale di comunicazione può essere intercettata da un intruso: è un circolo vizioso….).
Vedremo in seguito come tale problema sia stato recentemente risolto con l’introduzione dei sistemi crittografici a chiave pubblica.
La crittografia moderna
Attualmente, con l’avvento dei canali digitali, un messaggio testuale viene trasmesso lungo un canale di informazione in formato numerico: ogni carattere è trasformato in un numero intero non negativo (rappresentato in genere in base 2, servendosi delle cifre binarie 0,1) mediante delle codifiche concordate a livello internazionale.
Una delle codifiche più usate è il codice ASCII (American Standard Code for Information Interchange) che trasforma ogni carattere alfanumerico (ed anche vari caratteri di interpunzione e comandi di formattazione) in un byte di 8 bits binari 0,1, corrispondente ad un numero binario compreso fra 0=(00000000)2 e 255=(11111111)2 .
Per esempio nel codice ASCII la codifica numerica della lettera A maiuscola è 65=(01000001)2, della lettera B maiuscola è 66=(01000010)2, e così via proseguendo fino alla codifica numerica della lettera Z maiuscola che è 90=(01011010)2; le codifiche numeriche delle lettere minuscole vanno da 97=(01100001)2 a 122=(01111010)2, lo spazio è codificato con 32=(00100000)2 ; le cifre decimali 0,1,2,….,9 hanno codifiche numeriche da 48=(00110000)2 a 57=(00111001)2 etc…
Una volta codificati i singoli caratteri del testo, si trasmettono in successione le loro codifiche, formando una successione di bits 0,1.
Per esempio la frase “Vediamoci alle 3” codificata nel codice ASCII darebbe origine al seguente messaggio di 128 bits:
01010110011001010110010001101001011000010110110101101111011000110110100100100000 011000010110110001101100011001010010000000110011
(ogni gruppo di 8 bits è la codifica di un carattere, ed essendo 16 il numero di caratteri del testo, compresi gli spazi, si ha un totale di 816=128 bits).
Ovviamente oggi il significato di “messaggio” non è più limitato al caso di un messaggio testuale:
può essere un qualunque file che contiene informazioni (un’immagine, un file sonoro,un file video etc…): anche in questo caso l’informazione viene codificata con numeri rappresentati in base 2, e trasmessa come successione di bits 0,1.
Indipendentemente dall’informazione contenuta, definiremo dunque messaggio una qualunque successione finita di bits binari 0,1.
La successione di bits che forma il messaggio è in genere suddivisa in “blocchi” più piccoli (sui quali singolarmente opera l’eventuale cifratura o decifratura): spesso di fissa un intero N>0 tale che il valore numerico rappresentato da ogni singolo blocco sia <N.
Nella crittografia moderna si definirà dunque “messaggio” un qualunque numero intero x0 che sia minore di un intero positivo prefissato.
Con tale convenzione la struttura di un sistema crittografico sarà formata da:
- l’insieme dei messaggi in chiaro X={0,1,2,….,N}, dove N è un intero >0 fissato - l’insieme dei messaggi cifrati Y={0,1,2,….,M}, dove M è un intero >0 fissato
- una funzione di cifratura f : X Y, e una funzione di decifratura g : Y X tali che g(f(x))=x per ogni messaggio in chiaro xX
Spesso si avrà X=Y (dunque anche N=M).
Il vantaggio di tale schematizzazione è anche quello di permettere di definire le funzioni f, g servendosi di algoritmi algebrici (visto che f,g agiscono su numeri interi).
Sistemi crittografici a chiave pubblica.
Abbiamo visto che il problema dello scambio delle chiavi è un grave problema di tutti i sistemi crittografici.
Una efficiente soluzione a questo problema fu trovata negli anni ’70 con la nascita dei sistemi crittografici a chiave pubblica.
Si tratta di sistemi crittografici in cui le chiavi di cifratura e decifratura sono diverse; mentre la chiave di cifratura è pubblica (quindi nota a tutti), la chiave di decifratura è segreta e conosciuta solo dal soggetto destinatario, ma con la condizione che, a partire dalla conoscenza della chiave di cifratura, il calcolo della chiave di decifratura (da parte di un intruso) abbia “alta” complessità di calcolo (quindi sia “lungo” il tempo necessario all’intruso per la decifratura del messaggio).
In generale il calcolo della chiave di decifratura (a partire dalla conoscenza della chiave di cifratura) dovrebbe essere equivalente alla soluzione di un opportuno problema matematico per il quale non sia conosciuto un algoritmo di soluzione “veloce” (tutto ciò può essere precisato formalmente con la teoria della complessità computazionale, che non affronteremo in questo corso).
Questa fu l’idea di Diffie ed Hellman (1976): essi però non riuscirono a trovare un problema matematico per la cui soluzione non si fossero trovati algoritmi “veloci” e che nello stesso tempo potesse essere utilizzato per costruire un sistema crittografico a chiave pubblica.
Poi, nel 1977, Rivest, Shamir e Adleman (del MIT) proposero un sistema crittografico a chiave pubblica, che dalle loro iniziali fu chiamato sistema RSA, basato sul problema matematico della
“fattorizzazione di un intero >1 in prodotto di numeri primi”, problema per cui attualmente non esistono algoritmi “veloci” di soluzione, soprattutto nel caso di numeri molto grandi.
Il sistema RSA si basa sul Teorema RSA che in seguito dimostreremo.
Premettiamo alcuni risultati aritmetici relativi alla teoria delle congruenze.
Consideriamo la relazione di congruenza modulo n definita nell’insieme Z dei numeri interi relativi (dove n è un intero >1 fissato, il modulo della congruenza).
Sappiamo che tale relazione di equivalenza determina n classi di equivalenza distinte in Z (le classi di congruenza modulo n) e precisamente le seguenti:
[0], [1], ……., [n-1]
Comunque preso un intero relativo aZ esiste dunque un unico intero x con 0xn-1 tale che [x]=[a] cioè tale che xa (mod n). Tale unico intero x è detto riduzione di a modulo n ed è indicato con il simbolo x=amodn.
Da risultati precedentemente dimostrati conosciamo anche un algoritmo per calcolare tale intero x (se ovviamente a non è già un intero compreso fra 0 ed n-1 nel qual caso x=a):
1) se a>0: x=amodn=r dove r é il resto della divisione di a per il modulo n (per esempio 14mod3=2) 2) se a<0: si divide –a per il modulo n ottenendo resto r;
se r=0 allora x=amodn=0 (per esempio (-15)mod3=0);
se r>0 allora x=amodn=m-r (per esempio (-17)mod3=3-2=1)
