I cifrari a chiave pubblica:
Introduzione alle curve ellittiche
Monica Bianchini
[email protected]
I cifrari a chiave pubblica  1
 Se l’uso di tecniche crittografiche per proteggere i
documenti è antico quanto la scrittura stessa, solo
l’avvento del computer ha permesso la realizzazione
pratica dei sistemi crittografici di nuova concezione,
basati su principi impossibili da applicarsi con sistemi
manuali o meccanici
 Si tratta di una nuova classe di cifrari che godono di
importanti proprietà:
• sono molto sicuri, ma al contempo facili da gestire
• sono immuni dai principali problemi dei sistemi di
crittografia classici, primo fra tutti quello della gestione e
distribuzione delle chiavi
• sono in grado di fornire “servizi” aggiuntivi quali la firma
elettronica e la certificazione del mittente
I cifrari a chiave pubblica  2
 Tutti si basano sul concetto di chiave asimmetrica, del
tutto assente nella crittografia classica
 Infatti, lo svantaggio principale dei metodi a chiave
privata è che richiedono la comunicazione della chiave
fra mittente e ricevente, su un canale sicuro, prima della
trasmissione di qualsiasi messaggio cifrato…
• POTREBBE ESSERE MOLTO DIFFICILE DA REALIZZARE!
 Per esempio, se i corrispondenti vivono lontani e
decidono di comunicare via email, non avranno accesso
a nessun canale ragionevolmente sicuro per lo scambio
della chiave
I cifrari a chiave pubblica  3
Cifrario simmetrico
Cifrario asimmetrico
I cifrari a chiave pubblica  4
 Le basi teoriche della crittografia moderna risalgono a
meno di 40 anni fa, a partire dal 1969, con le prime
ricerche di James Ellis, del quartier generale governativo
delle comunicazioni britanniche (GCHQ)
 L’idea dei crittosistemi a chiave pubblica è dovuta a
Withfield Diffie e Martin Hellman (1976), mentre la prima
realizzazione pratica si ha l’anno successivo, ad opera di
Ronald Rivest, Adi Shamir e Leonard Adleman, ricercatori
al MIT (Massachusetts Institute of Technology) che
formularono RSA
I cifrari a chiave pubblica  5
 Diffie
ed Hellman, pubblicarono un lavoro teorico
fondamentale nel quale, ipotizzando di poter disporre di
un cifrario asimmetrico, dimostravano la fattibilità di
sistemi crittografici di nuovo tipo, adatti alla crittografia
di massa, basati sull’impiego di chiavi pubbliche
 Con i cifrari a chiave pubblica si inizia a parlare di strong
encryption, crittografia forte
 Nella pratica, un cifrario a chiave pubblica è dotato di
due chiavi distinte, che sono una l’ “inversa” dell’altra: se
una viene usata per la cifratura, la seconda deve essere
usata in decifratura, e viceversa
 Punto fondamentale del crittosistema è che le due chiavi
devono essere indipendenti: ossia la conoscenza di una
delle due chiavi non deve dare alcuna informazione utile
alla ricostruzione dell’altra
I cifrari a chiave pubblica  6
 I crittosistemi a chiave pubblica rendono il calcolo di dk,
a partire da ek, computazionalmente irrealizzabile  ek
può essere resa pubblica
 Il mittente potrà inviare il messaggio cifrato utilizzando
ek, ma solo il ricevente autorizzato sarà in grado di
decifrarlo, poiché sarà l’unico a conoscere dk
I cifrari a chiave pubblica  7
 Vantaggi
• La chiave pubblica può essere trasmessa tramite un
canale insicuro, in quanto la sua conoscenza da parte di
terzi non è sufficiente a mettere in pericolo la sicurezza
dei dati cifrati con essa; ciascuna chiave segreta resta
sotto la responsabilità del solo utente proprietario
• In un sistema a chiave segreta per ogni possibile coppia di
utenti deve esistere una chiave: per n utenti occorrono
n(n1)/2 chiavi
• In un sistema a chiave pubblica, deve esistere una coppia
di chiavi per ogni possibile utente, ovvero per n utenti
occorrono 2n chiavi
I cifrari a chiave pubblica  8
 Svantaggi
