Crittografia basata su identità (IBE): un concetto naturale ma un calcolo difficile. Studio progetto e valutazione di architetture HW per il calcolo della Tate Pairing in Caratteristica Tre.

CAPITOLO 1. INTRODUZIONE 2
dei metodi a chiave segreta e` che sono generalmente meno onerosi da un punto
di vista computazionale, e quindi piu` veloci di quelli a chiave pubblica.
Nella crittografia asimmetrica ciascuna parte detiene una coppia di chia-
vi: una privata, che deve essere mantenuta assolutamente segreta (come nella
crittografia simmetrica), e una pubblica, che viene resa disponibile a chiun-
que. Le coppie di chiavi sono legate tra loro matematicamente in modo che
un messaggio cifrato con una puo` essere decifrato solo con l’altra. Quando
l’utente A vuole inviare un messaggio riservato all’utente B, lo cifra con la
chiave pubblica di B e poi glielo invia; il messaggio puo` essere decifrato solo
da B con la propria chiave privata. Analogamente si comportera` B per ri-
spondere ad A in modo riservato, servendosi di una seconda coppia di chiavi,
una privata e l’altra pubblica.
Il grande vantaggio di questi metodi e` che viene eliminata l’esigenza di
inviare e ricevere una chiave segreta, in quanto e` sufficiente inviare una chiave
pubblica che non ha esigenze di riservatezza.
Esiste un terzo metodo, che potremmo definire “misto” o “ibrido”, che
consente di avere i vantaggi di entrambi i metodi precedenti; si utilizzano
due algoritmi di crittografia: uno asimmetrico e uno simmetrico. Le parti
che vogliono comunicare in modo riservato utilizzano entrambi gli algoritmi
e detengono ciascuna una coppia di chiavi (privata, pubblica) relative all’al-
goritmo asimmetrico. Possiamo supporre che le rispettive chiavi pubbliche
siano state precedentemente scambiate o che vengano scambiate all’inizio
della comunicazione. All’inizio di ogni sessione di comunicazione le parti si
scambiano una chiave segreta cifrata con un metodo a chiave pubblica (ov-
vero, si cifra la chiave segreta mediante la chiave privata, la si invia e la si
decifra mediante la chiave pubblica); la chiave simmetrica viene poi usata per
cifrare e decifrare i messaggi successivamente scambiati nella stessa sessione
tra le parti. La chiave segreta viene cambiata a ogni nuova sessione a tutto
vantaggio della sicurezza.
In questo lavoro di tesi ci occuperemo solamente di sistemi di crittografia
a chiave pubblica. I problemi matematici principali su cui si fonda la sicu-
rezza di un sistema a chiave pubblica sono la fattorizzazione in numeri primi
CAPITOLO 1. INTRODUZIONE 3
(RSA1) [25] oppure il problema del logaritmo discreto (DLP2) [19] applicato
al gruppo moltiplicativo di un campo finito.
Nel 1985 Victor Miller [22] propose la contestualizzazione del problema
del logaritmo discreto sul gruppo dei punti di una curva ellittica; questi
sistemi sono detti ECC 3 [26]. Essi sono in grado di fornire lo stesso livello
di sicurezza dei tradizionali sistemi a chiave pubblica, utilizzando chiavi e
certificati di lunghezza (in bit) inferiore. Per i particolari sulla definizione
di curva ellittica e la costruzione del gruppo di punti, si rimanda alla tesi;
sono aspetti troppo articolati per riassumerli qui. Cio` che conta e` sapere
che ECDLP4 e` un problema di log discreto, reputato molto difficile. Questo
e` possibile perche´ non esistono algoritmi a tempo sub-esponenziale per la
risoluzione di ECDLP.
L’utilizzo della crittografia a chiave pubblica impone la creazione di un’in-
frastruttura di autenticazione che leghi effettivamente le chiavi pubbliche al-
l’identita` degli utenti che le dichiarano. Tale infrastruttura viene indicata
come Public Key Infrastructure (PKI) [16]. Essa si basa sull’esistenza di
una Certification Authority sicura, che ha il compito di custodire le chiavi
pubbliche e di distribuirle a chi ne deve fare uso, garantendone l’autenticita`.
L’organizzazione e la gestione di una PKI rappresentano la parte piu` delica-
ta dei sistemi a chiave pubblica. La ricerca piu` attuale mira all’introduzione
di nuovi protocolli, basati su tecniche matematiche innovative, che possano
ridurre la gravosita` dei compiti affidati a una Certification Authority (CA),
mantenendo tuttavia i livelli di sicurezza dei sistemi attuali.
Nel 1984 Shamir [28] elaboro` uno schema di crittografia a chiave pubbli-
ca Identity Based Encryption (IBE) nel quale la chiave pubblica puo` essere
una stringa arbitraria, ad esempio un identificativo dell’utente destinatario,
come l’indirizzo e-mail. Nell’ambito IBE, quando Alice vuole mandare un
messaggio a Bob, ella semplicemente puo` eseguire la cifratura del messag-
gio utilizzando come chiave pubblica l’indirizzo e-mail di Bob, ad esempio
1Acronimo di Rivest, Shamir, Adleman autori del crittosistema.
2Discrete Logarithm Problem.
3Elliptic Curve Cryptosystem.
4Elliptic Curve Dicrete Logarithm Problem, ovvero il problema del logaritmo discreto
immerso nel gruppo dei punti di una curva ellittica.
CAPITOLO 1. INTRODUZIONE 4
[email protected]. Alice non ha la necessita` di interfacciarsi con una CA
per ottenere il certificato contenente la chiave pubblica di Bob. La possibi-
lita` di calcolare la chiave pubblica di cifratura, partendo direttamente dalle
informazioni pubbliche sull’identita` del destinatario, elimina la necessita` di
complesse operazioni di validazione dei certificati. In altri termini un sistema
IBE permette di beneficiare di tutti i vantaggi di un sistema a chiave pubbli-
ca, ma senza la necessita` dei certificati. Questo basta, per ora, a motivare il
potenziale applicativo di IBE, se si riuscisse a calcolarlo in modo efficiente.
Alla base di un tale sistema si trova una particolare funzione di dualita` che
gode della proprieta` di bilinearita` [5]. Le dualita` di Tate e di Weil (Tate/Weil
Pairing) sono delle mappe bilineari non degeneri che associano una coppia
di punti di una curva ellittica avente determinate proprieta`, a un elemento
del sottogruppo moltiplicativo di un particolare campo finito. Matematica-
mente, si puo` dimostrare che la Weil Pairing e` equivalente all’applicazione di
due funzioni di dualita` di Tate, e pertanto generalmente si considera la sola
dualita` di Tate.
Il calcolo della dualita` di Tate e` pero` un processo molto complesso, che si
scompone in svariati tipi di operazioni tra elementi di campi finiti: addizione,
moltiplicazione, potenza e radice. Per usare questi nuovi algoritmi IBE in
situazioni pratiche, la Tate Pairing deve essere calcolata in modo efficiente.
Basti dire che la Tate Pairing ha acquisito una forma calcolabile in tempo
almeno accettabile solo molto di recente, dopo un intenso lavoro di precisione
matematica. Il contributo piu` significativo fu apportato da Miller in [21],
e consiste nell’omonimo teorema che da` una regola ricorsiva per calcolare
funzioni razionali su curve ellittiche. In [8], Galbraith, Harrison e Soldera,
presentarono alcuni metodi per implementare efficientemente le operazioni
aritmetiche tra gli elementi dei campi finiti coinvolti nel calcolo. Barreto,
Kim, Lynn e Scott proposero in [2] la Tate Pairing ridotta. In particolare,
notarono che il denominatore dell’algoritmo standard di Miller diveniva pari
a uno, dopo l’esponenziazione finale, e che quindi poteva essere scartato,
senza cambiare il risultato della dualita`. In [6], Duursma e Lee diedero una
formula chiusa per il calcolo della Tate pairing in caratteristica tre, ottenendo
un algoritmo molto veloce. Subito dopo, Kwon propose un nuovo algoritmo,
CAPITOLO 1. INTRODUZIONE 5
dove non sono presenti estrazioni di radice cubica e quindi potenzialmente
piu` efficiente. Ulteriori ottimizzazioni all’algoritmo di Duursma per le curve
ellittiche supersingolari si possono trovare in [10], [15] e [27].
Comunque, tutti questi lavori si sono focalizzati principalmente sull’otti-
mizzazione dell’aritmetica dei campi finiti, in prospettiva di una implementa-
zione software della Tate Pairing. Il passaggio dalla formulazione matematica
a un algoritmo efficiente, in hardware, comporta molto lavoro di ingegnerizza-
zione. Solo recentemente sono apparsi degli articoli dove vengono discusse e
proposte delle soluzioni per un’implementazione hardware della Tate pairing
in caratteristica tre [9], [13]. In particolare, una scelta oculata nella rappre-
sentazione del campo finito esteso ha permesso di ottimizzarne le operazioni
e di renderle potenzialmente parallelizzabili, richiedendo solo dell’aritmetica,
relativamente semplice, nel campo base. Successivamente, grazie all’algo-
ritmo “folklore” proposto da Barreto in [1], anche l’estrazione della radice
cubica nel campo base di caratteristica tre e` divenuta computazionalmen-
te efficiente; cio` ha permesso di rivalutare l’algoritmo di Duursma-Lee, a
scapito di quello proposto da Kwon. Tutto questo comunque, per quanto
significativo, ha appena scalfito il problema di come calcolare efficientemente
in hardware la dualita` di Tate.
1.2 Scopo del lavoro
Lo scopo di questo lavoro di tesi e` quello di progettare architetture hardware
per il calcolo della Tate Pairing, mettendo in evidenza il massimo paralle-
lismo ottenibile in alcuni algoritmi (Duursma-Lee, Kwon e GPS) presenti
in letteratura per il calcolo della Tate Pairing in caratteristica 3, su curve
supersingolari. A differenza dei lavori svolti finora, dove ci si e` fermati a
ottimizzare le operazioni nel campo esteso F36m , semplicemente paralleliz-
zando quelle necessarie nel campo base F3m , abbiamo individuato le mutue
dipendenze fra tutte le operazioni in F3m presenti nell’algoritmo, paralleliz-
zando quindi operazioni nel campo base anche “non appartenenti” alla stessa
operazione nel campo esteso. Questa analisi, che comporta l’esplorazione di
uno spazio di soluzioni enormemente piu` esteso di quanto non si faccia nelle
CAPITOLO 1. INTRODUZIONE 6
ricerche finora note, ci ha permesso di ridurre al minimo la profondita` del
cammino critico del dispositivo di calcolo e quindi di ottimizzare la latenza
del calcolo stesso.
Abbiamo proposto anche un’architettura hardware e dato una stima del-
le aree e dei tempi necessari per eseguire ogni algoritmo di Tate Pairing,
confrontando i nostri risultati con quanto noto in letteratura.
Anticipiamo che i risultati sono molto buoni; schedulando le operazioni
mediante un algoritmo di tipo List-based, abbiamo ottenuto dei tempi di
calcolo della Tate Pairing inferiori a quelli presenti in letteratura, utilizzando
un numero ridotto di unita` funzionali hardware progettate per operare in
F3m , riducendo cos`ı anche i costi e le dimensioni.
Notevole interesse ha riscosso l’algoritmo GPS, evidenziando un eleva-
to grado di parallelismo, riducendo quindi in modo significativo i tempi di
calcolo della Tate Pairing.
1.3 Lavoro svolto
Il lavoro svolto puo` essere suddiviso in sette fasi:
1. Una prima fase di studio teorico finalizzata alla comprensione delle
problematiche relative alla crittografia basata su curve ellittiche, alla
dualita` di Tate e all’acquisizione delle basi matematiche necessarie.
2. Una seconda fase costituita dalla progettazione software degli algoritmi
utilizzati per implementare l’aritmetica in F3m e nel campo finito esteso,
in coordinate affini. Inoltre, l’implementazione di quattro algoritmi
presenti in letteratura per il calcolo della Tate Pairing in caratteristica 3
su curve supersingolari. In particolare, l’algoritmo BKLS, di Duursma-
Lee, GPS e di Kwon. Il codice e` stato scritto in ANSI C, avvalendosi
anche della libreria NTL [29] per la gestione di numeri in precisione
multipla e per l’aritmetica sui campi finiti.
3. Una terza fase, decisamente laboriosa, di riscrittura e ottimizzazione
degli algoritmi, in modo tale che comparissero solamente operazioni nel
CAPITOLO 1. INTRODUZIONE 7
campo base, ovvero addizioni/sottrazioni, moltiplicazioni, elevamenti al
cubo, estrazioni di radice cubica e inversioni di segno in F3m .
4. Una quarta fase di riscrittura degli algoritmi espansi, in una forma
richiesta da uno strumento automatizzato di scheduling, progettato e
programmato appositamente per tale scopo.
5. Una quinta fase di studio finalizzata alla comprensione del progetto di
un’architettura hardware VLSI (data-path), in particolare del problema
dello scheduling e delle varie politiche relative presenti in letteratura.
6. Una sesta fase di studio e di ricerca al fine di proporre un’architettura
hardware (coprocessore) per la Tate Pairing; in particolare, uno studio
di fattibilita` delle varie unita` funzionali e una stima delle aree occupate,
ipotizzando di sintetizzare il circuito su FPGA.
7. Una settima fase costituita da numerose simulazioni realizzate con lo
scheduler e dall’analisi e confronto dei risultati prestazionali (area e
tempo) ottenuti.
1.4 Cenni ai contenuti originali
Anticipiamo i principali contributi originali apportati dal seguente lavoro:
1. Implementazione in ANSI C di una libreria che permette di eseguire le
operazioni di gruppo su cui si basano i sistemi ECC e l’aritmetica in F3m
e in F36m in coordinate affini (mediante l’utilizzo dell’implementazione
dell’algebra sui campi finiti data dalle librerie NTL), con la possibilita`
di scegliere l’estensione del campo finito su cui lavorare.
2. Implementazione e ottimizzazione in ANSI C di quattro algoritmi (BKLS,
DL, KWON e GPS) che permettono il calcolo della dualita` di Tate su
curve ellittiche supersingolari, definite su campi finiti di Caratteristica
Tre. Inoltre, implementazione di un algoritmo efficiente per il calcolo
dell’esponenziazione finale.
CAPITOLO 1. INTRODUZIONE 8
3. Ottimizzazione dei tempi di esecuzione degli algoritmi sopracitati, me-
diante parallelizzazione delle operazioni nel campo finito F3m presenti in
ognuno di essi, utilizzando uno strumento automatizzato di scheduling.
4. Studio di fattibilita`, progetto e valutazione di architetture hardware
dedicate al calcolo della Tate Pairing in Caratteristica Tre, ipotizzando
di lavorare su FPGA (Field Programmable Gate Array).
1.5 Suddivisione del lavoro
Il Capitolo 2 fornisce un riassunto informale (cioe` quasi senza matematica)
dei capitoli 3, 4, 5 e 6, cos`ı da dare al lettore una comprensione intuitiva della
Tate Pairing e del suo uso in IBE, per rendere meno ardua la lettura della
trattazione formale successiva.
Nel Capitolo 3 si riportano i concetti matematici necessari alla compren-
sione della crittografia basata su curve ellittiche.
Nel Capitolo 4 si descrive il protocollo IBE analizzando la struttura-
zione delle procedure di cifratura, decifratura ed enunciando il problema
matematico su cui si basa la sicurezza di IBE.
Nel Capitolo 5 si introducono le Mappe di Dualita`, in particolare la Dua-
lita` di Tate. Si prosegue quindi con l’analisi degli algoritmi di Miller e BKLS,
i primi due proposti per il calcolo della Tate Pairing.
Il Capitolo 6 contiene tutti i dettagli dell’implementazione, partendo dal-
l’aritmetica nel campo base, per poi passare a quella nel campo esteso. Si
conclude il capitolo mostrando gli algoritmi piu` efficienti per il calcolo della
Tate Pairing noti in letteratura, riportando anche i tempi migliori ottenuti
in software.
Nel Capitolo 7 si introduce il problema dello scheduling, analizzando le
strategie possibili e menzionando gli algoritmi piu` comuni per risolverlo. Si
conclude il capitolo mostrando l’approccio utilizzato per realizzare lo stru-
mento di scheduling, usato in questa tesi per studiare la parallelizzazione in
hardware della dualita` di Tate.
Nel Capitolo 8 si propone un’architettura hardware per la Tate Pairing,
CAPITOLO 1. INTRODUZIONE 9
per poi procedere con l’analisi e lo studio di ogni singola unita` funzionale
presente.
Nel Capitolo 9 si riportano i risultati finali (costi e prestazioni), confron-
tandoli con quelli presenti in letteratura.
Il Capitolo 10 contiene le conclusioni sul lavoro svolto e suggerisce delle
linee guida per i lavori futuri.
Viene infine riportata un’appendice A contenente molti aspetti matema-
tici utili per la comprensione e lo sviluppo di tutto il lavoro, in particolare
l’algebra dei campi finiti. L’Appendice B invece completa i Paragrafi 7.4 e
8.3, proponendo delle tabelle aggiuntive.
Nel lavoro si da` per acquisita, da parte del lettore, la conoscenza dei
fondamenti dell’aritmetica dei campi finiti. Se cos`ı non fosse, il lettore e`
invitato prima a leggere l’Appendice A, che ne da` un sommario e contiene
numerosi esempi facili.
Capitolo 2
Concetti generali
Questo capitolo vuole riassumere in maniera informale i concetti che si incon-
treranno nei capitoli successivi, dove verranno invece trattati formalmente e
approfonditamente. Lo scopo e` quello di dare al lettore una comprensione
intuitiva del logaritmo discreto, delle curve ellittiche, della definizione e pro-
prieta` di dualita` di Tate, e di IBE mediante lo schema di Boneh-Franklin. Si
rimanda all’Appendice A per acquisire i fondamenti dell’aritmetica dei campi
finiti, che qui si suppongono gia` noti.
2.1 Logaritmo discreto
Si consideri un generico gruppo (finito) e si denoti con • la sua legge di
composizione (supponiamo di tipo moltiplicativo). Il problema del logaritmo
discreto si presenta nella seguente forma:
Dato un gruppo finito (G, •), a ∈ G, b ∈ H, con H = {ai : i ≥ 0}
sottogruppo generato da a, determinare l’unico intero c tale che
0 ≤ c ≤ |H| − 1 e ac = b. L’intero c si indica con logab. Con |H|
si denota l’ordine di H, cioe` il numero degli elementi h ∈ H.
Consideriamo ad esempio il campo finito Zp, con p primo (problema del
logaritmo discreto in Zp) e con Zp∗ il suo gruppo moltiplicativo. In questo
caso si puo` descrivere il problema nel modo seguente:
10
CAPITOLO 2. CONCETTI GENERALI 11
Dato p primo, a ∈ Zp elemento primitivo (cioe` a ha ordine uguale
a p− 1), b ∈ Zp∗, determinare l’unico intero c, con 0 ≤ c ≤ p− 2,
tale che ac ≡ b mod p. L’intero c si denota con logab.
Evidenziamo che H, per ogni scelta di a ∈ G, e` un gruppo ciclico di ordine
|H|. Quindi la questione si riconduce al caso di problema in un gruppo ci-
clico. Questo mostra come la difficolta` del problema del logaritmo discreto
dipenda principalmente dalla rappresentazione del gruppo considerato. Ci
sono infatti anche dei casi dove la risoluzione del problema del logaritmo
discreto e` banale. Consideriamo, per esempio, il gruppo additivo ciclico Zn
e supponiamo MCD(a, n) = 1 (quindi a e` un generatore di Zn ). L’opera-
zione ac corrisponde alla moltiplicazione di a per c modulo n. In questo caso
il problema del logaritmo discreto consiste nel trovare un intero c tale che
ac ≡ b mod n. Dal fatto che MCD(a, n) = 1 segue che a possiede a−1 , in-
verso moltiplicativo modulo n, che si puo` facilmente calcolare con l’algoritmo
euclideo [19]. A questo punto si ricava facilmente c = logab = ba−1 mod n.
Si consideri invece il gruppo moltiplicativo Zp∗, con p primo. Esso e`
un gruppo ciclico di ordine p − 1 e quindi e` isomorfo al gruppo additivo
Zp−1. E` stato mostrato in precedenza quanto il calcolo del logaritmo discreto
sia efficiente in tali gruppi additivi. Cio` suggerisce di trasportare il problema
dato in Zp∗ in quello facilmente risolvibile in Zp−1. Questo metodo puo` essere
applicato al problema del logaritmo discreto in ogni gruppo G. Se esiste un
metodo efficiente per calcolare l’isomorfismo tra H e Z|H|, il problema del
logaritmo discreto in G puo` essere risolto in maniera efficiente. Al contrario,
si puo` mostrare facilmente che un efficiente metodo di calcolo del logaritmo
discreto produce un algoritmo efficiente per il calcolo dell’isomorfismo tra i
due gruppi.
Quanto detto finora mostra che la difficolta` del problema del logaritmo
discreto dipende dalla rappresentazione del gruppo ciclico considerato. Un
problema molto interessante e` la ricerca di gruppi per cui il problema del
logaritmo discreto sia intrattabile: tra questi vi sono i gruppi moltiplicativi
di un campo di Galois GF (pn) e i gruppi di punti su curve ellittiche in un
campo finito, come verra` mostrato nel paragrafo 3.4.
CAPITOLO 2. CONCETTI GENERALI 12
2.2 Curva ellittica
I metodi crittografici basati sulle curve ellittiche sono stati proposti alla meta`
degli anni ′80. Una curva ellittica puo` essere definita su qualunque campo
(ad esempio reale, razionale, complesso), ma le curve utilizzate in crittografia
sono principalmente definite su campi finiti. Una curva ellittica nel piano x, y
e` costituita dall’insieme di elementi o punti (x, y) soddisfacenti l’equazione
y2 = x3 + ax + b, insieme ad un altro elemento indicato con O e chiamato
punto all’infinito, che puo` essere visualizzato come il punto all’inizio e alla
fine di ogni linea verticale. La regola per addizionare due punti su una curva
ellittica E(Fp) e` chiamata regola della corda e della tangente [19]. Il risulta-
to di tale addizione e` un terzo punto sulla curva. L’insieme dei punti E(Fp)
con l’operazione di addizione forma un gruppo, e tale gruppo e` usato per la
costruzione di crittosistemi su curve ellittiche. Vediamo il significato geome-
trico dell’addizione di due punti P = (x1, y1) e Q = (x2, y2) distinti su una
curva ellittica E. La somma di P e Q, denotata con −R = (x3, y3), e` definita
come segue (Figura 2.1, nel campo reale per consentire la rappresentazione
grafica):
• Si traccia una linea retta r tra P e Q per trovare il terzo punto di
intersezione R con la curva.
• −R e` il punto di intersezione tra la curva e la linea retta verticale r′
che passa per R.
Se P = (x1, y1), 2P = P +P , denotato con −R = (x3, y3), e` ottenuto nel
seguente modo (Figura 2.2):
• Si traccia la tangente r passante per il punto P , la quale interseca la
curva in un secondo punto R.
• −R e` il punto di intersezione tra la curva e la linea retta r′ ortogonale
all’asse delle x e passante per R.
Infine vi e` l’operazione di addizione multipla o prodotto scalare kP : con
questa scrittura si intende che il punto P = (x, y) e` sommato a se stesso k
volte, vale a dire kP = P + P + . . .+ P︸ ︷︷ ︸
k volte
.
CAPITOLO 2. CONCETTI GENERALI 13
Figura 2.1: Descrizione geometrica dell’addizione di due punti su una curva
ellittica.
Figura 2.2: Descrizione geometrica del raddoppio di un punto su una curva
ellittica.
CAPITOLO 2. CONCETTI GENERALI 14
Si dimostra che la somma tra punti di E ha tutte le proprieta` forma-
li dell’addizione (associativa, commutativa, esistenza dell’opposto, esistenza
dell’elemento neutro).
Esistono delle formule esplicite, di tipo razionale, che permettono di im-
plementare algebricamente le operazioni suddette; per approfondimenti si
rimanda al Paragrafo 3.2.
I sistemi crittografici basati sulle curve ellittiche sono di due tipi. Un tipo,
analogo a RSA, la cui sicurezza e` basata sul problema della fattorizzazione
intera (Algoritmo di Lenstra, [32]) e ha interesse solo da un punto di vista
accademico in quanto non offre alcun vantaggio rispetto a RSA. L’altro,
analogo ai sistemi basati sul problema del logaritmo discreto [19], e` molto
piu` interessante da un punto di vista pratico; la sua sicurezza trae origine
dal problema seguente: dati due punti P e Q su una curva ellittica, tali
che Q = kP , trovare l’intero k; questo problema e` chiamato il problema del
logaritmo discreto su curve ellittiche.
Attualmente, i metodi per calcolare il logaritmo discreto su curve ellitti-
che generiche sono molto meno efficienti di quelli per il calcolo del logaritmo
discreto convenzionale (cioe` in GF ∗(pn)) o per la fattorizzazione intera. Di
conseguenza il logaritmo discreto su curve ellittiche trova applicazione in
diversi contesti, in particolare nella dualita` di Tate e quindi nella Crittogra-
fia Basata su Identita` (IBE). In genere i migliori attacchi a questi sistemi
crittografici sono quelli a forza bruta.
E’ dimostrato che, per certe curve, il problema del logaritmo discreto su
curve ellittiche puo` essere ricondotto al problema del logaritmo discreto con-
venzionale; in questi casi occorrono chiavi della stessa dimensione di quelle
utilizzate dai metodi crittografici a chiave pubblica convenzionali; ma questi
casi sono conosciuti e facilmente eludibili. Inoltre, alcune curve, note come le
curve di Koblitz, danno luogo ad implementazioni molto veloci, ma potreb-
bero consentire attacchi specializzati [19]. Ad ogni modo, esistono famiglie
di curve ellittiche attualmente considerate sicure [19].