Siano a,n due numeri naturali, e supponiamo che n sia un numero primo ed n non sia divisore di a.

Matematica Discreta

Lezione dei giorni 3,10 e 17 maggio 2012

Una conseguenza del Teorema di Eulero-Fermat è la seguente:

Corollario (Piccolo Teorema di Fermat).

Siano a,n due numeri naturali, e supponiamo che n sia un numero primo ed n non sia divisore di a.

Allora si ha:

a

1 (mod n).

Dimostrazione:

Notiamo che i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n, e la possibilità mcd(a,n)=n è da escludere essendo n non divisore di a per ipotesi).

Poiché (n)=n-1 (perché n è primo) la tesi segue immediatamente dal Teorema di Eulero-Fermat.

Esponenziazione modulare.

Illustreremo ora l’algoritmo della esponenziazione modulare che permette di ottenere il seguente obiettivo: fissati 3 numeri naturali x,k,n, con n>1, calcoliamo in modo efficiente la riduzione modulo n della potenza x

:

x

modn

(ricordiamo che per definizione è l’unico numero intero t tale che tx

(mod n) e tale che 0tn-1).

Sia s il numero di cifre binarie dell’esponente k; la rappresentazione di k in base 2 è allora della forma:

k=a

2

+ a

2

+….+a

2

+a

2

(con ogni cifra a

=0,1) Costruiamo una successione y

,y

,...,y

di numeri naturali ponendo:

y

=1; per ogni i>0 y

= (y _{i  1} ² x ^a

) ^modn

Per esempio: y

= (y ₀ ² x ^a

) ^{modn, y}

⁼ (y ₁ ² x ^a

) ^{modn, y}

⁼ (y ₂ ² x ^a

) modn etc...

Ogni elemento della successione y

con i>0 si calcola dal precedente con due prodotti (il quadrato di y

e il prodotto del risultato per _x ^a

: osserviamo che quest’ultima potenza è = x oppure =1 perché l’esponente è la cifra binaria a

è =0,1), e con una riduzione modulo n (che rende il risultato

<n): questo permette di coinvolgere nei calcoli numeri non troppo “grandi” .

Dimostriamo che l’algoritmo fornisce appunto il valore della riduzione x

modn, e precisamente che si ottiene y

= x

modn (quindi la riduzione cercata è semplicemente l’ultimo termine della successione y

,y

,...,y

costruita dall’algoritmo).

Infatti si ha:

y

= (y ₀ ² x ^a

) modn da cui y

 (y ₀ ² x ^a

) ^{(mod n)}

y

