E’ la scienza che studia la possibilità che un soggetto

Teoria dei numeri e Crittografia: lezione del 11 gennaio 2012 Crittografia.

E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un utente B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che per un soggetto C (intruso), che sia in grado di intercettare il messaggio, sia “difficile” conoscere le informazioni in esso contenuto.

In un sistema crittografico il messaggio originale (detto messaggio in chiaro) prima di essere trasmesso dal mittente A viene opportunamente modificato (la cosiddetta cifratura che trasforma il messaggio in chiaro in un messaggio cifrato); è il messaggio cifrato che viene trasmesso lungo il canale di comunicazione: quando il destinatario B lo riceve, ne effettua una opportuna modifica (la cosiddetta decifratura) che fornisce come risultato il messaggio in chiaro originale.

Anticamente il concetto di ”messaggio” era ristretto ad un messaggio di tipo “testuale”, cioè costituito da caratteri alfabetici.

Al giorno d’oggi ogni messaggio è in forma digitale (cioè numerica) e può contenere informazioni di vario tipo (file immagine, file audio-video etc…): la codifica numerica avviene attraverso dei codici internazionali (per esempio il codice ASCII) e il messaggio viene trasmesso in base 2 come una successione di bits 0,1.

Il messaggio viene spesso suddiviso in blocchi di bits (di lunghezza prefissata) quindi in termini numerici un messaggio diventa un numero intero non negativo di grandezza limitata (cioè <N dove N>0 è un intero prefissato).

Se vogliamo formalizzare la struttura di un sistema crittografico, servendoci della teoria degli insiemi, possiamo dire che si possono individuare:

- un insieme finito X dei messaggi in chiaro, spesso coincidente con l’insieme I

={0,1,…,N-1}

dei numeri interi non negativi <N (dove N>0 è un intero prefissato)

- un insieme finito Y dei messaggi cifrati spesso coincidente con l’insieme I

={0,1,…,M-1} dei numeri interi non negativi <M (dove M>0 è un intero prefissato). Nei casi concreti talvolta è N=M, dunque X=I

=Y=I

- una funzione di cifratura f : X → Y (che trasforma ogni messaggio in chiaro x ∈ ^{X in un} messaggio cifrato y=f(x) ∈ X) e una funzione di decifratura g : Y → X (che ritrasforma il messaggio cifrato y=f(x) ∈ Y nel messaggio in chiaro x=g(y) ∈ ^X).

Dal punto di vista insiemistico, la proprietà della funzione di decifratura g si traduce nel fatto che per ogni messaggio in chiaro x ∈ X si deve avere g(f(x))=x, dunque la composizione g •••• ^{f deve} coincidere con la funzione identica i

dell’insieme X.

Questo implica che la funzione di cifratura f è iniettiva (e dunque biunivoca se X=Y) perché se f(x

)=f(x

) allora g(f(x

))=g(f(x

)) dunque x

=x

.

La funzione di cifratura e la funzione di decifratura si servono in generale di elementi ausiliari (detti rispettivamente chiavi di cifratura e chiavi di decifratura) che sono utilizzati nella trasformazione di un messaggio in chiaro in messaggio cifrato e nella ritrasformazione di un messaggio cifrato nel messaggio in chiaro da cui esso proveniva.

Un principio empirico è il seguente: la sicurezza di un sistema crittografico risiede nella segretezza delle chiavi e non in quella delle funzioni di cifratura e decifratura.

Il sistema crittografico di Cesare.

E’ un sistema crittografico molto semplice (ma poco sicuro) che pare fosse utilizzato da Cesare per

le sue corrispondenze personali.

Supponiamo che l’insieme dei messaggi in chiaro X e quello dei messaggi cifrati Y coincidano entrambi con I

={0,1,2,……,20} e che tali numeri si facciano corrispondere alle 21 lettere dell’alfabeto italiano (A=0, B=1, C=2,….., Z=20)

Fissiamo una lettera dell’alfabeto e il suo corrispondente numerico a (dunque 1 ≤ ^a ≤ 20 ): tale valore numerico a è la chiave di cifratura, detta offset. Definiamo la funzione di cifratura f : X → ^{Y nel} modo seguente: disponiamo in modo “circolare” gli elementi di X (in modo che dopo il valore 21 vi sia di nuovo il valore 0 e così via), e per ogni messaggio in chiaro x ∈ X definiamo il messaggio cifrato y=f(x)=(x+a)mod21: in pratica ogni lettera viene cifrata spostandola di un numero di posizioni uguale all’offset a lungo l’alfabeto in verso orario.

