Crittografia basata su curve ellittiche

Prefazione IX

Prefazione

La sempre maggiore diffusione di dispositivi wireless e il crescente bisogno di

sicurezza esigono l’utilizzo di sistemi crittografici che possano soddisfare le

stringenti limitazioni imposte, in termini di consumo energetico, utilizzo di banda

e capacità elaborativa. L’introduzione della Crittografia basata su Curve Ellittiche

Elliptic Curve Cryptography ) è relativamente recente ma negli ultimi dieci

(ECC,

anni tale tecnica si è rapidamente imposta come alternativa ai sistemi crittografici

a chiave pubblica già largamente utilizzati come RSA e DSA. La principale

attrattiva dell’ ECC è che al momento non esistono algoritmi sufficientemente

veloci che risolvano il problema matematico sul quale si basa. Ciò significa che

l’ECC offre lo stesso livello di sicurezza dei sistemi tradizionali (RSA, DSA,

Diffie-Hellman) utilizzando chiavi di dimensione inferiore, richiedendo così

elaborazioni più veloci, consumi energetici contenuti e un risparmio di utilizzo

della banda. Tali caratteristiche, quindi, rendono l’ECC particolarmente adatta

all’utilizzo in ambienti con limitata disponibilità di risorse: palmari, telefoni

cellulari, smart cards.

Obbiettivi e Organizzazione della Tesi. Verrà presentata la Crittografia basata

su Curve Ellittiche, analizzando sia gli aspetti teorici che i protocolli utilizzati e

soprattutto confrontando questa tecnica con le attuali soluzioni a chiave pubblica.

Considerata la natura dell’argomento, l’esposizione sarà caratterizzata da un taglio

necessariamente matematico e formale. Il primo capitolo riprende i concetti base

della Crittografia. Il Capitolo 2 presenta i principali sistemi asimmetrici e

introduce brevemente l’ECC mentre il terzo descrive le Curve Ellittiche e

l’aritmetica ad esse abbinata. Il Capitolo 4 affronta lo studio del problema

matematico sul quale si basa l’ ECC, ossia l’Elliptic Curve Discrete Logarithm

Problem (ECDLP). Nel Capitolo 5 si analizzano i principali protocolli crittografici

basati sulle curve ellittiche. L’ultimo capitolo infine confronta l’ECC con gli altri

sistemi a chiave pubblica. In Appendice A sono raccolte le nozioni matematiche

fondamentali per la comprensione dell’argomento, l’Appendice B contiene le

formule matematiche relative alla regola di addizione su Curve Ellittiche.

X Prefazione

Al fine di evitare traduzioni dall’inglese all’italiano troppo “forzate”, ho

mantenuto molti termini nella lingua originale, ritenendo che questo non potesse

compromettere la leggibilità dei contenuti.

Introduzione alla Crittografia 1

Capitolo 1

Introduzione alla Crittografia

1.1 Concetti di base kryptòs gràphein

Il termine Crittografia deriva dalla lingua greca ( , nascosto e ,

scrivere) ed è la scienza, in parte arte, delle scritture segrete. La crittografia,

comunque, non mira a nascondere un particolare messaggio, obiettivo della

steganòs

steganografia ( , coperto), bensì a modificarne il significato. Per rendere

incomprensibile un testo lo si altera per mezzo di un procedimento concordato dal

mittente e dal destinatario. Questi può quindi invertire il procedimento, e ricavare

il testo originale. Il vantaggio della crittografia è che se il nemico intercetta il

messaggio, esso risulta irriconoscibile. Infatti l’avversario, non conoscendo il

procedimento di alterazione, troverà arduo, se non impossibile, ricostruire il

nemico avversario

e/o trova

significato originale. L’utilizzo del termine

giustificazione nel fatto che storicamente la crittografia è stata impiegata per scopi

militari, in ambienti diplomatici e dai servizi segreti, oltre che per motivi

passionali. Un avvincente storia della crittografia è raccontata in [30].

Precisamente la crittografia studia le tecniche matematiche che consentono di

modificare un messaggio in modo da renderlo incomprensibile ad un avversario

malintenzionato, ma leggibile al destinatario. La modifica del testo in chiaro viene

cifratura testo cifrato

detta , e produce il . Il procedimento inverso che dal

decifratura

.

messaggio cifrato ricostruisce il messaggio in chiaro è chiamato

Come detto precedentemente, il mittente ed il legittimo destinatario devono

condividere a priori una conoscenza che consenta la cifratura del messaggio in

chiaro e la successiva decifratura. Tale conoscenza però non è il processo di

chiave

modifica stesso ma la cosiddetta ossia una stringa alfanumerica che

costituisce un parametro della funzione di cifratura e della funzione di decifratura.

Pertanto il metodo di alterazione è noto a chiunque, e quindi anche al nemico, ma

ogni volta viene parametrizzato da una chiave segreta condivisa fra mittente e

destinatario. Questo concetto, universalmente condiviso, è passato alla storia

Principio di Kerckhoff

come , dal nome del linguista-crittografo fiammingo

La

Auguste Kerckhoff che nel 1883 postulò tale idea in un articolo intitolato “

cryptographie militare ”:

“tutti gli algoritmi devono essere pubblici, solo le chiavi sono segrete”

2 Introduzione alla Crittografia

Nel tempo infatti i vari sistemi di crittografia che basavano la propria sicurezza

security by obscurity

sulla segretezza del metodo (nel gergo anglosassone, ) hanno

fallito. P

In Figura 1.1 è illustrato un generico modello crittografico, dove rappresenta il

C

testo in chiaro e è il messaggio cifrato.

P C P

Mittente Destinatario

Cifratura Decifratura

Chiave Chiave

Figura 1.1 Generico schema crittografico

Se la crittografia si occupa dei possibili metodi di cifratura, la Crittoanalisi studia

le tecniche che consentono di decifrare, leggi sconfiggere, tali metodi ossia di

ricavare il testo in chiaro dal messaggio cifrato senza conoscere la chiave segreta

ma sfruttando debolezze dell’algoritmo impiegato. Più precisamente la

crittoanalisi mira a scoprire il valore della chiave utilizzata. Le aree della

crittografia e della crittoanalisi formano insieme ciò che viene chiamata

Crittologia.

Vediamo ora come le tecniche crittografiche vengono utilizzate per garantire

comunicazioni sicure fra due controparti.

Canale insicuro

A B

E

Figura 1.2 Modello di comunicazione

Introduzione alla Crittografia 3

A B

Nella Figura 1.2 sono rappresentate le entità e che comunicano attraverso un

E A B

canale insicuro sul quale è in ascolto un entità nemica . Ad esempio e

E

possono essere due persone che dialogano attraverso telefoni cellulari ed vuole

A può rappresentare il browser web di una

ascoltare la loro conversazione. Oppure

α β

persona la quale desidera fare acquisti sul sito di shopping-online

B E

. In tale scenario il canale è Internet e l’entità vuole

rappresentato dal sito web

A B

leggere il traffico fra e per, ad esempio, ottenere il numero della carta di

α A B

credito di . Un terzo esempio vede e che si scambiano e-mail su Internet e

E

l’avversario che desidera leggere la loro corrispondenza oppure inviare a sua

B A

volta messaggi a , facendo finta di essere .

Gli scenari appena descritti ci aiutano a delineare quelli che sono i principali

obiettivi di una comunicazione sicura:

Confidenziality: mantenere un informazione segreta a tutti tranne a chi deve

A B E

a non deve essere leggibile da .

leggerla. Quindi un messaggio inviato da

Data Integrity: assicurare che i dati non vengano alterati senza

B A

autorizzazione. Quindi deve poter rilevare se i messaggi inviati da sono

E

.

stati modificati da

Data Origin Authentication: B

verificare la fonte dei dati. può verificare se i

A A

dati con mittente pari ad sono stati effettivamente inviati da .

Entity Authentication: B

verificare l’identità di un’entità. deve essere

convinto dell’identità della controparte con cui sta comunicando.

Non-repudiaton: impedire che un entità possa negare di aver commesso una

B A

certa azione. Quando riceve un messaggio da , non solo è convinto che tale

A

messaggio è stato proprio generato da , ma può anche convincere una terza

A

parte neutrale di questo; pertanto non può negare di avere inviato il

B

messaggio a .

Gli algoritmi crittografici possono essere divisi in due classi principali: gli

algoritmi a chiave simmetrica e quelli a chiave pubblica (o asimmetrica). Nei

paragrafi successivi entrambe le famiglie verranno presentate.

4 Introduzione alla Crittografia

1.2 Crittografia a chiave simmetrica

Gli algoritmi di crittografia a chiave simmetrica usano la stessa chiave sia per la

cifratura che per la decifratura, da cui il nome. Storicamente nati per primi, i

cifrari simmetrici fanno uso, in modo più o meno evoluto, di tecniche di

E D

sostituzione e di trasposizione. Nella Figura 1.3 ( ) e ( ) rappresentano la

K

funzione di cifratura e di decifratura mentre è la chiave condivisa fra mittente e

canale sicuro

destinatario. Tale chiave dovrà essere comunicata attraverso un che,

1

nella realtà dei fatti, è difficile da realizzare .

P C P

Mittente Destinatario

E( ) D( )

K Canale sicuro

Origine

chiave

Figura 1.3 Sistema crittografico simmetrico

La caratteristica più apprezzata dei cifrari simmetrici è che sono particolarmente

veloci e facili da implementare, sia in hardware che in software. L’aspetto

Problema della Distribuzione delle Chiavi

negativo invece, riguarda il cosiddetto :

N

se ho entità che devono comunicare in modo sicuro attraverso un cifrario di tipo

N

simmetrico, ogni entità dovrà possedere – 1 chiavi differenti, una per ognuna

delle altre entità; questo significa che in totale dovranno essere generate, e

1 D’altra parte questo canale sicuro, potrebbe essere utilizzato anche per trasmettere il messaggio

stesso. Introduzione alla Crittografia 5

−

N ( N 1

) chiavi diverse. Si capisce bene che già con valori modesti

conservate, 2

di N la cosa diventa complicata da gestire.

Vediamo ora una breve rassegna dei principali algoritmi simmetrici. Per

approfondimenti si veda [22, 31, 32].

DES/3DES

. Nel maggio del 1973 il National Bureau of Standards degli Stati

Uniti sollecitò lo sviluppo del Data Encryption Standard (DES) ossia di un

crittosistema di riferimento. Il DES venne progettato dall’IBM come modifica di

un cifrario preesistente chiamato LUCIFER e venne pubblicato nel Federal

Register il 17 marzo 1975. Nel gennaio del 1977 il governo degli Stati Uniti

adottò il DES come standard per le informazioni “unclassified”, ossia non

riservate. Tralasciando i dettagli dell’algoritmo è utile evidenziare la lunghezza

della chiave utilizzata: 56 bit. Per le potenze di calcolo disponibili negli anni ’70,

’80 tale dimensione era considerata sufficientemente sicura. Ma già nel 1998 un

elaboratore progettato dall’Electronic Frontier Foundation e dalla Cryptography

Research, denominato Deep Crack, riuscì a violare l’algoritmo DES con attacco a

forza bruta in meno di 56 ore, con costi di realizzo alla portata di enti governativi

e istituti di ricerca. Pertanto oggi il DES non è più considerato sicuro. Il cosiddetto

triplo DES, 3DES, costituisce una evoluzione del DES originale, attraverso un uso

ripetuto, in cascata, di tre cifrari DES; in tal modo è possibile portare la

dimensione della chiave a 112 bit, ottenendo così un crittosistema molto robusto

che viene largamente utilizzato in tutte le odierne soluzioni crittografiche

commerciali.

AES

. Verso la fine degli anni ’90 il NIST (National Institute of Standards and

Technology) decise che il governo statunitense aveva bisogno di un nuovo

standard per le comunicazioni non riservate. A tal fine nel 1997 organizzò una

gara internazionale, alla quale parteciparono crittografi da tutto il mondo, per

individuare il nuovo standard che avrebbe preso il nome di AES (Advanced

Encryption Standard). Nell’ottobre 2000 il NIST annunciò che il vincitore del

concorso era l’algoritmo Rijndael, sviluppato da due studiosi belgi Joan Daemen e

Vincent Rijmen e nel novembre 2001 AES divenne uno standard del governo

degli Stati Uniti. Tale algoritmo supporta chiavi con dimensioni da 128, 192 e 256

bit, quindi è impensabile violarlo con attacco a forza bruta.

6 Introduzione alla Crittografia

1.3 Crittografia a chiave pubblica

Come già detto nel paragrafo precedente, la distribuzione delle chiavi è sempre