Analisi della sicurezza nelle moderne tecniche crittografiche tesina

Analisi della sicurezza nelle moderne tecniche

crittografiche ITIS “E. Mattei” Sondrio

Esame di Stato 2015

Alunno: Riva Davide

Classe V, sezione E

Indice

1. Premessa storica 2

2. Considerazioni iniziali 4

3. La crittografia asimmetrica 5

4. Algoritmo di fattorizzazione 7

5. I sistemi paralleli 8

6. Struttura del software e benchmarking 11

7. Ciclo di vita e modelli di sviluppo del software 13

8. L’open source e gli open data 14

9 Bibliografia 16

1

1. Premessa storica

Da sempre l’uomo ha ricercato mezzi per poter comunicare a distanza con

la maggior segretezza possibile, principalmente in periodo di guerra

quando il nascondere le informazioni al nemico era di vitale importanza.

Emblema dei metodi utilizzati

nell’antichità è il cifrario di

Cesare (ideato dall’omonimo

imperatore di Roma vissuto nel

primo secolo a.C.): esso consiste

nel sostituire ogni lettera nel

testo originario con quella che la

segue di tre posti nell’alfabeto

(vedi esempio a fianco).

Numerosi furono i metodi di

cifratura utilizzati, ma non si fecero significativi passi avanti nell’ambito della

crittoanalisi sino al XIX secolo: infatti i cifrari erano molto semplici e si

basavano sull’idea che solo il mittente e il destinatario potessero conoscere

la chiave e che essa fosse unica sia per cifrare che per decifrare.

Le cose cambiarono durante la

Seconda guerra mondiale (1939-1945);

i tedeschi infatti utilizzarono la

macchina Enigma, uno strumento

meccanico che era in grado di generare

dieci milioni di miliardi di chiavi,

rendendo di fatto impossibile la

decifratura delle trasmissioni con i

mezzi disponibili all’epoca. Inoltre la

chiave veniva cambiata

quotidianamente, in modo che se una

delle macchine fosse caduta sotto

mano nemica essi avrebbero potuto

decifrare i messaggi scambiati solo fino

allo scoccare della mezzanotte.

Fintanto che questo metodo rimaneva

inviolabile, la Germania poteva

continuare i suoi progetti di egemonia.

Gli Alleati però, grazie al lavoro del

matematico britannico Alan Turing,

realizzarono Colossus, una macchina in

grado di decifrare le trasmissioni dei

nazisti; essa fu uno tra i primi calcolatori realizzati e gettò le basi delle

moderne tecniche di crittoanalisi. Grazie a questi strumenti divenne infatti

2

possibile eseguire calcoli matematici in tempi ridottissimi: sul mercato con

una spesa massima di 100 euro sono oggi disponibili macchine in grado di

effettuare 100 mila milioni di operazioni in virgola mobile in un secondo

(come Parallella).

La crittografia tornò nuovamente in auge durante la Guerra fredda nella

seconda metà del XX secolo, quando divenne fondamentale per le due

superpotenze che si erano create (USA e URSS) mantenere il massimo

livello di segretezza: in questo contesto nacque l’OTP (One-Time Pad), un

meccanismo che se usato correttamente rendeva i dati cifrati inviolabili. Ma

gli enormi problemi, soprattutto legati al fatto che la chiave era lunga tanto

quanto il messaggio da cifrare e che essa stessa doveva essere comunicata

hanno reso necessario lo sviluppo di nuovi metodi, tra i quali la crittografia

asimmetrica. Con questo metodo mittente e destinatario posseggono due

chiavi usate rispettivamente per cifrare e decifrare, rendendo inutile il

tentativo d’intercettare la chiave scambiata che non potrà quindi essere

utilizzata per decodificare i messaggi analizzati.

Ci si rese inoltre conto che non era tanto la segretezza che rendeva sicuro

un metodo di cifratura, quanto la robustezza della chiave. Si cominciò così a

rendere pubblicamente disponibili gli algoritmi anche fuori dal campo

militare; a oggi gli utilizzi sono molteplici: dall’autenticazione nei sistemi di

pagamento a una semplice chiamata tutti noi ogni giorno ci troviamo a

usarli senza rendercene conto.

Alan Turing Nato il 23 giugno 1912 Turing fu un abile

matematico, logico e crittoanalista, nonché un

pioniere dell’informatica. Definì per la prima volta il

concetto di “algoritmo” e teorizzò un modello

matematico (la macchina di Turing) che permise la