Per esempio se la chiave di cifratura è a=3 e se x=4 (valore numerico della lettera E) allora f(4)=7, valore numerico della lettera H (appunto la lettera che si trova 3 posizioni più avanti rispetto alla lettera E).

La funzione di decifratura g : Y → X utilizza la stessa chiave a, ed è ovviamente definita nel modo seguente: per ogni y ∈ Y si ha g(y)=(y-a)mod21 (corrisponde ad uno spostamento di a posizioni in verso antiorario).

Ovviamente non è opportuno scegliere l’offset a=0 , che rende coincidenti messaggio in chiaro e messaggio cifrato.

Per rendere operativamente più semplice la cifratura, il mittente scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso destra di a posizioni (se a è la chiave di cifratura) sempre pensando ad una struttura “circolare”: sotto ogni lettera si trova la sua cifratura.

Per esempio nel caso a=3:

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 questo caso, per cifrare il testo in chiaro “ATTACCATESUBITO” applicando ad ogni lettera del testo la funzione f di cifratura, si ottiene il seguente testo cifrato (da trasmettere lungo il canale di comunicazione):

“DZZDFFDZHVAENZR”

Analogamente, per rendere operativamente più semplice la decifratura, il destinatario scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso sinistra di a posizioni: sotto ogni lettera si trova la sua decifratura.

Nel nostro caso (sempre con a=3):

A B C D E F G H I L M N O P Q R S T U V Z U V Z A B C D E F G H I L M N O P Q R S T

Decifrando il testo ricevuto “DZZDFFDZHVAENZR” (lettera per lettera) si riottiene il testo originale “ATTACCATESUBITO”.

Nel sistema crittografico di Cesare la chiave di cifratura coincide con quella di decifratura, e ovviamente deve essere concordata in anticipo fra il mittente e il destinatario. Il sistema di Cesare è poco sicuro: l’intruso che intercetti il messaggio cifrato, potrebbe cercare di risalire al messaggio in chiaro con il metodo della “forza bruta”, provando a decifrare il messaggio con tutte le possibili chiavi (che sono in tutto 20) fino ad ottenere un messaggio che abbia un senso compiuto.

Il sistema crittografico di Cesare fa parte dei cosiddetti sistemi a sostituzione monoalfabetica

(ogni lettera dell’alfabeto viene cifrata con un’altra lettera, ma sempre con la stessa lettera, anche se

la lettera originale appare in diverse posizioni nel testo in chiaro).

Nell’esempio precedente la lettera A, che si trova in 2 posizioni diverse nel messaggio in chiaro

“ATTACCATESUBITO” viene cifrata sempre con la lettera D.

Per rendere più difficile l’uso della “forza bruta” da parte dell’intruso, si può utilizzare una variante del sistema di Cesare, in cui il numero di chiavi è molto più grande.

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione σ dei numeri 0,1,2,….,20 (o equivalentemente delle lettere dell’alfabeto A,B,.…,Z) e si definisce la funzione di cifratura f : X → Y nel modo seguente: per ogni messaggio in chiaro x ∈ X si pone f(x)= σ ^(x).

Dal punto di vista operativo, il mittente scrive, sotto la successione delle lettere dell’alfabeto, le lettere nella permutazione fissata: sotto ogni lettera si trova la sua cifratura.

Per esempio se la permutazione fissata come chiave é BFGTURSEIOLMZNCUDATHP:

A B C D E F G H I L M N O P Q R S T U V Z B F G T U R S E I O L M Z N C U D A Q H P la cifratura del testo in chiaro “ATTACCATESUBITO” è “BAABGGBAUDQFIAZ”.

La funzione di decifratura g : Y → X si ottiene viceversa associando ad ogni lettera (considerata nella permutazione) la lettera che si trova sopra di essa (formalmente g(y)= σ

(y) per ogni y ∈ ^{Y ).}

Anche in questo caso la chiave di cifratura (la permutazione fissata) coincide con quella di decifratura, e deve essere concordata in anticipo fra il mittente e il destinatario: ma il numero di chiavi possibili coincide con 21! (il numero delle possibili permutazioni di 21 lettere), e poiché tale numero è molto grande (ha 20 cifre in base 10) il metodo della “forza bruta” non è praticamente applicabile dall’intruso che cerca di “rompere” il sistema crittografico.