= (y ₁ ² x ^a

) modn da cui y

 (y ₁ ² x ^a

) (mod n) e dunque y

 ^{(a 2}

^a

²

⁾

-

x

^ (mod n) y

= (y ₂ ² x ^a

) modn da cui y

 (y ₂ ² x ^a

) (mod n) e dunque y

 ^{(a 2 a 2}

^a

²

⁾

2 - s 2 1 -

x

^{ } (mod n)

etc..

Così procedendo alla fine si ottiene la congruenza:

y

 ^{(a 2 a 2 . a 2}

^a

²

⁾

- 2 s - 1 s - 1 s -

x

^{    } = x

(mod n)

Ma per costruzione ogni y

si calcola con una riduzione modulo n, quindi in particolare 0y

n-1, e allora, per definizione di riduzione modulo n, la precedente congruenza implica che y

è proprio la riduzione di x

modulo n, come si voleva:

y

= x

modn.

Esempio. Come esempio di applicazione dell’algoritmo dell’esponenziazione modulare, sviluppiamo il calcolo della riduzione 33084

mod83411 (coinvolta nella simulazione del sistema RSA visto nell’esempio precedente).

Si rappresenta l’esponente d=16565 in base 2:

16565 = (100000010110101)

con 15 cifre binarie a

=1, a

=a

=a

=a

=a

=a

=0, a

=1

a

=0, a

=a

=1, a

=0, a

=1, a

=0

a

=1.

Si costruisce la successione y

, y

,….., y

: y

= 1

y

= y

y

mod83411 = 33084 y

= y

y

mod83411 = 31914 y

= y

y

mod83411 = 55086 y

= y

y

mod83411 = 58627 y

= y

y

mod83411 = 8052 y

= y

y

mod83411 = 24357 y

= y

y

mod83411 = 44417 y

= y

y

mod83411 = 12012 y

= y

y

mod83411 = 70525 y

= y

y

mod83411 = 81908 y

= y

y

mod83411 = 47057 y

= y

y

mod83411 = 49432 y

= y

y

mod83411 = 34276 y

= y

y

mod83411 = 241 y

= y

y

mod83411 = 12597

Il valore finale é appunto y

= 12597 = 33084

mod83411 (ed é quello indicato come risultato nell’esempio precedente).

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.

Poiché il messaggio può sempre essere suddiviso in “blocchi” (che poi il destinatario dovrà

“incollare” per riottenere l’intera informazione originale) potremo anche in certi casi identificare il

concetto di messaggio con il singolo carattere alfabetico: la cifratura e la decifratura opereranno in

questo caso sulle singole lettere del testo.

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, un insieme finito Y dei messaggi cifrati (in molti casi concreti gli insiemi X,Y saranno uguali), una funzione di cifratura f : X  Y (che trasforma ogni messaggio in chiaro xX in un messaggio cifrato y=f(x)X) e in 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.

Vedremo dagli esempi che la funzione di cifratura e la funzione di decifratura si servono 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.

Il sistema crittografico di Cesare.

E’ un sistema crittografico molto semplice (ma poco sicuro) che pare fosse utilizzato dagli antichi Romani.

Supponiamo che l’insieme dei messaggi in chiaro X e quello dei messaggi cifrati Y coincidano entrambi con l’insieme delle 21 lettere dell’alfabeto italiano:

X = Y = {A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U,V,Z}

Diamo un valore numerico intero compreso fra 0 e 20 alle lettere: A=0, B=1, C=2,…., Z=20.

Fissiamo una lettera dell’alfabeto (sarà la chiave di cifratura del nostro sistema crittografico) e calcoliamo il suo valore numerico a con 0a20 (tale valore numerico è detto offset); definiamo poi la funzione di cifratura f : X  Y nel modo seguente: disponiamo in modo “circolare” gli elementi di X (in modo che la lettera successiva alla Z sia la A), e per ogni messaggio in chiaro xX (dunque x è una delle 21 lettere dell’alfabeto) definiamo il messaggio cifrato y=f(x) uguale a quella lettera che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario.

Per esempio se la chiave di cifratura è la lettera D con valore numerico a=3, e se x=E allora f(E)=H (la lettera H si trova 3 posizioni più avanti rispetto alla lettera E). Ovviamente non ha molto senso scegliere come chiave di cifratura la lettera A con offset a=0, in quanto la cifratura di ogni lettera la lascerebbe invariata.

La funzione di decifratura g : Y  X utilizza una chiave di decifratura uguale a quella di cifratura, ed è definita nel modo seguente: dato yY (quindi y è una delle 21 lettere dell’alfabeto) si definisce g(y) uguale a quella lettera che si trova (a partire dalla lettera y) spostandosi di a posizioni lungo l’alfabeto in verso antiorario.

E’ ovvio che, se y=g(x) è la cifratura del messaggio in chiaro x, g(y) coincide con il messaggio in chiaro originale x.

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 è l’offset cioè il valore numerico della chiave di cifratura) sempre pensando ad una struttura “circolare”: sotto ogni lettera x si trova la sua cifratura f(x).

Per esempio nel caso a=3 (chiave di cifratura è la lettera D):

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 y si trova la sua decifratura g(y).

Nell’esempio precedente (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”.

Come abbiamo visto, 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 21) 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 messaggio in chiaro).

Nell’esempio precedente la lettera A, pur trovandosi 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.

Anche in questo sistema crittografico l’insieme X dei messaggi in chiaro e l’insieme Y dei messaggi cifrati coincidono con l’insieme delle lettere dell’alfabeto:

X = Y = {A,B,C,D,E,…..,U,V,Z}

Come chiave di cifratura (e anche di decifratura) si fissa una permutazione delle lettere dell’alfabeto (quindi un qualunque modo di disporre ordinatamente le 21 lettere) e si definisce la funzione di cifratura f : X  Y nel modo seguente: per ogni messaggio in chiaro xX (dunque x è una delle 21 lettere dell’alfabeto) si definisce il messaggio cifrato y=f(x) uguale a quella lettera che si trova, nella permutazione fissata, nella stessa posizione che ha la lettera x nella successione alfabetica.

Dal punto di vista operativo, il mittente scrive, sotto la successione delle lettere dell’alfabeto, le lettere della permutazione (fissata come chiave di cifratura): sotto ogni lettera x si trova la sua cifratura f(x).

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 V 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 y (considerata

nella permutazione) la lettera g(y) che si trova sopra di essa.

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 (per avere un’idea della sua grandezza si consideri che ha 20 cifre in base 10) il metodo della “forza bruta” non è praticamente applicabile dall’intruso che cerca di

“rompere” il sistema crittografico (il tempo di calcolo sarebbe troppo lungo).

Si pensi che anche con utilizzando al giorno d’oggi un computer, se esso riuscisse ad esaminare ognuna della possibili 21! chiavi in 1 miliardesimo di secondo, il tempo necessario per esaminarle tutte sarebbe superiore a 10

secondi (corrispondenti ad oltre 3000 anni).

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.

Ecco un grafico dei valori percentuali delle frequenze delle lettere della lingua italiana (in ordine decrescente):

Per esempio 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%) 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) pose 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: ricordiamo che nel sistema di Cesare si fissa come chiave una lettera dell’alfabeto con valore numerico a (offset), con 0 a20; ogni lettera x del testo in chiaro é cifrata con la lettera y 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).