• Gli algoritmi simmetrici e quelli asimmetrici necessitano di
chiavi di lunghezza diversa per raggiungere lo stesso
grado di sicurezza teorica
• Generalmente, gli algoritmi asimmetrici sono molto più
lenti da eseguire, rispetto a quelli simmetrici, e pertanto di
uso poco agevole per la cifratura di messaggi lunghi
I cifrari a chiave pubblica  9
 Dal 1977, sono stati formalizzati diversi crittosistemi a
chiave pubblica, la cui sicurezza è affidata alla difficoltà
di risoluzione di problemi matematici diversi
 RSA (1977)  la sicurezza è basata sulla difficoltà nella
fattorizzazione di interi “grandi”
 MerkleHellman Knapsack (1978)  la sicurezza del
sistema è basata sulla NPcompletezza del problema
della somma di sottoinsiemi
• Dato un insieme di interi, è possibile enucleare un
sottoinsieme di somma nulla?
• Tutti i crittosistemi di questo tipo si sono rivelati insicuri,
tranne il crittosistema di ChorRivest
I cifrari a chiave pubblica  10
 McEliece (1978)  è basato sulla teoria algebrica dei
codici, ed è a tutt’oggi ritenuto sicuro; la sicurezza è
dovuta alla difficoltà del problema di decodificare un
codice lineare (che è NPcompleto)
 ElGamal (1984)  la sicurezza è basata sulla difficoltà
del calcolo del logaritmo discreto in campi finiti
 Curve ellittiche  sono crittosistemi che traggono
origine da sistemi tipo ElGamal, ma operano sulle curve
ellittiche piuttosto che sui campi finiti; sono i sistemi più
sicuri, anche per chiavi piccole
I cifrari a chiave pubblica  11
 I sistemi a chiave pubblica non possono garantire la
sicurezza incondizionata, poiché una spia, essendo
venuta in possesso di un testo cifrato y, può codificare
ogni possibile testo in chiaro x, utilizzando ek, che è
pubblica, fino a trovare l’unico x tale che y=ek(x)

Per i sistemi a chiave pubblica è sensato studiare la
“sicurezza computazionale”
 A questo scopo, può essere concettualmente utile
pensare ad un sistema a chiave pubblica, in termini
astratti, come ad una funzione unidirezionale
I cifrari a chiave pubblica  12
 La funzione pubblica di codifica ek deve essere semplice
da calcolare, ma difficile da invertire, per tutti tranne che
per il ricevente: una funzione siffatta è una funzione
oneway (unidirezionale)
 ek deve essere una funzione iniettiva e oneway
 Le funzioni unidirezionali giocano un ruolo fondamentale
nella costruzione di crittosistemi a chiave pubblica
 Sfortunatamente, anche se vi sono varie classi di
funzioni che sono ritenute unidirezionali, non esiste per
nessuna di esse una prova certa
I cifrari a chiave pubblica  13
 Sia n il prodotto di due numeri primi “grandi”, p e q, e sia
b un intero positivo
 : ZnZn definita da
(x) = xb (mod n)
è ritenuta essere una funzione unidirezionale (e, di fatto,
è la funzione di codifica in RSA)
 Tuttavia,
l’essere oneway non è una proprietà
sufficiente per , poiché il ricevente autorizzato deve
essere in grado di decifrare i messaggi in maniera
efficiente
I cifrari a chiave pubblica  14
 Il ricevente deve possedere una trapdoor  una sorta di
canale preferenziale, una “scappatoia”  che gli permetta
di accedere rapidamente all’informazione codificata, cioè
di decifrare facilmente il testo cifrato, grazie alla sua
conoscenza di informazione aggiuntiva su k
 ek deve essere iniettiva, oneway, trapdoor
Riassumendo...
 I principali problemi sui quali si basano i sistemi
crittografici moderni sono:
• Il problema della fattorizzazione di interi grandi (Integer
Factorization Problem – IFP )
• Il problema del calcolo del logaritmo discreto su campi
finiti (Discrete Logarithm Problem – DLP )
• Il problema del calcolo del logaritmo discreto su curve
ellittiche (Elliptic Curve Discrete Logarithm Problem –
ECDLP )
I campi vettoriali  1
 Un campo è un insieme G che soddisfa le seguenti