Anche tale sistema crittografico, come quello di Cesare, è un sistema a sostituzione monoalfabetica (ogni lettera dell’alfabeto viene cifrata con un’altra lettera, ma sempre con la stessa lettera, anche se la lettera originale appare in diverse posizioni nel testo in chiaro).

Tutti i sistemi a sostituzione monoalfabetica sono però vulnerabili ad un altro tipo di attacco, quello basato sull’analisi statistica delle frequenze delle lettere .

Se un testo è scritto in una certa lingua (e soprattutto se esso è molto lungo) il numero di presenze (in percentuale) di ogni lettera dell’alfabeto nel testo è in genere molto vicino ad un valore statistico che si conosce a priori.

Per esempio, nella lingua italiana, le vocali a, e sono le lettere statisticamente più frequenti (quasi il 12% di frequenza); seguono la vocale i (poco oltre l’11%), la vocale o (circa il 10%), la consonante n (circa il 7%) e così via, fino alle consonanti q, z (le meno frequenti, con un valore di circa 0,5%).

Poiché ogni lettera del testo in chiaro ha sempre la stessa cifratura (indipendentemente dalla sua posizione), esaminando la frequenza delle lettere nel testo cifrato si potrebbe, con una certa approssimazione, fare delle ipotesi sulle lettere di cui esse sono la cifratura (soprattutto se il testo è molto lungo) e poi, attraverso altre considerazioni “linguistiche” (ogni lingua ha certi “vincoli” fra le lettere di una parola) sarebbe possibile, anche per tentativi, risalire al testo in chiaro.

Il sistema crittografico di Vigenère

La vulnerabilità alle analisi statistiche dei sistemi crittografici a sostituzione monoalfabetica risiede

dunque nel fatto che ogni lettera dell’alfabeto viene cifrata sempre con la stessa lettera,

indipendentemente dalla sua posizione nel testo.

Il sistema crittografico di Vigenère (introdotto nel ‘500) pone rimedio a questo difetto, perché è un sistema a sostituzione polialfabetica, nel senso che ogni lettera dell’alfabeto viene cifrata con una lettera che però dipende dalla posizione della lettera stessa nel testo in chiaro.

Il sistema di Vigenère è una evoluzione del sistema di Cesare: nel sistema di Cesare si fissa come chiave (offset) una lettera dell’alfabeto con valore numerico a; ogni lettera x del testo in chiaro é cifrata con la lettera che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario (pensando sempre all’alfabeto con un struttura circolare).

Invece nel sistema di Vigenère la chiave è una parola di lunghezza k>0 sull’alfabeto A,B,…,Z:

poiché k è in genere minore del numero di lettere del testo in chiaro, per effettuare la cifratura si ripete più volte la chiave sotto il testo in chiaro fino a “coprire” tutte le lettere di quest’ultimo (anche in eccesso), e poi si cifra ogni lettera del testo in chiaro con il sistema di Cesare utilizzando come chiave la lettera della parola chiave che si trova sotto di essa.

Per esempio, se il testo in chiaro è “APPUNTAMENTOALLETRE”, e se la chiave è la parola

“SEGRETO” :

A P P U N T A M E N T O A L L E T R E S E G R E T O S E G R E T O S E G R E T O S T V O R P O F I T N S T D E I C L I

Nella prima riga vi è il testo in chiaro, nella seconda la chiave ripetuta più volte (fino a coprire il testo in chiaro), nella terza il testo cifrato: per esempio si cifra la seconda lettera P con chiave E (offset =4), ottenendo la cifratura T; si cifra la terza lettera P con chiave G (offset =16), ottenendo la cifratura V e così via. Come si vede una lettera del testo in chiaro può essere cifrata in modo diverso a secondo della sua posizione: la P in seconda posizione viene cifrata con T; la P in terza posizione viene cifrata con V. Per semplificare la cifratura, si può utilizzare una matrice 21x21, composta da alfabeti ordinati e shiftati verso destra: la prima riga contiene le lettere dell’alfabeto nel loro ordine naturale; la seconda riga contiene le lettere shiftate di 1 posto verso destra (sempre pensando ad una struttura circolare); la terza riga contiene le lettere shiftate di 2 posti verso destra etc…. (vedere sotto la matrice).Per cifrare una lettera del testo in chiaro basta individuare, nella prima riga, la colonna in cui si trova la lettera stessa, poi individuare, nella prima colonna, la riga in cui si trova la lettera che ha il ruolo della chiave (offset): la cifratura sarà la lettera che si trova all’incrocio fra la colonna e la riga individuate. Per esempio per cifrare la lettera T con la chiave R: si individua nella prima riga la colonna della T, si individua nella prima colonna la riga della R e si ottiene la cifratura N all’incrocio.