Nel sistema di Vigenère la chiave di cifratura (ed anche di decifratura) è una successione di k lettere dell’alfabeto, quindi, nel linguaggio del calcolo combinatorio, la chiave è una parola di lunghezza k sull’alfabeto delle lettere A,B,C,…Z (spesso è una parola di senso compiuto per ricordarla più facilmente).

In questo sistema l’insieme X dei messaggi in chiaro e l’insieme Y dei messaggi cifrati coincidono con l’insieme di tutte le parole di lunghezza k sull’alfabeto composto dalle lettere A,B,C,….,Z e da un carattere “speciale” # considerato come ultima lettera dopo la Z.

Il testo da spedire viene suddiviso in “blocchi” ognuno formato da k lettere: l’ultimo blocco (se ha lunghezza <k) viene completato con caratteri #.

La cifratura viene dunque fatta (in un modo che ora descriveremo) su ogni singolo blocco (considerato come elemento dell’insieme X dei messaggi in chiaro) ottenendo come messaggio cifrato ancora un blocco di k lettere : il destinatario riceve i blocchi, decifra ogni blocco e “incolla”

i blocchi ottenuti (cancellando eventuali caratteri speciali # nell’ultimo blocco) riottenendo il messaggio originale.

La funzione di cifratura f è definita nel modo seguente: se a

a

,….a

è il blocco da cifrare, e se b

b

…..b

è la chiave, la cifratura si ottiene cifrando ogni lettera a

del blocco con il sistema di Cesare utilizzando come chiave la lettera b

(i valori numerici dell’offset in questo caso variano da 0, attribuito alla lettera A, fino a 21, attribuito al carattere speciale #).

Dal punto di vista operativo, per facilitare la cifratura, si possono scrivere le lettere della chiave b

b

…..b

sotto quelle del blocco da cifrare a

a

,….a

, cifrando ogni singola lettera a

(con il sistema di Cesare) utilizzando come chiave la lettera b

sottostante: la lettera a

sarà trasformata in quella che si trova (in senso orario) in una posizione a distanza uguale al valore numerico della lettera b

. Per esempio, supponiamo che il testo il testo in chiaro sia “APPUNTAMENTOALLETRE”, e che la chiave sia la parola “SEGRETO” :

Poiché la parola chiave ha lunghezza k=7, suddividiamo il testo in blocchi di 7 lettere, completando l’ultimo blocco con i caratteri #:

A P P U N T A

M E N T O A L

L E T R E # #

Otteniamo 3 blocchi, ognuno da considerare come elemento dell’insieme X dei messaggi in chiaro.

Per effettuare la cifratura del primo blocco, scriviamo sotto le sue lettere le 7 lettere della chiave

“SEGRETO” e cifriamo ogni lettera del blocco con il sistema di Cesare utilizzando come chiave la lettera sottostante:

A P P U N T A S E G R E T O S T V N R O O

Nella terza riga vi è la cifratura del blocco: per esempio si cifra la seconda lettera P del blocco con il sistema di Cesare con chiave E (offset =4), ottenendo la cifratura T; si cifra la terza lettera P del blocco 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 invece cifrata con V.

Nello stesso modo si procede per cifrare il secondo blocco:

M E N T O A L

S E G R E T O

E I T M S T #

e il terzo blocco:

L E T R E # # S E G R E T O

D I B I I S N

La funzione g di decifratura ovviamente opera in modo inverso, utilizzando la decifratura del sistema di Cesare sulle singole lettere dei blocchi cifrati: si riottengono così i 3 blocchi originari, che, incollati e con l’eliminazione dei caratteri # nell’ultimo blocco, danno il testo in chiaro originario.

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)

Alle debolezze riscontrate nel sistema crittografico di Vigenére si può ovviare nel seguente modo:

poiché uno dei punti deboli è l’uso ripetuto della parola chiave per decifrare i vari “blocchi” del 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 per decifrare i vari blocchi); 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” e in pratica non utilizzabile 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 (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)