proprietà:
• Sono definite due operazioni, genericamente indicate con
•
•
•
•
•
+ e  (e che nel caso dei reali/complessi sono
effettivamente la somma e il prodotto)
La somma ed il prodotto sono operazioni interne al campo
Valgono le proprietà commutativa e associativa per
somma e prodotto
Vale la proprietà distributiva tra prodotto e somma (sia
destra che sinistra)
Esiste, ed è unico, l’elemento neutro, sia per la somma che
per il prodotto (0 ed 1, rispettivamente)
Per ciascun elemento del campo, esiste l’elemento inverso
relativamente a somma e prodotto (l’opposto per la
somma, il reciproco per il prodotto)
I campi vettoriali  2
 La cardinalità dell’insieme G viene indicata con |G| ed è
chiamata ordine del campo: se questa è finita allora G è
un campo finito
 Sia Zn={0, 1, 2, 3, ... , n1} un campo finito
• Se n=pq, dove p è un numero primo e q un intero positivo,
p e q sono detti rispettivamente caratteristica e grado di
estensione del campo
• g è un generatore per il campo finito Zn se ogni elemento
di Zn può essere scritto come potenza di g (escluso lo 0)
Il crittosistema RSA  1
 RSA è realizzato in Zn, dove n è il prodotto di due numeri
primi distinti p e q  (n)=(p1)(q1) (numero degli
interi positivi minori di n primi con n)
Sia n =pq, con p e q numeri primi. Siano P=C=Zn
Sia K ={(n,p,q,a,b): n =pq, p,q primi, ab1 (mod (n))}
Per k=(n,p,q,a,b):
ek(x) = xb (mod n)
dk(y) = ya (mod n)
x,y  Zn
I valori di n e b sono pubblici, p,q ed a segreti
Il crittosistema RSA  2
 Le operazioni di codifica e decodifica sono inverse
poiché ab1 (mod (n)), ab=t(n)+1, per
qualche intero t  1
 Infatti,
 Sia Zn* l’insieme dei residui modulo n primi con n
 Sia xZn*, allora…
(xb)a  xt(n)+1 (mod n)  (x(n))t x (mod n)
 1t x (mod n)  x (mod n)
(x(n)=1 per il teorema di Eulero che asserisce che Zn* è
un gruppo moltiplicativo di ordine (n))
Esempio di sistema RSA insicuro  1
 Supponiamo che siano p=101 e q=113  n=11413 e
(n)=100112=11200
 Poiché 11200=26527, un intero b può essere utilizzato
quale esponente di codifica se e solo se b non è divisibile
per 2, 5 o 7
 Il proprietario della chiave privata non fattorizzerà (n),
verificherà solo che
l’algoritmo di Euclide
MCD((n),b)=1
utilizzando
 Supponiamo che scelga b=3533; allora l’algoritmo di
Euclide calcola b1=6597 (mod 11200)  l’esponente di
decodifica è a=6597
Esempio di sistema RSA insicuro  2
 Il proprietario della chiave privata pubblica n=11413 e
b=3533
 Supponiamo che il suo corrispondente voglia inviargli il
testo 9726, egli calcolerà
97263533 (mod 11413)=5761
ed invierà il testo cifrato 5761 sul canale
 Quando
il proprietario della chiave privata riceve
y=5761, utilizza l’esponente di decifratura segreto a per
calcolare
57616597 (mod 11413)=9726
Sicurezza di RSA
 La sicurezza del crittosistema RSA è basata sulla
“speranza” che ek(x)=xb (mod n) sia oneway, così da
rendere computazionalmente impossibile, per una spia,
decrittare il testo cifrato
 La scappatoia (trapdoor) che permette al proprietario
della chiave privata di decifrare il crittogramma è
costituita dalla conoscenza della fattorizzazione di n=pq
 Dato che il proprietario della chiave privata conosce p e
q, può calcolare (n)=(p1)(q1) e quindi l’esponente di
decifratura a, utilizzando l’algoritmo di Euclide esteso
Il logaritmo discreto  1
 La potenza di un numero in aritmetica finita si definisce
