Crittografia basata su curve ellittiche

Università Ca’ Foscari – Venezia

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Informatica (Triennale)

Tesi di Laurea

Crittografia basata su Curve Ellittiche

Laureando: Gianluca Salvalaggio

Relatore: Chiar.mo prof. Riccardo Focardi

Anno Accademico 2004-2005

a Federica per l’infinita pazienza,

a Riccardo per i suoi “in bocca al lupo”,

a tutti e due … per esserci.

Indice

Indice I

Acronimi V

Simboli Matematici VII

Prefazione IX

1. Introduzione alla Crittografia 1

1.1 Concetti di base.......................................................................................... 1

1.2 Crittografia a chiave simmetrica................................................................. 4

1.3 Crittografia a chiave pubblica..................................................................... 6

1.4 Firma digitale............................................................................................. 7

1.5 Valutare un sistema crittografico ................................................................ 8

2. Crittografia a Chiave Pubblica 11

2.1 Introduzione ............................................................................................. 11

2.2 RSA ......................................................................................................... 12

2.1.1 Algoritmi per risolvere l’IFP........................................................................... 14

2.3 Sistemi basati sul Logaritmo Discreto ...................................................... 17

2.2.1 Protocollo Diffie-Hellman............................................................................... 17

2.2.2 Sistema El Gamal ............................................................................................ 18

2.2.3 Algoritmo DSA ............................................................................................... 20

2.2.4 Algoritmi per risolvere il DLP ........................................................................ 21

2.4 Crittografia su Curva Ellittica................................................................... 22

2.4.1 El Gamal su curva ellittica .............................................................................. 23

3. Curve Ellittiche 25

3.1 Introduzione ............................................................................................. 25

3.2 La legge di Gruppo................................................................................... 31

3.3 Rappresentazione dei Punti....................................................................... 33

3.3.1 Coordinate Proiettive....................................................................................... 33

3.3.2 Legge di Gruppo con Coordinate Proiettive.................................................... 35

3.4 Moltiplicazione Scalare ............................................................................ 36

3.5 Ordine di Gruppo ..................................................................................... 37

3.5.1 Determinare l’ordine di una Curva.................................................................. 39

3.5.2 Ordine dei Punti .............................................................................................. 40

3.6 Curve speciali .......................................................................................... 41

3.6.1 Curve Supersingolari....................................................................................... 42

3.6.2 Curve anomale ................................................................................................ 42

3.7 Weil pairing ............................................................................................. 43

II Indice

4. Logaritmo Discreto su Curve Ellittiche 47

4.1 Introduzione ............................................................................................. 47

4.2 Attacchi generali ...................................................................................... 48

4.2.1 Metodo Pohlig-Hellman .................................................................................. 48

4.2.2 Metodo Baby-Step Giant Step......................................................................... 49

ρ

4.2.3 Metodo Pollard ............................................................................................ 50

4.2.4 Metodo index-calculus .................................................................................... 52

4.3 Attacchi speciali ....................................................................................... 53

4.3.1 Attacco MOV .................................................................................................. 53

4.3.2 Attacco su curve anomale................................................................................ 56

4.4 Riassunto ................................................................................................. 56

5. Crittografia basata su Curve Ellittiche 59

5.1 Introduzione ............................................................................................. 59

5.2 Parametri di Dominio ............................................................................... 60

5.2.1 Criteri di scelta ................................................................................................ 60

5.3 Generazione delle Chiavi.......................................................................... 61

5.3.1 Validazione delle Chiavi ................................................................................. 61

5.4 Rappresentazione del messaggio .............................................................. 62

5.5 Firma Digitale .......................................................................................... 63

5.5.1 Introduzione..................................................................................................... 63

5.5.2 ECDSA............................................................................................................ 64

5.6 Cifratura a Chiave Pubblica...................................................................... 66

5.6.1 ECIES.............................................................................................................. 66

5.7 Scambio Chiavi ........................................................................................ 68

5.7.1 ECDH .............................................................................................................. 69

5.7.2 ECMQV........................................................................................................... 70

5.8 Standards dell’ECC .................................................................................. 72

6. Considerazioni conclusive 75

6.1 Confronti.................................................................................................. 75

6.1.1 Dimensioni delle Chiavi .................................................................................. 77

6.1.2 Dimensioni della Firma ................................................................................... 78

6.1.3 Prestazioni ....................................................................................................... 79

6.2 Conclusioni .............................................................................................. 82

Indice III

A. Concetti Matematici 83

A.1 Teoria dei Numeri ................................................................................... 83

A.2 Algebra Astratta ...................................................................................... 85