e 255=(11111111)

.

Per esempio nel codice ASCII la codifica numerica della lettera A maiuscola è 65=(01000001)

, della lettera B maiuscola è 66=(01000010)

, e così via proseguendo fino alla codifica numerica della lettera Z maiuscola che è 90=(01011010)

; le codifiche numeriche delle lettere minuscole vanno da 97=(01100001)

a 122=(01111010)

, lo spazio è codificato con 32=(00100000)

; le cifre decimali 0,1,2,….,9 hanno codifiche numeriche da 48=(00110000)

a 57=(00111001)

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 816=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 x0 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 xX

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 aZ esiste dunque un unico intero x con 0xn-1 tale che [x]=[a] cioè tale che xa (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)

Dimostriamo ora il Teorema su cui si basa il sistema crittografico a chiave pubblica RSA:

Teorema RSA.

Sia n un numero naturale prodotto di 2 primi distinti p,q e sia t un numero 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, cioè sia x un numero naturale.

Calcolando la funzione di Eulero con la nota formula (dimostrata nella prima parte del corso) si ha

(n)= (pq)=(p-1)(q-1): per ipotesi si ha t-1=k(p-1)(q-1) con k intero, cioè t=1+k(p-1)(q-1) Dimostriamo dapprima che p è divisore della differenza x

-x.

Se p è divisore di x, ciò è banale perché sarà x=ph con h intero, da cui x

-x = p

h

-ph = p(p

h

-h).

Supponiamo allora p non divisore di x; per il Piccolo Teorema di Fermat si ha:

x

1 (mod p)