come
ab=x (mod n)
 Come
nell’aritmetica ordinaria, è possibile definire
un’operazione inversa rispetto all’esponente: il logaritmo
 Per definizione, il logaritmo è l’esponente a cui si deve
elevare la base a per ottenere il valore x:
b=loga x (mod n)
Tale logaritmo si dice logaritmo discreto
 Se il calcolo della potenza è relativamente semplice, il
calcolo del logaritmo è computazionalmente molto
complesso, può avere più soluzioni o nessuna
Il logaritmo discreto  2
 Per esempio, in Z7, si ha:
20 = 1
21 = 2
22 = 4
23 = 1
24 = 2
25 = 4
26 = 1
e quindi, il log24 è pari a 2 ma anche a 5; viceversa non
esistono log23, log25, log26
 In generale, si ritiene che il problema del calcolo del
logaritmo discreto sia “difficile” come il problema della
fattorizzazione di numeri grandi, anche se non esiste
attualmente una dimostrazione dell’asserto
Metodo di DiffieHellman
per lo scambio di chiavi  1
 È realizzato in Zn, con n numero primo e g generatore di
Zn, e si basa sulla difficoltà di calcolo dell’intero k tale
che p=gk (mod n), noti p, g, ed n
 Alice e Bob vogliono scambiarsi un messaggio
• Siano n e g due numeri interi che soddisfano le seguenti
proprietà:
 n è un numero primo grande (100200 cifre)
 g<n
 MCD(g,n1)=1: g e n primi fra loro
 n e g noti ad Alice e Bob
• Alice sceglie keyprivAlice=a<n e calcola h=ga (mod n)
• Bob sceglie keyprivBob=b<n e calcola k=gb (mod n)
Metodo di DiffieHellman
per lo scambio di chiavi  2
 Alice e Bob pubblicano rispettivamente keypubAlice=h e
keypubBob=k
 Alice calcola keyAliceBob=ka (mod n) e la usa come chiave
per crittare i messaggi diretti a Bob
 Bob calcola keyBobAlice=hb (mod n) e la usa come chiave
per crittare i messaggi diretti ad Alice
 keyAliceBob=keyBobAlice ?
ka (mod n)=(gb (mod n))a (mod n)=gba (mod n)
=gab (mod n)=(ga (mod n))b (mod n)
=hb (mod n)
 k_s=keyAliceBob=keyBobAlice è la chiave di sessione
Metodo di DiffieHellman
per lo scambio di chiavi  3
 Dopo che Alice e Bob hanno generato una chiave di
sessione, possono scambiarsi messaggi utilizzando un
qualsiasi cifrario simmetrico
 Il metodo di DiffieHellman è di fatto un protocollo
“sicuro” per lo scambio di chiavi, da utilizzarsi in
crittosistemi simmetrici
 Ma… quanto “sicuro” ?
• Il problema del calcolo del logaritmo discreto è
computazionalmente intrattabile con la potenza di calcolo
attuale, almeno per n intero “sufficientemente grande” 
lungo qualche centinaio di bit
Il crittosistema di ElGamal
 ElGamal è realizzato in Zn, con n numero primo e g
generatore di Zn
Sia n un numero primo. Siano P=C=Zn
Sia K ={(n,g,a,c,b,d,h): g generatore di Zn, a=gc, b=gd}
Per k=(n,g,a,c,b,d,h):
(gh (mod n), ek(x)=xbh (mod n))
dk(y) = (gh (mod n))d (y (mod n))
x,y  Zn
I valori di n, g, a, e b sono pubblici, c, d ed h segreti
Crittografia e curve ellittiche
 Negli ultimi tempi l’interesse degli appassionati di teoria
dei numeri verso le curve ellittiche è andato crescendo,
forse a causa del loro impiego per la famosa
dimostrazione dell’ultimo teorema di Fermat da parte di
Andrew Wiles
 I cifrari basati sulle curve ellittiche furono proposti in
maniera indipendente da Victor Miller e Neal Koblitz
verso la metà degli anni ottanta
 Le curve ellittiche possono interpretarsi come una