nascita dei computer. Grazie alle sue conoscenze

nell’ambito della crittoanalisi durante la Seconda

guerra mondiale lavorò per il governo brittannico

per il quale decriptò le comunicazioni militari che i

nazisti si scambiavano.

Morì suicida il 7 giugno 1954, probabilmente a

causa delle accuse di omossessualità (all’epoca

considerata un crimine) che nel 1952 lo costrinsero

ad accettare la castrazione chimica per evitare la

prigione. 3

2. Considerazioni iniziali

Nella nostra epoca i sistemi di cifratura sono utilizzati da chiunque (cittadini,

aziende, stati) e per qualsiasi scopo (dalla semplice connessione al proprio

modem Internet, alle transazioni bancarie sino alla cifratura di documenti

sensibili di una nazione). Sono inoltre nate numerose aziende relative a

questo ambito, prima fra tutte RSA Security che, fra i suoi prodotti,

annovera anche l’omonimo metodo di crittografia asimmetrica.

Gli algoritmi sviluppati diventano sempre più complessi e le chiavi di

cifratura sempre più lunghe; nello stesso tempo i meccanismi di decifratura

si affinano sempre più e le prestazioni dei PC aumentano in modo

vertiginoso: oggi la domanda non è “questo algoritmo è sicuro?” ma

piuttosto “in quanto tempo verrà decifrato?”. Per esempio nel 1991 venne

indetta la RSA Factoring Challenge nella quale veniva premiato con una

somma di denaro chi fosse riuscito a fattorizzare delle chiavi asimmetriche

prestabilite. Se in quell’anno una chiave di bit veniva considerata

3

30

relativamente sicura, oggi il numero consigliato è cresciuto sei volte tanto,

sino a raggiungere i bit. Chiunque non rimanga al passo con i tempi è

2

048

destinato a perdere una parte della sicurezza all’interno del suo sistema

informatico: recuperando messaggi risalenti agli anni novanta è possibile

infatti decifrarli con relativa semplicità, cosa che avverrà anche fra qualche

decennio con i documenti cifrati ora. 4

3. La crittografia asimmetrica

Questo tipo di crittografia permette di scambiare messaggi da una persona

a un’altra senza che sia necessaria una chiave comune.

Supponiamo ad esempio che

un nostro amico debba inviarci

un messaggio segreto senza

che nessun altro possa

leggerne il contenuto;

intuitivamente basterebbe

rinchiuderlo all’interno di uno

scrigno protetto con un

lucchetto, per poi fabbricare

una copia delle chiavi da

fornire al mittente. In questo

modo solo i possessori delle chiavi, chiunque essi siano, possono inviare e

ricevere messaggi. Ma cosa succederebbe se venisse sottratta la chiave? Il

nuovo possessore potrebbe fingersi uno dei due e spedire dei contenuti a

proprio piacimento o leggere quelli in arrivo.

Per questo scopo nacque la

crittografia asimmetrica:

permettere la comunicazione

senza avere la necessità di

conoscere a priori la chiave

(nell’esempio precedente

significa non dover possedere

necessariamente la chiave per

poter inviare il messaggio). In

questo metodo esistono due

diverse chiavi: una pubblica

(utilizzata solitamente per cifrare) e una privata (che ha invece la funzione di

decifrare i messaggi criptati precedentemente dalla chiave pubblica).

Supponiamo che Marco debba inviare un messaggio a Lucia: Marco invierà

solamente il lucchetto a Lucia (chiave pubblica), la quale lo userà per

chiudere lo scrigno contenente il messaggio; Marco allora, una volta

ricevuto lo scrigno, lo aprirà con la sua chiave (chiave privata): in questo

modo nessuno potrà aprire il lucchetto eccetto Marco.

Un altro campo in cui la crittografia asimmetrica viene largamente utilizzata

è quello delle firme digitali. In questo caso le due chiavi invertono le proprie

funzionalità: la chiave privata infatti viene utilizzata dal mittente con la

quale cifra la funzione di hash del messaggio (che rappresenta una sorta

d’impronta digitale, statisticamente diversa al variare del contenuto).

5

Successivamente chiunque in possesso della chiave pubblica potrà

verificare che il messaggio non sia stato modificato da terzi e attestare la

paternità di quel documento (in quanto per manomettere il messaggio è

necessario manomettere anche il suo hash, il quale è però crittografato e

quindi modificabile solo dal possessore della chiave privata).

Ma qual’è il meccanismo alla base di questo tipo di algoritmi? La cifratura