Ricordando che la congruenza è compatibile con il prodotto, possiamo moltiplicare membro a membro tale congruenza per sé stessa k(q-1) volte ottenendo:

x

1 (mod p)

e moltiplicando ancora per la congruenza x x (mod p) (sempre per la compatibilità della congruenza con il prodotto) otteniamo:

x

x (mod p) ossia: x

x (mod p)

quindi p è divisore della differenza x

-x.

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

-x.

Per un risultato dimostrato nella prima parte del corso (prima del Teorema di Fattorizzazione Unica), essendo p,q primi distinti, anche il loro prodotto n=pq è divisore di x

-x, e si ottiene dunque la tesi x

x (mod n).

Illustriamo ora come si implementa il sistema crittografico RSA.

Ricordiamo che esso è un sistema a chiave pubblica, in cui la chiave di cifratura è pubblica (conosciuta da tutti) e la chiave di decifratura è segreta (conosciuta solo dal soggetto destinatario che deve decifrare i messaggi): per un intruso il calcolo della chiave di decifratura (conoscendo quello di cifratura) deve essere “difficile” cioè comportare lunghi tempi di calcolo.

Il soggetto destinatario B sceglie 2 numeri primi distinti p,q (in genere molto grandi, anche con centinaia di cifre) e calcola il loro prodotto n=pq, rendendo pubblico n, ma tenendo segreti i fattori primi p,q .

L’insieme dei messaggi in chiaro X (e anche di quelli cifrati Y) é l’insieme {0,1,….,n-1}.

Il soggetto B sceglie poi a suo piacere un numero naturale c coprimo con (n), cioè tale che mcd(c,(n))=1: sappiamo che nel monoide Z

delle classi di congruenza modulo (n) (rispetto al prodotto di classi) la classe [c] è simmetrizzabile.

Il soggetto B calcola il simmetrico di [c] nel monoide Z

: per il calcolo di tale simmetrico si può usare, come sappiamo, l’algoritmo Euclideo delle divisioni successive (algoritmo “veloce” che non comporta lunghi tempi di calcolo anche per numeri molto grandi).

In pratica B trova con l’algoritmo Euclideo delle divisioni successive i coefficienti interi relativi x,y tal che 1=mcd(c, (n))=cx+(n)y: il simmetrico di [c] nel monoide Z

è la classe [x].

Il soggetto B calcola poi d=xmod(n), cioè la riduzione di x modulo (n) (quindi d è l’unico intero tale che 0d(n)-1 e tale che [d]=[x] in Z

): ovviamente essendo [d]=[x] anche [d] è simmetrico di [c] nel monoide Z

. Poiché [0] in Z

non è simmetrizzabile, siamo certi che d>0, quindi anche d è un numero naturale.

La chiave di cifratura (resa pubblica) è il numero naturale c; la chiave di decifratura (tenuta segreta dal destinatario B) è il numero naturale d.

La funzione di cifratura f : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo f(x)=x

modn (è la riduzione modulo n del numero x

).

La funzione di cifratura g : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo g(y)=y

modn (è la riduzione modulo n del numero y

)

Dobbiamo però verificare che per ogni messaggio in chiaro x (quindi per ogni x numero intero compreso fra 0 ed n-1) si abbia g(f(x))=x.

Osserviamo che (essendo [d] simmetrico di [c] nel monoide Z

) si ha [c][d]=[cd]=[1] in Z

quindi:

cd 1 (mod (n)).

Posto t=cd, possiamo allora applicare il Teorema RSA ottenendo:

x

= x

 x (mod n).

Ma posto y=f(x)=x

modn segue (per la definizione della riduzione modulo n):

y  x

(mod n).

Analogamente posto z=g(f(x))=g(y)=y

modn segue:

z  y

(mod n).

Moltiplicando membro a membro la congruenza y  x

(mod n) per sé stessa d volte si ha (per la compatibilità della congruenza con il prodotto):

y

 x

(mod n)

e per la proprietà transitiva della relazione di congruenza:

z  x

(mod n)

ma x

= x

 x (mod n) e di nuovo per la proprietà transitiva:

z  x (mod n)

Ma z,x sono entrambi numeri appartenenti all’insieme {0,1,…,n-1}, dunque, se sono congrui modulo n, sono certamente uguali fra loro (ricordiamo che le classi di congruenza modulo n con rappresentante compreso fra 0,1,…,n-1 sono tutte distinte), e si conclude che:

x = z = g(f(x)).

E’ dunque vero che decifrando la cifratura del messaggio in chiaro x, si riottiene x.

Esempio di cifratura con il sistema RSA. Supponiamo che il testo da trasmettere sia la seguente indicazione di una rotta da seguire

“15GRADISUD”.

Codifichiamo nel codice ASCII i singoli caratteri del testo:

Carattere Valore numerico In binario

1 49 (00110001)

5 53 (00110101)

G 71 (01000111)

R 82 (01010010)

A 65 (01000001)

D 68 (01000100)

I 73 (01001001)

S 83 (01010011)

U 85 (01010101)

D 68 (01000100)

Il testo in chiaro (come successione di 80 bits 0,1) è allora:

00110001001101010100011101010010010000010100010001001001010100110101010101000100 Il destinatario sceglie 2 numeri primi distinti, per esempio p=239, q=349 (segreti) e rende pubblico il loro prodotto n=83411 (nel nostro esempio i numeri coinvolti sono ovviamente troppo piccoli per rendere “sicuro” il sistema). I blocchi da cifrare (e spedire) devono avere valore numerico <n;:

poiché il più grande numero naturale esprimile con 16 bits in base 2 è 2

-1=65535, possiamo suddividere la successione di 80 bits in 5 blocchi di 16 bits ciascuno.

Il primo blocco di 16 bits da cifrare è dunque 0011000100110101 (valore numerico x=12597).

Il destinatario calcola la funzione di Eulero (n)=(p-1)(q-1)=82824 e sceglie come chiave di cifratura (rendendola pubblica) per esempio il numero naturale c=5 (resa pubblica); notiamo che c è coprimo con (n)=82824 come dimostra l’algoritmo Euclideo (con 3 divisioni):

82824 = 516564+4 (q

=16564, r

=4) 5 = 41+1 (q

=1, r

=1)

4 = 14+0 (q

=4, r

=0) quindi mcd(82824, 5)=1

(si può anche ottenere la stessa conclusione notando che 5, 82824 non hanno in comune divisori tranne 1).

Il mittente cifra il primo blocco di 16 bits di valore numerico x=12597 con la funzione di cifratura e

la chiave di cifratura c=5:

y = f(x) = x

modn = 12597

mod83411 = 317201802686979902757mod83411 = 33084 (il numero 33084 é il resto della divisione di 12597

per 83411).

Poi il mittente rappresenta in base 2 il blocco cifrato y (sempre utilizzando 16 bits):

33084 = (1000000100111100)

e spedisce i 16 bits lungo il canale di trasmissione (facendo lo stesso con gli altri 4 blocchi di 16 bits: li cifra e li spedisce di seguito al primo).

Il destinatario riceve la successione i 5 blocchi di 16 bits ciascuno.

Vedremo poi come il destinatario opera la decifratura di ogni singolo blocco per riottenere (incollando i blocchi decifrati) il messaggio originario.

Continuiamo a sviluppare l’esempio di cifratura e decifratura con il sistema RSA.

Il primo blocco cifrato di 16 bits ricevuto dal destinatario è 1000000100111100 (di valore numerico y=33084); a tale blocco il destinatario deve applicare la funzione di decifratura.

Per fare ciò il destinatario deve calcolare prima la chiave di decifratura d secondo la procedura indicata nel sistema RSA.

Abbiamo detto che la chiave di cifratura scelta era c=5, numero naturale coprimo con (n)=82824 come dimostra l’algoritmo Euclideo (con 3 divisioni):