“versione analogica” del concetto di gruppo moltiplicativo
in un campo finito
 Per comprendere come questa particolare classe di
cubiche possa essere impiegata per costruire una
categoria di metodi crittografici, attualmente ritenuti i più
sicuri, occorre introdurne le proprietà matematiche
fondamentali
Le curve ellittiche  1
o Definizione 1
Sia K un campo di caratteristica p2,3 e sia x3+ax+b,
con a,bK, un polinomio cubico privo di radici multiple;
una curva ellittica su K è l’insieme costituito dalle coppie
(x,y) con x,yK che soddisfano l’equazione
y2=x3axb
più un punto isolato O, detto punto all’infinito
 Se p=2, l’equazione delle curve ellittiche può assumere
le due forme…
y2cy=x3axb
curva supersingolare
y2xy=x3axb
curva non supersingolare
 …e per p=3
y2=x3ax2bxc
Le curve ellittiche  2
Grafici delle curve ellittiche sul campo  di
equazione (a) y2=x3x, (b) y2=x31, (c) y2=x35x6
Le curve ellittiche  3
o Definizione 2
Sia E una curva ellittica su , e siano P e Q punti di E; si
definiscono l’opposto di P e la somma PQ, in base alle
seguenti regole
• Se P coincide con il punto all’infinito O, allora P=O e
PQ=Q, cioè O è l’elemento neutro per l’addizione di punti
• Altrimenti, l’opposto P di P è il punto con ascissa x uguale
a quella di P ed ordinata opposta, cioè P=(x,y)
• Se Q=P, PQ= O
Le curve ellittiche  4
• Se P e Q hanno ascisse distinte, allora r= PQ interseca la
curva E esattamente in un ulteriore punto R (se r non è
tangente ad E in P, nel qual caso R=P, o in Q, così che
R=Q); se R è distinto da P e Q, PQ=R.
Le curve ellittiche  5
• Se P=Q, sia t la tangente alla curva in P e sia R (l’unico)
ulteriore punto di intersezione di t con la curva, allora
PQ=2P=R
Le curve ellittiche  6
 Come si calcolano le coordinate di PQ ?
• Se P=(x1,y1) e Q=(x2,y2) con x1x2, sia y=x l’equazione
della retta r per P e Q (che non è verticale); in questo
caso, =(y2y1)/(x2x1) e =y1x1; i punti di r, (x,x),
giacciono anche sulla curva ellittica E se e solo se
soddisfano l’uguaglianza x3(x)2axb=0
• Due soluzioni dell’equazione cubica sono note e
corrispondono ai punti P e Q; poiché in un polinomio
monico di grado n, la somma delle radici coincide con il
coefficiente del termine di grado n1, 2=x1x2x3, da
cui…
x3=[(y2y1)/(x2x1)]2x1x2
e
y3= y1[(y2y1)/(x2x1)](x1x3)
Le curve ellittiche  7
• Se
P=Q,
=dy/dx=[f(x,y)/x]/[f(x,y)/y]|P,
f(x,y)=y2(x3axb), cioè =(3x12  a)/2y1, da cui…
e
con
x3=[(3x12  a)/2y1]2 2x1
y3= y1[(3x12  a)/2y1](x1x3)
 I punti di una curva ellittica E formano un gruppo
abeliano relativamente all’operazione di somma
 Come in ogni gruppo abeliano, si userà la notazione nP,
per indicare l’operazione di somma del punto P con se
stesso effettuata n volte, se n>0, ovvero la somma di P
con se stesso effettuata n volte, per n negativo
 Per definizione, il punto all’infinito O rappresenta il “terzo
punto di intersezione” delle rette verticali con la curva E
Curve ellittiche su campi finiti
 Sia K il campo finito Zn, costituito da n = pq elementi
 Sia E una curva ellittica definita su Zn
 E è composta da al più 2n1 punti, il punto all’infinito O