asimmetrica si basa sul principio che il prodotto fra due numeri primi (che

corrisponde a una parte sia della chiave pubblica che privata) è

relativamente veloce da effettuare, ma la fattorizzazione del numero

semiprimo (cioè un numero naturale che è il prodotto di due numeri primi)

generato dalla moltiplicazione precedente è un’operazione

computazionalmente complessa.

Esempio

Immaginiamo ad esempio di prendere come numeri primi 97 e 103:

ottenere il loro prodotto (9991) è semplice, ma non esiste nessun metodo

altrettanto veloce per risalire ai due fattori iniziali conoscendo solo 9991. E’

ora possibile intuire perché questo tipo di crittografia può essere

considerato sicuro: presi due numeri primi molto grandi diventa quindi

impossibile (in quanto richiederebbe tempi nell’ordine delle centinaia di

anni) ottenere la chiave pubblica da quella privata o viceversa. 6

4. Algoritmo di fattorizzazione

Per poter scomporre un numero semiprimo nei suoi due fattori e è

n p q

stata scelta una versione migliorata dell’algoritmo Trial Division poiché è

semplice da implementare ed è parallelizzabile all’infinito rendendo il

software di decodifica scalabile: ciò significa che all’aumentare delle risorse

disponibili (in questo caso computer) i calcoli all’interno dell’algoritmo si

possono distribuire in esse aumentando le prestazioni. Inoltre la sua

complessità è lineare al crescere di .

n

Innanzitutto è necessario determinare in che range effettuare la ricerca di

uno dei due numeri ( o ) per i quali ; infatti conoscendo un

p q p q = n

*

fattore è possibile ottenere l’altro ( ).

p = n

/q, q = n

/p

Possiamo dimostrare per assurdo che almeno un fattore debba trovarsi

nell’intervallo . Poniamo e , dove .

] 1; n ] p = n + k q = n + m k > 0 m > 0

⋀

√ √ √

Il loro prodotto sarà quindi ,

p q = (√

n + k

) (√

n + m

) = n + m n + k n + k

m

√ √

* *

ovviamente maggiore di e quindi impossibile.

n

Il caso limite sarà infatti per , ottenendo una radice quadrata

k = m = 0

perfetta ( ).

p q = (√

n + 0

) (√

n + 0

) = n n = n

√ √

* * *

Dividiamo ora il numero per , verificando se sia pari o meno. Nel caso in

n 2

cui lo sia possiamo affermare che uno dei due fattori è sicuramente ,

2

mentre l’altro è . Nel caso sia dispari si divide invece per tutti i numeri

n / 2 n

dispari interi presenti nell’intervallo (in quanto non essendo

] 2; n ]

√

divisibile per 2 non lo sarà neppure per tutti i suoi multipli), verificando

quale delle operazioni non abbia resto: se il resto è il divisore

0

corrisponderà ad uno dei due fattori.

Esempio

Proviamo a fattorizzare il numero . Sicuramente non è pari in quanto

3

5

con resto di . Cercheremo quindi i suoi fattori

n

/2 = 3

5 / 2 = 1

7, 5 1

nell’intervallo :

] 2; n ] = ] 2; 5 ]

√

3 non è un fattore di 35

3

5 mod 3 = 2 4 non è un fattore di 35

3

5 mod 4 = 3 5 è un fattore di 35

3

5 mod 5 = 0

Il secondo fattore sarà quindi .

3

5 / 5 = 7

Verifichiamo infine il risultato: se allora :

p = 5 q = 7 n = p q = 5 7 = 3

5

⋀ * *

l’algoritmo ha correttamente individuato i due fattori del numero

analizzato. 7

5. I sistemi paralleli Il software realizzato sulla base

dell'algoritmo analizzato

precedentemente può essere

eseguito in modo parallelo su

diversi host all'interno di un

dominio Windows; inoltre nelle

singole macchine esso è suddiviso

sui vari core del processore. In

questo modo è possibile ottenere

delle ottime prestazioni dividendo

il carico su PC di fascia media,

evitando così l'acquisto di costosi

server.

Tramite il protocollo MPI (Message

Passing Interface) è stato quindi

possibile trasformare un gruppo

di macchine MIMD (Multiple Instruction stream – Multiple Data stream) in

un cluster (ovvero un insieme di elementi di elaborazione che comunicano e

cooperano per risolvere velocemente problemi di grandi dimensioni e

possono essere visti come un unico sistema) attraverso lo scambio di

messaggi.