A B C D E F G H I L M N O P Q R S T U V Z B C D E F G H I L M N O P Q R S T U V Z A C D E F G H I L M N O P Q R S T U V Z A B D E F G H I L M N O P Q R S T U V Z A B C E F G H I L M N O P Q R S T U V Z A B C D F G H I L M N O P Q R S T U V Z A B C D E G H I L M N O P Q R S T U V Z A B C D E F H I L M N O P Q R S T U V Z A B C D E F G I L M N O P Q R S T U V Z A B C D E F G H L M N O P Q R S T U V Z A B C D E F G H I M N O P Q R S T U V Z A B C D E F G H I L N O P Q R S T U V Z A B C D E F G H I L M O P Q R S T U V Z A B C D E F G H I L M N P Q R S T U V Z A B C D E F G H I L M N O Q R S T U V Z A B C D E F G H I L M N O P R S T U V Z A B C D E F G H I L M N O P Q S T U V Z A B C D E F G H I L M N O P Q R T U V Z A B C D E F G H I L M N O P Q R S U V Z A B C D E F G H I L M N O P Q R S T V Z A B C D E F G H I L M N O P Q R S T U Z A B C D E F G H I L M N O P Q R S T U V

Per decifrare si usa un metodo simile, ma costruendo una matrice in cui le righe contengono alfabeti shiftati verso sinistra.

Il fatto che nel sistema di Vigenére una lettera del testo in chiaro possa essere cifrata in modo diverso a secondo della sua posizione sembrava porre il sistema al riparo da attacchi basati sull’analisi statistica delle frequenze delle lettere, e per circa 3 secoli tale sistema fu praticamente inviolabile.

Però nell’800 vi furono dei tentativi di attacco di tale sistema che ebbero successo, e che si basano sulle considerazioni che seguono.

Se una lettera nel testo in chiaro si ripete 2 volte ad una distanza che è multipla della lunghezza k della parola chiave, allora la sua cifratura (in queste posizioni) è la stessa (perché la lettera chiave sottostante è la stessa): nell’esempio precedente (in cui la chiave é la parola “SEGRETO” di lunghezza k=7) nella scrittura della parola chiave ripetuta sotto il testo in chiaro la lettera chiave S si ritrova in posizione 1, 8, 15, 22 etc.. (cioè in posizioni a distanza multipla di 7); analogamente la lettera chiave G si ritrova in posizione 3, 10, 17, 24 etc.. (sempre in posizioni a distanza uguale a multipli di 7) e così via. Una lettera del testo in chiaro che si trovasse ripetuta, per esempio, nelle posizioni 1 e 15, sarebbe cifrata con la stessa lettera, dunque ritroveremmo la stessa lettera nel testo cifrato nelle posizioni 1 e 15.

Si potrebbe allora (soprattutto con un testo in chiaro molto lungo, in cui la ripetizione delle lettere è più frequente) esaminare quali lettere del testo cifrato si ripetono e a quale distanza: un divisore di una di tali distanze potrebbe essere la lunghezza k della chiave. A questo punto, sperimentando con uno di tali valori possibili della lunghezza della chiave, si potrebbero tentare metodi statistici sulla frequenza delle lettere: per esempio se si sperimenta con il valore possibile k=7, si esaminano nel testo cifrato le lettere in posizione 1, 8, 15, 22 etc…. (che sono tutte cifrate con la stessa lettera chiave), e a tali lettere si applicano i metodi statistici; poi si esaminano le lettere in posizione 2, 9, 16, 23, etc…. (anche queste tutte cifrate con il sistema di Cesare con la stessa lettera chiave) ed anche a tali lettere si applicano i metodi statistici e così via.

Una volta individuate alcune lettere del testo in chiaro e le loro cifrature, si può con facilità risalire alla conoscenza di alcune delle lettere della chiave.