e 2n coppie (x,y)ZnZn, ovvero per ciascuna delle n
possibili ascisse xZn esistono al più 2n ordinate yZn
che soddisfano l’equazione di E
In realtà, vale il seguente…
o Teorema di Hasse
Sia N il numero di punti in Zn appartenenti ad una curva
ellittica E, definita su Zn; vale la disuguaglianza
|N  (n1)| 2n
Da plaintext a punti su E  1
 Supponiamo di codificare il plaintext x come un intero r
 Sia E una curva ellittica definita su Zn, con n=pq, numero
intero “grande” e dispari
 Un metodo probabilistico (non esistono algoritmi deterministici
per risolvere questo problema!) per codificare r mediante Pr
può essere schematizzato come segue:
• Si sceglie k (≤50 è sufficiente); sia 0≤r<R, e n>Rk
• Gli interi compresi fra 1 ed Rk possono essere scritti nella forma
rkj, con 1≤j<k  si stabilisce una corrispondenza biunivoca fra
detti interi ed un sottoinsieme degli elementi di Zn
• Per esempio, ciascun numero 1≤i<Rk può essere scritto come un
intero ad s cifre in base p, ciascuna cifra del quale rappresenta il
relativo coefficiente di un polinomio di grado s1, corrispondente
ad un elemento di Zn
Da plaintext a punti su E  2
 Pertanto, dato r, per ogni 1≤j<k, si ottiene un elemento
xcZn, coincidente con rkj
 Per tale xc, si calcola y2=xc3axcb, e si cerca di estrarre
la radice quadrata per calcolare il corrispondente valore
di yc
• Se si riesce a calcolare un yc, tale che yc2=f(xc), si ottiene
Pr=(xc, yc)
• Se invece tale yc non esiste, allora si incrementa j di
un’unità e si riprova a calcolare yc a partire xc=rkj1
Da plaintext a punti su E  3
 Posto di riuscire a trovare un xc t.c. esiste yc calcolato
come sopra, per j≤k, r può essere ricalcolato da
Pr=(xc,yc) come r=[(x1)k)], con xcx (mod n) e x Zn
 Poiché f(x) è un quadrato in Zn approssimativamente nel
50% dei casi (tale probabilità vale esattamente N/2n,
che è molto vicino ad ½), la probabilità che il metodo
proposto fallisca nel calcolare il punto Pr la cui coordinata
xc è compresa fra rk1 e rkk è  2k
Crittosistemi su curve ellittiche  1
 I vantaggi dei crittosistemi costruiti attraverso curve
ellittiche rispetto ai codici su campi finiti sono:
• Gran numero di gruppi abeliani (costituiti dai punti di una
curva) che si possono costruire su uno stesso campo finito
• Non esistenza di algoritmi subesponenziali per risolvere il
problema del logaritmo discreto su curve non
supersingolari
• Chiavi più corte per garantire lo stesso grado di sicurezza
Crittosistemi su curve ellittiche  2
 Le curve ellittiche permettono di formulare un problema
analogo a quello del logaritmo discreto su un campo
finito (DLP, Discrete Logarithm Problem)
 Problema
Siano dati una curva ellittica E su Zn ed un punto BE; il
problema del logaritmo discreto su E in base B (ECDLP,
Elliptic Curve Discrete Logarithm Problem) è
dato PE trovare, se esiste, xZ tale che xB=P
Crittosistemi su curve ellittiche  3
 Osservazioni
• Per i campi finiti esiste un algoritmo, detto index calculus,
che permette di calcolare il logaritmo discreto (ovvero di
risolvere il DLP) con complessità subesponenziale
• Tale algoritmo si fonda sulla definizione delle operazioni di
somma e prodotto, e quindi non è applicabile sulle curve
ellittiche che possiedono esclusivamente una struttura
additiva
• La sicurezza dei crittosistemi su curve ellittiche risiede
nell’attuale non conoscenza di algoritmi subesponenziali
per risolvere l’ECDLP
• Esistono tuttavia algoritmi subesponenziali per particolari
classi di curve ellittiche (in particolare per le curve
supersingolari)
DiffieHellman su curve ellittiche
 Supponiamo che Alice e Bob vogliano accordarsi su una