82824 = 516564+4 (q

=16564, r

=4) 5 = 41+1 (q

=1, r

=1)

4 = 14+0 (q

=4, r

=0) quindi mcd(82824, 5)=1

Per calcolare la chiave di decifratura d, il destinatario calcola il simmetrico di [c] in Z

= Z

, calcolando i coefficienti interi relativi che permettono di rappresentare 1 come combinazione lineare di 82824, 5 con l’algoritmo Euclideo esteso.

In pratica calcola i termini delle successioni s

, t

: s

=1, s

=0, s

=s

-s

q

=1, s

=s

-s

q

= -1

t

=0, t

=1, t

=t

-t

q

= -16564, t

=t

-t

q

= 16565 ottenendo i coefficienti s

= -1, t

=16565 tali che 1 = 82824(-1)+516565

Dunque [16565] è il simmetrico di [5] in Z

= Z

.

La chiave di decifratura d (tenuta segreta dal destinatario) è la riduzione modulo (n) di tale valore:

d=16565mod82824=16565

(in questo caso la riduzione coincide con il numero stesso perché esso è già compreso nell’intervallo [0,(n)-1]).

Il destinatario può dunque applicare la funzione di decifratura g al primo blocco (di valore numerico y=33084) e facendo i calcoli ottiene come previsto il valore numerico del primo blocco in chiaro x:

g(y) = y

modn = 33084

mod83411 = 12597 = x

(teoricamente il valore 12597 si dovrebbe ottenere come resto della divisione di 33084

per 83411).

Infine il destinatario rappresenta in binario il blocco x (sempre utilizzando 16 bits):

12597 = (0011000100110101)

e (dopo avere decifrato gli altri 4 blocchi) dispone in successione i bits ottenendo il messaggio in chiaro da 80 bits (che attraverso il codice ASCII si decodificano nelle lettere del testo

“15GRADISUD”).

Nell’esempio precedente si può notare il seguente problema : il soggetto destinatario che vuole

decifrare il messaggio, si trova a dovere calcolare 33084

mod83411. Teoricamente questo valore

si dovrebbe ottenere considerando il resto della divisione di 33084

per 83411: in effetti i numeri

coinvolti nel calcolo sono molto grandi (il numero 33084

ha più di 80000 cifre in base 10) ed il

nostro esempio è basato su numeri primi p,q di soli 3 cifre, mentre nella realtà i sistemi RSA sono

basati su numeri con centinaia di cifre, e ciò renderebbe “astronomici” i valori da manipolare.

Abbiamo visto però in precedenza che esiste un un algoritmo efficiente per risolvere tale problema:

l’esponenziazione modulare RSA-129 challenge.

La sicurezza del sistema RSA si basa sulla difficoltà di trovare i fattori primi di un numero naturale molto “grande”: ovviamente però la valutazione di tale sicurezza deve essere fatta con cura, tenendo conto dell’evoluzione degli algoritmi e dei mezzi informatici, per evitare valutazioni errate e troppo ottimistiche.

Possiamo a tale riguardo ricordare il cosiddetto “RSA-129 challenge”: una 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 p,q di 64 e 65 cifre):

(1143816257578888676692357799761466120102182967212423625625618429357069352457338 978 30597123563958705058989075147599290026879543541) =

(3490529510847650949147849619903898133417764638493387843990820577) * (32769132993266709549961988190834461413177642967992942539798288533)

era alla base di un sistema RSA con cui era cifrato il messaggio testuale “the magic words are squeamish ossifrage” (letteralmente “le parole magiche sono schizzinoso avvoltoio”).

La chiave c di cifratura (resa pubblica insieme al valore di n) era c=9007.

Le previsioni, basate sulla efficienza degli algoritmi di fattorizzazione dell’epoca, erano che fossero necessari “milioni di anni” per calcolare i fattori primi p,q, e quindi la chiave di decifratura d, con la quale decifrare il messaggio.