A.2.1 Gruppi............................................................................................................. 85

A.2.2 Anelli e Campi ............................................................................................... 87

A.2.3 Isomorfismi .................................................................................................... 90

A.2.4 Campi finiti .................................................................................................... 90

A.3 Discriminante di un polinomio ................................................................ 91

A.4 Complessità degli Algoritmi .................................................................... 91

B. Legge di Gruppo delle Curve Ellittiche 95

B.1 Legge di Gruppo nel caso char(K) 2,3 .................................................. 95

B.2 Legge di Gruppo nel caso char(K) = 2 ..................................................... 97

Bibliografia 99

Acronimi

Acronimi V

• AES American Encryption Standard
• ANSI American National Standards Institute
• DES Data Encryption Standard
• DHP Diffie Hellman Problem
• DLP Discrete Logarithm Problem
• DSA Digital Signature Algorithm
• DSS Digital Signature Standard
• EC Elliptic Curves
• ECC Elliptic Curve Cryptography
• ECDH Elliptic Curve Diffie-Hellman
• ECDHP Elliptic Curve Diffie-Hellman Problem
• ECDLP Elliptic Curve Discrete Logarithm Problem
• ECMQV Elliptic Curve Menezes Qu Vanstone
• FIPS Federal Information Processing Standards
• GF Galois Field
• GMR Goldwasser, Micali, Rivest
• IEEE Institute of Electrical and Electronics Engineers
• IFP Integer Factorization Problem
• MAC Message Authentication Code
• MIME Multipurpose Internet Mail Extensions
• MIPS Million of Instructions Per Second
• MOV Menezes, Okamoto, Vanstone
• NFS Number Field Sieve
• NIST National Institute of Standards and Technology
• PKI Public Key Infrastructure
• QFS Quadratic Field Sieve
• RFC Request for Comments
• RSA Rivest, Shamir, Adleman
• SSL Secure Socket Layer
• TLS Transport Layer Security

Simboli matematici

Simboli Matematici VII

b|a b divide a

x più grande intero minore o uguale a x

≅ isomorfismo fra gli anelli R ed S.

R S

⊕ somma diretta fra gli anelli R ed S.

R S

E[m] gruppo m-torsione della curva E

g g

gruppo ciclico generato da

ϕ Z n

coprimi a

funzione di Eulero, esprime il n° di interi di .

(n ) n

chiusura algebrica del campo

K K

∆ discriminante

K K

char( ) caratteristica del campo n

grado MOV relativo all’intero

n

deg ( )

MOV

a b a b

gcd( , ) massimo comune divisore fra e

f f

) immagine della funzione

Im( n n

log logaritmo in base 2 di

n

logaritmo naturale di

ln n α α

−

1

+

( c o (

1

)) (log n ) (log log n )

O ( e )

α

L c

[ , ]

n

*

R R

insieme degli elementi invertibili dell’anello

Z n n

insieme degli interi modulo : 0, 1, 2, …, –1

Prefazione

Prefazione IX

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 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

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 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 significato originale.

steganòs

nemico avversario

e/o trova

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 detta cifratura, e produce il testo cifrato. Il procedimento inverso che dal messaggio cifrato ricostruisce il messaggio in chiaro è chiamato decifratura.

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 modifica stesso ma la cosiddetta chiave, 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 come Principio di Kerckhoff, dal nome del linguista-crittografo fiammingo Auguste Kerckhoff che nel 1883 postulò tale idea in un articolo intitolato “La 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 sulla segretezza del metodo (nel gergo anglosassone, security by obscurity, ) hanno fallito.

In Figura 1.1 è illustrato un generico modello crittografico, dove P rappresenta il testo in chiaro e C è il messaggio cifrato.

C

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à A e B che comunicano attraverso un canale insicuro sul quale è in ascolto un’entità nemica E.

Ad esempio A e B possono essere due persone che dialogano attraverso telefoni cellulari ed E vuole ascoltare la loro conversazione.

Oppure A può rappresentare il browser web di una persona la quale desidera fare acquisti sul sito di shopping-online B. In tale scenario il canale è Internet e l’entità E è rappresentata dal sito web e vuole leggere il traffico fra A e B per, ad esempio, ottenere il numero della carta di credito di α.

Un terzo esempio vede A e B che si scambiano e-mail su Internet e E l’avversario che desidera leggere la loro corrispondenza oppure inviare a sua volta messaggi a B, facendo finta di essere A.

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 leggerla. Quindi un messaggio inviato da A a B non deve essere leggibile da E.
• Data Integrity: assicurare che i dati non vengano alterati