Inoltre poiché spesso la parola chiave ha un senso compiuto (può essere anche un’intera frase di senso compiuto molto lunga) una volta trovate alcune sue lettere si possono fare ipotesi sulle altre lettere, sempre utilizzando considerazioni basate sui vincoli che la lingua del testo in chiaro pone nella struttura delle parole.

Il sistema crittografico OTP (One Time Pad)

Ai difetti riscontrati nel sistema crittografico di Vigenére si può ovviare nel seguente modo: poiché uno dei punti deboli è la ripetizione della parola chiave sotto il testo in chiaro, si può usare una parola chiave lunga almeno quanto tutto il testo; tale chiave deve essere inoltre usata per cifrare un solo messaggio e poi sostituita con un’altra (usarla per cifrare più messaggi porterebbe alla stessa vulnerabilità dovuta alla sua ripetizione sotto il testo); inoltre poiché un altro punto debole del sistema è il fatto che la chiave (se di senso compiuto) soddisfa certe vincoli legati alla lingua del testo, la parola chiave dovrebbe essere formata da lettere casuali.

Un sistema crittografico di questo tipo (sistema “One Time Pad”=”Blocco Monouso”) è chiamato

“sistema cifrario perfetto” e la sua assoluta sicurezza è comprovata da una dimostrazione matematica formale (dovuta a Shannon).

Ovviamente è un sistema abbastanza “scomodo” perché le chiavi sono molto lunghe, ed ognuna è

usata per cifrare un solo messaggio: i 2 utenti (mittente e destinatario) devono concordare su un

insieme di moltissime chiavi, tutte di grande lunghezza.

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, in cui la chiave di cifratura e la chiave di decifratura sono diverse.

In entrambi i casi però vi è 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….).

Una efficiente soluzione a questo problema fu trovata negli anni ’70 con la nascita dei sistemi crittografici a chiave pubblica.

Sistemi crittografici a chiave pubblica.

Si tratta di sistemi crittografici, proposti in modo solo teorico nel 1976 da Diffie e Hellman, in cui la chiave di cifratura è pubblica (quindi nota a tutti) mentre la chiave di decifratura è segreta (conosciuta solo dal destinatario) ma in modo che (a partire dalla conoscenza della chiave di cifratura) il calcolo della chiave di decifratura abbia complessità “alta”, per esempio superiore alla polinomiale (quindi sia “computazionalmente difficile” la decifratura del messaggio in chiaro, se non si conosce a priori la chiave di decifratura): in genere il calcolo della chiave di decifratura è equivalente ad un problema matematico per la cui soluzione non esistano ancora algoritmi di complessità non superiore alla polinomiale.

Spesso però la certezza che il calcolo della chiave di decifratura abbia complessità non superiore alla polinomiale può essere messa in discussione dalla nascita di algoritmi sempre più sofisticati, che minano la sicurezza di questi tipi di sistemi.

La prima realizzazione concreta di un sistema crittografico a chiave pubblica avvenne nel 1978, con il sistema RSA, proposto da Rivest, Shamir e Adleman, basato sul problema matematico della

“fattorizzazione in primi”..

Esso si basa sul seguente risultato.

Teorema RSA.

Sia n un numero naturale prodotto di 2 primi distinti p,q e sia t un naturale tale che t ≡ ^{1 (mod} ϕ ^(n)), dove ϕ (n) è la funzione di Eulero.

Allora per ogni intero x ≥ 0 si ha: x

≡ x (mod n).

Dimostrazione:

Se x=0 la tesi è banale, quindi sia x>0.

Calcolando la funzione di Eulero con le usuali formule si ha ϕ ⁽ⁿ⁾⁼ ϕ (pq)=(p-1)(q-1): per ipotesi si ha t-1=k(p-1)(q-1) con k intero.

Dimostriamo dapprima che p è divisore della differenza x

-x.

Se p è divisore di x, ciò è banale perché p sarà divisore anche di x

.

Quindi supponiamo p non divisore di x: per il Piccolo Teorema di Fermat si ha:

x

≡ 1 (mod p)

Elevando ambo i membri all’esponente k(q-1) e moltiplicando per x si ottiene:

x

=x

≡ x (mod p) quindi p è divisore della differenza x

-x.

Con ragionamenti analoghi si ha che q è divisore della differenza x

-x.

Essendo p,q primi distinti, essi sono coprimi, dunque anche il loro prodotto n=pq è divisore della differenza x