chiave segreta da utilizzare per un crittosistema classico
1)
2)
3)
4)
5)
Alice e Bob devono fissare un campo finito Zn, dove n=pr, ed
una curva ellittica E definita su questo campo
Il passo successivo consiste nel rendere pubblico un punto
BE, detto base (che avrà un ruolo analogo al generatore g nel
caso del DiffieHellman classico); non è necessario che B sia
un generatore di E, ma si suppone che abbia ordine o
“sufficientemente” grande
Alice sceglie un numero a costituito dallo stesso numero di cifre
(o), che terrà segreto, ed invia pubblicamente a Bob la
quantità aB
Allo stesso modo, Bob sceglie b dello stesso ordine di
grandezza ed invia ad Alice la quantità bB
Entrambi possono calcolare abB che servirà da chiave segreta
Esempio
 Sia data la curva ellittica y2=x3x1 e il suo punto B(1;1)
 Alice sceglie a=2, calcola aB e lo pubblica  aB=(2;3)
 Bob sceglie b=3, calcola bB e lo pubblica  bB= (13;47)
 La chiave segreta è abB, cioè il punto di coordinate
7082/2209 e 615609/103823
ElGamal su curve ellittiche
 Viene fissata una curva ellittica E su un campo Zn ed un
punto BE
 Ogni utente sceglie un intero casuale a, che
rappresenterà la sua chiave segreta, e pubblica aB
 Se Alice vuole spedire a Bob il messaggio ME, si attua
il protocollo seguente
1) Alice sceglie un intero casuale k ed invia a Bob la coppia
(kB, Mk(bB)), dove (bB) e la chiave pubblica di Bob
2) Bob può decodificare il messaggio originale calcolando
M=Mk(bB)b(kB)
utilizzando la propria chiave segreta b
 È evidente che un intruso che sapesse risolvere il
problema ECDLP potrebbe ricavare b e da questo risalire
al paintext
PGP  1
“What one man can invent another can discover.” [Sherlock Holmes]
The Adventure of the Solitary Cyclist, Sir Arthur Conan Doyle
 Il programma PGP (Pretty Good Privacy, Philip R.
Zimmerman, 1991) è a chiave pubblica e utilizza il
seguente protocollo di comunicazione:
• Un
utente invia la propria chiave pubblica ad un
corrispondente; l’eventuale intercettazione è irrilevante;
chiunque vi abbia accesso, infatti, può spedire posta cifrata
al proprietario della chiave privata, ma una volta effettuata
la cifratura di un messaggio, nemmeno l’autore è in grado
di rileggerlo
• Il corrispondente codifica il messaggio con la chiave
pubblica ricevuta e lo invia al proprietario della chiave; se
anche il messaggio venisse intercettato, solo il legittimo
destinatario, in possesso della chiave privata, è in grado di
decifrarlo
PGP  2
 Chiave di sessione
• Poiché la cifratura asimmetrica è molto più lenta della
crittografia simmetrica, la tecnologia PGP utilizza un
approccio ibrido al problema della sicurezza:
 Il messaggio viene inizialmente cifrato con un algoritmo
di cifratura a chiave segreta (IDEA o CAST): viene
automaticamente
creata
una
chiave
casuale
temporanea, detta chiave di sessione, che viene
utilizzata per cifrare soltanto quel documento
 La chiave di sessione viene a sua volta cifrata mediante
la chiave pubblica del ricevente (RSA o DiffieHellman)
• Quando
il messaggio giunge a destinazione, il
ricevente utilizza la propria chiave privata per
decifrare la chiave di sessione, che poi impiega per
decifrare il messaggio
PGP  3
 Firma digitale
• Per essere certo della provenienza di un messaggio, il
destinatario può richiedere al mittente di apporre al
messaggio la propria firma digitale, utilizzando la
propria chiave privata: viene così creato un file cifrato
che non può essere duplicato in alcun modo
• Chiunque sia in possesso della chiave pubblica del
mittente può leggere la firma ed identificare la
provenienza del messaggio
• Un documento, cui sia stata apposta una firma
digitale, non può essere falsificato, né disconosciuto
• La possibilità di autenticare la provenienza e la
sicurezza dei messaggi digitali hanno aperto la strada
all’ecommerce: la cifratura e le firme digitali, infatti,
hanno reso “sicuri” i pagamenti via Internet tramite
carta di credito