Ma lo sviluppo di nuovi algoritmi (in particolare del cosiddetto “crivello quadratico” di Pomerance) e il lavoro in parallelo di più di 1000 computers messi a disposizione da utenti Internet, permise, dopo 8 mesi di lavoro, di calcolare nel 1994 la seguente chiave di decifratura (con 129 cifre):

d=106698614368578024442868771328920154780709906633937862801226224496631063125911 774470873340168597462306553968544513277109053606095

e decifrare quindi il messaggio.

Il problema della firma digitale nei sistemi a chiave pubblica.

In un sistema crittografico a chiave pubblica, la chiave di cifratura è pubblica, dunque un intruso C potrebbe spedire al destinatario B un messaggio cifrato firmandolo come se il mittente fosse A, ossia

“fingendo” che A sia l’autore del messaggio: è il cosiddetto “problema della firma digitale”.

Vediamo una possibile soluzione a tale problema, nel sistema RSA.

Firma digitale nel sistema RSA.

E’ necessario che sia A che B (mittente e destinatario) implementino un proprio sistema RSA.

Il soggetto A sceglierà un intero n

=p

q

prodotto di 2 primi distinti, una chiave di cifratura c

e una di decifratura d

, con funzione di cifratura definita da:

f

(x)= x ^c

modn (per ogni x{0,1,……,n

-1}

e funzione di decifratura g

definita da:

g

(y)= y

modn (per ogni y{0,1,……,n

-1}

Analoghe scelte da parte del soggetto B: n

=p

q

, c

, d

f

(x)= x modn (per ogni x{0,1,……,n ^c

-1}

g

(y)= y

modn (per ogni y{0,1,……,n

-1}

Primo caso: supponiamo che sia n

≤n

.

Insieme con il messaggio cifrato, il mittente A manda una sua “firma digitale” (per esempio una frase del tipo “Firmato: Mario Rossi”) ma affinché B sia certo che la firma è proprio quella del soggetto A, il mittente A suddivide la “firma digitale” in blocchi codificati con valore numerico <n

; se x è uno di tali blocchi, A applica ad x l’algoritmo di decifratura g

(“come se” x fosse un messaggio cifrato da decifrare) ottenendo y=g

(x){0,1,……,n

-1}Í{0,1,……,n

-1}, e poi applica l’algoritmo di cifratura f

ottenendo z=f

(y)=f

(g

(x)) {0,1,……,n

-1}, e infine spedisce z al destinatario B.

Notiamo che il valore y=g

(x) può essere calcolato solo da A, in quanto la chiave di decifratura d

è conosciuta solo da A; il valore z=f

(y) può essere calcolato da chiunque perché la chiave di cifratura c

è pubblica.

Il destinatario B, ricevendo z, applica la decifratura g

(ricordiamo che B è in possesso della chiave segreta d

di decifratura) ottenendo g

(z)=g

(f

(y))=y, poi applica la cifratura f

(B è in possesso come tutti della chiave pubblica c

di cifratura) ottenendo f

(y)=f

(g

(x))=g

(f

(x))=x (si è sfruttata la proprietà f

g

=g

f

, ovviamente valida in quanto x ^c

^d

modn= x ^d

^c

modn).

Alla fine B legge la “firma digitale”in chiaro (dopo avere riunito i blocchi x), e può essere certo dell’identità del mittente A.

Secondo caso: sia invece n

<n

.

In questo caso {0,1,……,n

-1}Í{0,1,……,n

-1}: il mittente A suddivide la sua “firma digitale” in

blocchi codificati con valore numerico <n

, e (se x è uno di tali blocchi) spedisce z=g

(f

(x)) al

destinatario B, il quale calcolando g

(f

(x))=x riottiene la firma digitale in chiaro (dopo avere riunito

i blocchi x), e può essere certo dell’identità del mittente A.