-x, e si ha la tesi.

Possiamo allora implementare il sistema crittografico RSA nel modo seguente.

Il soggetto destinatario B sceglie 2 numeri primi distinti p, q e calcola il loro prodotto n=pq, rendendo pubblico n, ma tenendo segreti i fattori primi p, q.

Per trovare p, q il destinatario B può testare numeri naturali random di s cifre (con s abbastanza

“grande”) con test di primalità probabilistici (come quello di Rabin-Miller) fino a trovare una coppia di numeri p, q che può “dichiarare” primi con una bassissima probabilità di errore.

Lo spazio dei messaggi in chiaro (e anche di quelli cifrati) sarà I

={0,1,….,n-1}.

Il soggetto B sceglie anche un naturale c coprimo con ϕ (n): per fare ciò B può per esempio scegliere un numero primo c con c>p,q (se per assurdo fosse c non coprimo con ϕ (n), sarebbe c divisore del numero ϕ (n)=(p-1)(q-1), dunque c divisore di p-1 oppure di q-1, cioè c<p oppure c<q, contraddizione).

Il soggetto B trova poi un numero naturale d tale che [d]=[c]

nel gruppo moltiplicativo Z

*: per il calcolo di d si può usare, come sappiamo, l’algoritmo Euclideo delle divisioni successive, applicato alla coppia di numeri c, ϕ (n) entrambi noti a B.

La chiave di cifratura (resa pubblica) è c; la chiave di decifratura (tenuta segreta da B) è d.

L’algoritmo di cifratura f: I

→

I

è definito ponendo f(x)=x

modn : il calcolo della cifratura del messaggio in chiaro x da parte del mittente A può essere effettuata in modo efficiente con l’algoritmo dell’esponenziazione modulare, noti i valori x, c, n.

L’algoritmo di decifratura g: I

→

I

è definito ponendo g(y)=y

modn : la decifratura del messaggio cifrato y=f(x) da parte del destinatario B può essere effettuata anch’essa in modo efficiente con l’algoritmo dell’esponenziazione modulare, noti i valori x, d, n.

Applicando il Teorema RSA si ha, ponendo t=cd (notare che da [c][d]=[1] in Z

* segue in effetti t=cd ≡ ^{1 (mod} ϕ ^(n)):

g(f(x))= x

modn ≡ x (mod n)

e quindi g(f(x))=x (perché g(f(x)),x ∈ ^I

, dunque 0≤ g(f(x)),x≤ n-1). Ciò dimostra che decifrando il messaggio cifrato si ritorna effettivamente al messaggio in chiaro x.

Notare che per calcolare la chiave di decifratura d, è necessario conoscere ϕ (n)=(p-1)(q-1), e ciò è equivalente a conoscere i fattori primi p,q di n (per alcune considerazioni fatte in una lezione precedente): il problema è quindi quello di fattorizzare in primi il numero n, e per un generico valore n non è a tutt’oggi noto un algoritmo di fattorizzazione di complessità polinomiale.

Ciò non toglie che per particolari valori di n, alcuni algoritmi di fattorizzazione riescano in modo efficiente a calcolare i fattori primi p,q di n, e quindi a rompere il sistema RSA.

Il soggetto B deve quindi scegliere con cura i primi p,q: non troppo piccoli (algoritmo ingenuo di fattorizzazione), non troppo vicini a n (algoritmo di Fermat); inoltre p-1, q-1 non devono avere fattori primi piccoli (algoritmo p-1 di Pollard) e così via.

Notizie storiche: Nella sfida lanciata nel 1977 dagli inventori del sistema RSA, relativa alla fattorizzazione del numero RSA-129, di 129 cifre in base 10, tale numero (prodotto di 2 primi di 64 e 65 cifre) era alla base di un sistema RSA con cui era cifrato il messaggio testuale “the magic words are squeamish ossifrage”.

L’esponente c per la cifratura (reso pubblico insieme al valore di n) era c=9007.

La decifratura ebbe successo nel 1994, con l’uso dell’algoritmo del crivello quadratico (per il calcolo dei due fattori primi di n) su più di 600 pc che lavorarono in parallelo per 8 mesi.

Esempio.

Diamo un esempio di cifratura e decifratura mediante il sistema RSA.

Sia n=2047, prodotto dei primi p=23, q=89, di modo che ϕ ⁽ⁿ⁾⁼ ϕ (pq)=(p-1)(q-1)=1936.

Il primo c=97 (che è >p,q) è dunque certamente coprimo con ϕ ^(n).

Con l’algoritmo Euclideo si calcola l’inverso [d] di [c] in Z

*, ottenendo d=1457 .

Se per esempio il messaggio in chiaro è x=10, il messaggio cifrato (ottenuto con l’esponenziazione modulare) è y=10

mod2047=1607.

Per decifrarlo si calcola 1607

mod2047=10, riottenendo il messaggio in chiaro.

Il problema del logaritmo discreto.

Si tratta di un altro problema a tutt’oggi di alta complessità di calcolo.

Dal Teorema di Gauss sappiamo che, se n è un numero primo, il gruppo moltiplicativo:

Z

* = {[0], [1], ……., [n-1]}

é un gruppo ciclico (di cardinalità n-1) generato da un opportuno elemento α =[a] di periodo n-1 (a è quindi una radice primitiva modulo n): notare che esiste un algoritmo (che non descriveremo in dettaglio), dovuto allo stesso Gauss, che permette di calcolare una radice primitiva modulo n, se n è primo.

Fissato n primo, e fissata una radice primitiva a modulo n (quindi un intero a compreso fra 1 e n-1 tale che α =[a] sia generatore del gruppo ciclico Z

* ) osserviamo che, essendo [a] di periodo n-1, le sue potenze distinte (che esauriscono tutte le classi in Z

*) sono [a], [a]

,….., [a]

.

Dunque per ogni [x]∈Z

* esiste un (unico) esponente k, con 1≤ k ≤ n-1 tale che [x]=[a]

.

In altri termini per ogni numero naturale x con 1≤ x ≤ n-1 esiste un (unico) numero naturale k, con 1≤ k ≤ n-1 tale che x=a

modn: tale k è detto logaritmo discreto di x in base a modulo n (ricordiamo che a è un radice primitiva modulo il numero primo n).

Esempio.

Se n=13, a=11 (si verifica che tale a è una radice primitiva dell’unità modulo 13), fissato x=3, il logaritmo discreto di 3 in base 11 è 4, in quanto [11]

=[3], dunque 3=11

mod13.

Come per il problema della fattorizzazione in primi, anche per il problema del logaritmo discreto non esiste a tutt’oggi un algoritmo di complessità polinomiale che, fissato il numero primo n e la radice primitiva a modulo n, e dato in input un intero x con 1≤ x ≤ n-1, calcoli il logaritmo discreto di x in base a modulo n.

Vedremo che il problema del logaritmo discreto può essere usato anche per concordare “a distanza”

fra due soggetti (in modo sicuro) la chiave di un sistema crittografico a chiave simmetrica.

Scambio di chiavi di Diffie-Hellmann.

In un sistema crittografico a chiave simmetrica, il problema è quello di concordare la chiave comune (di cifratura e decifratura) fra i soggetti A (mittente) e B (destinatario).

Una possibilità è ovviamente quella che A decida il valore della chiave e la trasmetta a B mediante sistemi a chiave pubblica (RSA etc.).

Ma il problema del logaritmo discreto permette di risolvere il problema anche in altro modo, come osservato da Diffie e Hellman, senza che vi sia nessuna comunicazione “pericolosa” fra A e B relativa alla chiave da concordare.

I soggetti A,B concordano su un numero primo n e su una radice primitiva a modulo n (che possono essere resi pubblici senza problemi).

Inoltre A sceglie un naturale x con 1≤ x ≤ n-1 (tenendolo segreto) e analogamente B sceglie un naturale y con 1≤ y ≤ n-1 (tenendolo segreto).

Infine A spedisce a B il valore z=a

modn, mentre B spedisce ad A il valore w= a

modn.

Notiamo che in questa fase un eventuale intruso C che intercetti il valore z o il valore w, non è in grado “facilmente” di calcolare x oppure y (che sono i rispettivi logaritmi discreti in base a modulo n).

A questo punto A calcola il valore w

modn, mentre B calcola il valore z

modn: tali valori (compresi fra 1 ed n-1) coincidono con a

modn (perché sono entrambi congrui al valore a

modn, quindi coincidono perché compresi fra 1 ed n-1), e possono essere quindi scelti da A e B come chiave concordata per un sistema crittografico a chiave pubblica.

Vedremo ora come il problema del logaritmo discreto può essere usato per la costruzione di un sistema crittografico a chiave pubblica.

Sistema crittografico di ElGamal.

E’ un sistema crittografico a chiave pubblica basato sul problema del logaritmo discreto.

Il destinatario B fissa un numero primo n, e calcola una radice primitiva a modulo n (per esempio con l’algoritmo di Gauss), rendendo pubblici tali dati.

Poi sceglie un numero intero h, con 1≤h≤n-1, e calcola (per esempio con l’esponenziazione modulare) il valore b=a

modn: quindi b ≡ ^a

(mod n), ossia h è il logaritmo discreto in base a del numero b modulo n.

In questo sistema crittografico lo spazio dei messaggi in chiaro è I

-{0}={1,2,….,n-1}.

La chiave di cifratura è b, che viene resa pubblica; la chiave di decifratura è h, tenuta segreta.

L’algoritmo di cifratura è definito nel modo seguente: il mittente A fissa a piacere un intero k , con 1≤k≤n-1 (senza la necessità di comunicarlo a B) e se x∈{1,2,….,n-1} è il messaggio in chiaro, calcola (utilizzando per esempio l’esponenziazione modulare) i due numeri:

γ ^=a

modn δ ^=(xb

)modn (quindi 1 ≤ γ ^, δ ≤ n-1, γ≡ ^a

^{(mod n),} δ≡ ^(xb

) (mod n)).

Il messaggio cifrato è la coppia ( γ ^, δ ): quindi lo spazio dei messaggi cifrati è il prodotto cartesiano I

-{0}x I

-{0}, e la funzione di cifratura f: I

-{0} → I

-{0}x I

-{0} è definita da:

f(x) = ( γ ^, δ ^{) = (a}

^{modn, (xb}

^)modn)

Descriviamo la funzione di decifratura g: I

-{0}x I

-{0}→ I

-{0} tale che g(f(x))=x per ogni messaggio in chiaro x. Sia y=f(x)=( γ ^, δ ) il messaggio cifrato.

Sia poi [ β ] l’inverso di [ γ ^{] in Z}

* (il valore β si calcola a partire da γ ,n con l’algoritmo Euclideo):

quindi βγ ≡1 (mod n).

Si calcola infine, con l’esponenziazione modulare, il valore σ=(δβ

)modn (quindi σ≡δβ

(mod n)) e si definisce la funzione di decifratura ponendo g(y)= σ ^.

Notiamo che la chiave di decifratura (tenuta segreta da B) è h, cioè il logaritmo discreto in base a del numero b modulo n, ed è computazionalmente “difficile” da calcolare.

Resta da verificare però che g(f(x))=x.

Infatti si hanno le seguenti congruenze modulo n:

g(f(x)) ≡ σ ≡ δβ

≡ ^xb

β

≡ ^x(a

⁾

β

≡ ^x(a

⁾

β

≡ ^x γ

β

≡ ^x( γβ ⁾

≡ x (mod n) da cui σ =x (perché sono numeri congrui modulo n, e compresi fra 1 e n-1).

Il vantaggio del sistema di ElGamal rispetto al sistema RSA è che basta la scelta di un solo primo come base del sistema, ma lo svantaggio è che il messaggio cifrato ha mediamente lunghezza doppia del messaggio in chiaro.

Esempio.

Sia n=997 (primo). Con l’algoritmo di Gauss si trova una radice primitiva modulo n, per esempio a=7 (si verifica infatti che [a] ha periodo 996=n-1 nel gruppo Z

*). Il destinatario B rende noti n, a.

Supponiamo che la chiave di decifratura (segreta) scelta da B sia h=105.

Il destinatario B calcola b=7

mod997=989, e rende pubblica tale chiave di cifratura.

Supponiamo che il messaggio in chiaro che il mittente A deve spedire sia x=813.

Per cifrare il messaggio x, il mittente A sceglie un intero intero k , con 1≤k≤n-1 (per esempio k=87), poi calcola γ ⁼⁷

mod997=849, δ =(813⋅989

)mod997=19, e spedisce come messaggio cifrato la coppia ( γ ^, δ )=(849,19).

Il destinatario B, per decifrare il messaggio, calcola l’inverso [ β ^{] di [} γ ^{] in Z}

*, ottenendo β ^{=869, e}

calcola poi σ =(19⋅869

)modn=813, riottenendo il messaggio in chiaro.