Le Curve Ellittiche in Crittografia
Alessandro Berti
[email protected]
Universitá degli Studi di Padova
12/03/2012
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
1 / 90
INTRODUZIONE
Le CURVE ELLITTICHE (CE o EC) sono uno strumento molto potente
nel ramo della CRITTOGRAFIA.
Sono considerate ”difficili da attaccare”, tanto che il governo americano,
per cifrare i segreti piú importanti, si basa su esse.
Lo studio di algoritmi basati su CE é iniziato nel 1985 grazie a Miller e a
Koblitz.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
2 / 90
INTRODUZIONE
In questa presentazione, si introdurrá:
1
Cosa sono le curve ellittiche
2
Alcuni algoritmi per la crittografia basati su curve ellittiche
3
Tecniche per lo studio della primalitá e della fattorizzazione mediante
curve ellittiche
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
3 / 90
DEFINIZIONE DI CE
Sia K un campo (per esempio, K = R o K = Q o K = C o K = Fq con
q = p r ).
La definizione di curva ellittica dipende dalla caratteristica del campo in
questione
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
4 / 90
DEF. CE (caso ch(K ) 6= 2, 3)
Sia x 3 + ax + b un polinomio senza radici multiple.
Definizione
Una CURVA ELLITTICA su K é l’insieme dei punti (x, y ) ∈ K 2 che
soddisfano l’equazione
y 2 = x 3 + ax + b
Insieme ad un singolo elemento O chiamato ”punto all’infinito”.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
5 / 90
DEF. CE (caso ch(K ) = 2)
Definizione
Una CURVA ELLITTICA su K é l’insieme dei punti che soddisfano a una
delle due equazioni
y 2 + cy = x 3 + ax + b
y 2 + xy = x 3 + ax 2 + b
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
6 / 90
DEF. CE (caso ch(K ) = 3)
Definizione
Una CURVA ELLITTICA su K é l’insieme dei punti che soddisfano
all’equazione
y 2 = x 3 + ax 2 + bx + c
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
7 / 90
SOMMARE I PUNTI
Un fatto importante riguardante le CURVE ELLITTICHE é che i loro
punti formano un gruppo abeliano.
Per il momento assumiamo che K = R, cosı́ che la curva ellittica sia una
curva sul piano (piú un altro punto O).
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
8 / 90
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
9 / 90
SOMMARE I PUNTI
Definizione
Sia E una curva ellittica su K = R e siano P, Q due punti su E .
Definiamo il negativo di P e la somma P + Q secondo le regole
1
Se P é O, −P é O e P + Q é Q; ció vuol dire che O é l’elemento
zero di quel gruppo di punti.
Se P 6= O e Q 6= O
2
Il negativo −P é il punto con la stessa coordinata x ma con
coordinata y cambiata −(x, y ) = (x, −y ).
3
Se P e Q hanno x uguale, la linea l = PQ interseca la curva in un
altro punto R. Allora poniamo P + Q = −R.
4
Se Q = −P allora P + Q = O.
5
Se P = Q, sia l la linea tangente alla curva in P, e R il punto di
intersezione di l con la curva, e si ponga P + Q = −R.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
10 / 90
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
11 / 90
IL PUNTO ALL’INFINITO
É l’elemento ”nullo” del gruppo abeliano (per definizione).
Visivamente, possiamo collocarlo infinitamente in alto.
É il ”terzo punto di intersezione” di ogni linea verticale con la curva.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
12 / 90
FORMULE PER LA SOMMA
Data una CE y 2 = x 3 + ax + b e due punti distinti P e Q, siamo
interessati a trovare una formula ”esplicita” per la somma.
1
Sia y = mx + q retta passante per i due punti (m = yx22 −y
−x1 , q = y1 − mx1 ).
Allora possiamo scrivere P = (x1 , mx1 + q) e Q = (x2 , mx2 + q). Vogliamo
trovare P + Q = (x3 , y3 ).
Consideriamo allora il sistema di equazioni
(
y 2 = x 3 + ax + b
y = mx + q
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
13 / 90
FORMULE PER LA SOMMA
Il sistema precedente ci conduce a un’equazione del terzo grado
x 3 − (mx + q)2 + ax + b = 0
Di questo polinomio, conosciamo giá due radici, x1 e x2 (i punti
corrispondenti stanno sia sulla curva che sulla retta). Vogliamo trovare x3 .
Sfruttiamo il fatto che la somma delle radici di un polinomio di terzo grado
é uguale a meno il coefficiente del termine di secondo grado per ottenere
2
x3 = m − x1 − x2 =
y2 − y1
x2 − x1
2
− x1 − x2
Quindi
y3 = −y1 +
y2 − y1
x2 − x1
(x1 − x3 )
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
14 / 90
FORMULE PER LA SOMMA
Abbiamo visto nelle slides precedenti delle formule per la somma di due
punti distinti P e Q. Ma se volessimo fare P + P?
Ci sarebbe da trovare l’equazione della tangente alla curva, e trovare
l’altro punto di intersezione con la curva. Procediamo per differenziazione
implicita, trovando che
dy /dx =
3x12 + a
2y1
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
15 / 90
FORMULE PER LA SOMMA
Allora le formule viste prima si scrivono
2
3x12 + a
x3 =
− 2x1
2y1
2
3x1 + a
y3 = −y1 +
(x1 − x3 )
2y1
Dato n ∈ N, é allora possibile definire la quantitá nP = P + P + . . . + P
per n volte.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
16 / 90
CURVE ELLITTICHE SUI RAZIONALI
Le curve algebriche su Q godono di un’interessante proprietá
Teorema
(di Mordell) Il gruppo abeliano di una curva algebrica su Q é finitamente
generato.
Questo significa che abbiamo un sottogruppo di torsione (i punti di ordine
finito) finito piú un sottogruppo generato da un numero finito di punti di
ordine infinito.
Il numero di generatori che servono per la parte infinita é chiamato il
rango r .
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
17 / 90
L’ORDINE DI UN PUNTO
Precisiamo cosa intendiamo per ordine.
Definizione
L’ordine N di un punto P su una curva ellittica é il piú piccolo intero
positivo tale che NP = O; tale N non deve per forza esistere.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
18 / 90
CAMPI FINITI
Mettiamoci ora a lavorare su K = Fq .
É chiaro sin da subito che le CE su Fq possono avere al massimo 2q + 1
punti; cioé il punto all’infinito piú altri 2q punti, che possono essere dati da
1
2
preso x ∈ Fp , si calcoli x 3 + ax + b (si puó sempre fare!)
√
si prenda y = ± x 3 + ax + b
Tuttavia, non sempre si puó estrarre la radice quadrata!
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
19 / 90
RESIDUI QUADRATICI
Definizione
Un numero n é chiamato residuo quadratico modulo p se esiste un intero
x tale che
x 2 ≡ n (mod p)
In caso contrario, n é detto essere un non-residuo quadratico.
Se p é un numero primo dispari, allora metá dei numeri 1, 2, . . . , p − 1
sono residui e metá non-residui quadratici. Questo perché i residui
quadratici si ottengono calcolando b 2 modulo p per 1 ≤ b ≤ (p − 1)/2.
Gli altri quadrati si ripetono in ordine inverso.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
20 / 90
SIMBOLO DI LEGENDRE
Il simbolo di Legendre é definito come segue:
Se p é un numero primo e a é un intero, allora
a
p
é uguale a:
1
0 se p divide a
2
1 se a é un quadrato modulo p - ossia esiste un intero k tale che
k 2 ≡ a (mod p)
3
−1 se a non é un quadrato modulo p, cioé a é un non-residuo
quadratico modulo p
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
21 / 90
PROPRIETÁ DEL SIMBOLO DI LEGENDRE
Il simbolo di Legendre possiede un certo numero di proprietá che
consentono di velocizzare i calcoli. Le piú importanti sono:
ab
b
1
= pa
p
p
1
2
p =1
−1
3
= (−1)(p−1)/2
p
2
(p 2 −1)/8
4
p = (−1)
q
p
(p−1)(q−1)/4
5
p = q (−1)
L’ultima proprietá prende il nome di legge di reciprocitá quadratica.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
22 / 90
IL SIMBOLO DI JACOBI
Il simbolo di Jacobi é una generalizzazione del simbolo di Legendre che
utilizza la scomposizione in fattori primi dell’argomento inferiore. É
definito come segue:
Sia n > 2 un numero naturale dispari e n = p1α1 p2α2 . . . pkαk . Per ogni intero
a, il simbolo di Jacobi é
αk
a a α1 a α2
a
=
...
n
p1
p2
pk
dove
porre
a
p
n
1
con p primo é il simbolo di Legendre. Si conviene inoltre di
= 1.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
23 / 90
IL SIMBOLO DI JACOBI
Notiamo che se na = −1, allora a non é un residuo quadratico di n
perché
non é residuo quadratico di qualche fattore di n. Inoltre, se
a
=
0,
allora (a, n) > 1. Tuttavia, se na = 1 non si puó dedurre che a
n
sia un residuo quadratico di n perché é possibile che un numero pari di
fattori di n siano non-residui, e quindi il prodotto dei loro simboli di
Legendre valga ugualmente 1.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
24 / 90
ALGORITMO DI TONELLI-SHANKS
L’algoritmo di Tonelli-Shanks é usato con l’aritmetica modulare per
risolvere una congruenza della forma
x 2 ≡ n (mod p)
dove n é un residuo quadratico (modp) e p é un primo dispari.
Tonelli-Shanks non puó essere usato per moduli composti.
L’algoritmo funziona cosı́:
INPUT: p, un numero primo dispari. n,un residuo quadratico (mod p),
che significa che il simbolo di Legendre pn = 1.
OUTPUT: R, un intero che soddisfa R 2 ≡ n.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
25 / 90
ALGORITMO DI TONELLI-SHANKS
1
2
Tira fuori le potenze di 2 da p − 1, definendo Q e S come
p − 1 = Q2S con Q dispari.
Si selezioni z tale che il simbolo di Legendre pz = −1 (z dovrebbe
essere un non-residuo quadratico modulo p) e si ponga c ≡ z Q .
3
4
Sia R ≡ n(Q+1)/2 , t = nQ e M = S.
Ripeti:
- se t ≡ 1, ritorna R
i
- altrimenti, trova il piú piccolo i, 0 < i < M, tale che t 2 ≡ 1
M−i−1
, e si ponga R ≡ Rb, t ≡ tb 2 , c ≡ b 2 e M = i.
- sia b ≡ c 2
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
26 / 90
APPROCCIO CLASSICO
tic
p = 20996011;
% p \equiv 3 mod 4
% x = 13371337 x^2 mod p = 8708486
n = 8708486;
for i=1:p-1
t = mod(i^2,p);
if (t == n)
break;
end
end
i
toc
Elapsed time is 3.272411 seconds.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
27 / 90
APPROCCIO CON TONELLI-SHANKS
Definiamo anzitutto una funzione potenza ”efficiente”, che ci permetta di
calcolarle modulo p in fretta. Per esempio, invece di calcolare a23
moltiplicando a per 23 volte, questo metodo calcola anzitutto a2 , a4 , a16 e
poi moltiplica a ∗ a2 ∗ a4 ∗ a16 .
function P = pot_mod(a,m,p)
P=1; M=m; A=a;
while (M > 0)
q = floor(M/2); r = M - 2*q;
if (r==1) P = mod(P*A,p); end
M=q; A=mod(A^2,p);
end
end
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
28 / 90
APPROCCIO CON TONELLI-SHANKS
tic
p = 20996011;
n = 8708486; z = 20996010; S=0; Q=p-1;
while (mod(Q,2) == 0) Q=Q/2; S=S+1; end
c = pot_mod(z,Q,p); R = pot_mod(n,(Q+1)/2,p);
t = pot_mod(n,Q,p); M = S;
while (mod(t,p) ~= 1)
tt = t; while (mod(tt,p) ~= 1) tt = pot_mod(tt,2,p); end
b = pot_mod(c,pot_mod(2,(M-i-1),p),p); R = mod(R*b,p);
c = mod(b^2,p); M = i;
end
R
toc
Elapsed time is 0.107229 seconds.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
29 / 90
N DI PUNTI DI UNA CE IN Fq
Prima avevamo detto che una curva ellittica in Fq non poteva
(oggettivamente!) avere piú di 2q + 1 punti.
Ma c’era il problema delle radici: visto che solo metá degli elementi di Fq
ammettono radice quadrata, ci si aspetta che N sia piú o meno metá degli
elementi.
Chiamiamo ora χ(x) = qx il simbolo di Jacobi.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
30 / 90
N DI PUNTI DI UNA CE IN Fq
Il numero di soluzioni y ∈ Fq all’equazione y 2 = u é uguale a 1 + χ(u), e
allora la curva ellittica avrá un numero di punti pari a (contando anche il
punto all’infinito!)
1+
X
(1 + χ(x 3 + ax + b)) =
x∈Fq
=q+1+
X
χ(x 3 + ax + b)
x∈Fq
Ci aspettiamo che χ(x 3 + ax + b) possa essere, con la stessa frequenza,
+1 e −1.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
31 / 90
N DI PUNTI DI UNA CE IN Fq
Possiamo trattare il problema come quello di una ”passeggiata casuale”.
Tira una moneta q volte, fai un passo avanti quando esce 1, fai un passo
indietro quando esce −1.
Per il Calcolo delle Probabilitá, dopo q tiri ti troverai ad una distanza
√
dall’origine mediamente pari a q.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
32 / 90
N DI PUNTI DI UNA CE IN Fq
La somma
aleatoria.
P
χ(x 3 + ax + b) si comporta un po’ come una passeggiata
Teorema
(di Hasse) Sia N il numero di punti di una curva ellittica su Fq . Allora
√
|N − (q + 1)| ≤ 2 q
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
33 / 90
LA CONGETTURA DI WEIL
Consideriamo una CE su Fq , che ha N punti.
Sia Fqr estensione di Fq e consideriamo la stessa CE sul nuovo campo.
Essa avrá un numero di punti pari a Nr .
Sia z la seguente serie
z(T ; E /Fq ) = e
P
Nr T r /r
dove T é tale 0 ≤ T < q1 .
Questa serie si chiama la funzione zeta della curva ellittica.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
34 / 90
LA CONGETTURA DI WEIL
La congettura di Weil ci dice che la funzione precedente assume una forma
molto speciale
Teorema
(Congettura di Weil) La funzione zeta é una funzione razionale nella
forma
Z (T ; E /Fq ) =
1 − dT + qT 2
(1 − T )(1 − qT )
dove d é un’opportuna costante.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
35 / 90
SOMMARE I PUNTI IN Fq
Ricordiamo le formule per la somma di punti di CE su R
y2 − y1 2
− x1 − x2
x3 =
x2 − x1
y2 − y1
y3 = −y1 +
(x1 − x3 )
x2 − x1
Si possono applicare anche su Fq ?
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
36 / 90
INVERSI MODULARI
1
Il problema é il termine m = yx22 −y
−x1 . Dopo aver eliminato i fattori in
comune, puó succedere che il denominatore sia diverso da 1.
In tal caso, per calcolare m si deve calcolare l’inverso del denominatore in
Fq .
Come si puó fare? Si puó trovare un’identitá di Bezout tramite
l’algoritmo di Euclide esteso.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
37 / 90
ALGORITMO DI EUCLIDE ESTESO
Dati due numeri, m e n, m > n, se ne vuole scrivere l’identitá di Bezout.
Si trovano delle successioni {qk }k , {rk }k , {nk }k tali che, posto n1 = m e
n2 = n abbiamo:
n1 = q1 n2 + r1
n2 = q2 n3 + r2
...
nm = qm nm+1 + rm
nm+1 = qm+1 nm+2 + 0
rm é l’ultimo resto non nullo. É il Massimo Comun Divisore tra m e n
e nk = rk−2 .
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
38 / 90
ALGORITMO DI EUCLIDE ESTESO
Poi si torna a ritroso nel procedimento trovando l’identitá di Bezout.
Esempio
Si vuole calcolare l’identitá di Bezout tra 97 e 29. Abbiamo
97 = 3 ∗ 29 + 10
29 = 2 ∗ 10 + 9
10 = 9 ∗ 1 + 1
9=9∗1
Quindi MCD(97, 29) = 1. Costruiamo ora l’identitá di Bezout. Abbiamo
1 = 10 − 1 ∗ 9 =
= 10 − 29 + 2 ∗ 10 = 3 ∗ 10 − 29 =
= 3 ∗ (97 − 3 ∗ 29) − 29 = 3 ∗ 97 − 10 ∗ 29
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
39 / 90
INVERSI MODULARI
Nell’esempio precedente, dati 97 e 29, si é trovato che
3 ∗ 97 − 10 ∗ 29 = 1
I numeri 3 e 10 si chiamano inversi modulari e sono tali che
3 ∗ 97 ≡ 1 (mod 29)
−10 ∗ 29 ≡ 1 (mod 97)
Abbiamo trovato un modo per invertire i denominatori in Fq !
Ci basta calcolare l’inverso modulare di (x2 − x1 ) modulo q, quindi é
sufficiente usare l’algoritmo di Euclide esteso per trovare un’identitá di
Bezout tra (x2 − x1 ) e q.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
40 / 90
REALIZZAZIONE ALG. EUCLIDE ESTESO
function [x,y] = ide_bez(a,b)
n(1)=a; n(2)=b;
q(1)=floor(n(1)/n(2)); r(1)=mod(n(1),n(2)); i=1;
while (r(i) ~= 0) n(i+2)=r(i); i=i+1;
q(i)=floor(n(i)/n(i+1)); r(i)=mod(n(i),n(i+1)); end
i=i-1; x=1; y=-q(i);
while (i>=2)
i=i-1; temp=x; x=y; y=temp-q(i)*y; end
end
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
41 / 90
SOMMARE I PUNTI SU Fq
function [x,y] = sum_pts(x1,y1,x2,y2)
% consideriamo la curva ell. su F_q; y^2 = x^3 + x + 1
q=5; a=1;
% se (x1,y1) \’e il punto all’infinito, allora la somma e’ l’a
if (x1==0 && y1==0) x=x2; y=y2; return; end
% se (x2,y2) \’e il punto all’infinito, allora la somma e’ l’a
if (x2==0 && y2==0) x=x1; y=y1; return; end
% se le ascisse coincidono ma le ordinate no,
% allora la somma \’e il punto all’infinito
if (x1==x2 && y1~=y2) x=0; y=0; return; end
if (x1==x2 && y1==y2)
if (mod(2*y1,q)==1) B=1; end
if (mod(2*y1,q)~=1) [A,B] = ide_bez(q,mod(2*y1,q)); end
m = mod((3*x1^2 + a)*B,q); end
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
42 / 90
SOMMARE I PUNTI SU Fq
if (x1~=x2)
if (mod(x2-x1,q)==1) B=1; end
if (mod(x2-x1,q)~=1) [A,B] = ide_bez(q,mod(x2-x1,q)); end
m = mod((y2-y1)*B,q); end
x = mod(m^2 - x1 - x2,q);
y = mod(-y1 + m*(x1-x),q);
end
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
43 / 90
MOLTIPLICARE I PUNTI SU Fq
x1=2;
y1=1;
x=0;
y=0;
for i=1:4
x2=x;
y2=y;
[x,y] = sum_pts(x1,y1,x2,y2)
end
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
44 / 90
MOLTIPLICARE I PUNTI SU Fq
Riepilogando:
- Abbiamo definito l’algoritmo di Euclide esteso per poter invertire gli
elementi in Fq
- Abbiamo definito la funzione che somma i punti, in tutti i casi possibili
(ascisse coincidenti, . . . )
- Per moltiplicare un punto per se stesso, abbiamo ripetuto per n volte
l’operazione di somma.
Visto che Fq é un campo finito, l’ordine di ogni elemento é finito. Per
esempio, prendendo P = (2, 1) che stá sulla curva ellittica y 2 = x 3 + x + 1
otteniamo la seguente sequenza:
(2, 1)
(2, 4)
(0, 0)
(2, 1) . . .
Quindi l’ordine di (2, 1) é 2.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
45 / 90
CRITTOGRAFIA
Vogliamo capire come ”celare” un testo in chiaro tramite l’uso di curve
ellittiche.
APPROCCIO INGENUO: Si associa a ogni testo in chiaro un numero
m, si calcola x = m3 + am + b e si cerca di estrarre la radice trovando y .
Tuttavia, non é affatto detto che tale radice esista . . .
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
46 / 90
CRITTOGRAFIA
APPROCCIO SENSATO: Sia k > 1 intero fissato, m numero
corrispondente al nostro testo in chiaro.
Si provano a trovare le radici quadrate di x = f (km + j)
(f (ξ) = ξ 3 + aξ + b) dove j é un intero che puó andare da 0 a k − 1.
Finché se ne trova una che esiste!
Allora avremmo individuato un punto (x, y ) sulla nostra curva ellittica che
corrisponde a m.
Il metodo precedente aveva probabilitá 1/2 di successo. Questo metodo ha
una probabilitá 1 − 2−k di successo.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
47 / 90
CIFRATURA DOUBLE-LOCK
A parole possiamo descriverla cosı́:
1
Lucy vuole mandare un regalo a Charlie; lo mette in una scatola e ci
appone un lucchetto (che solo lei puó aprire)
2
Charlie riceve il pacco; non puó aprirlo, ci appone un altro lucchetto
(che solo lui puó aprire) e lo rimanda a Lucy.
3
Lucy riceve il pacco, rimuove il proprio lucchetto e rimanda tutto a
Charlie. Sul pacco sará rimasto solo il lucchetto di Charlie.
4
Charlie puó rimuovere l’ultimo lucchetto; ha il suo regalo!
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
48 / 90
CIFRATURA DOUBLE-LOCK
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
49 / 90
COME FARE LA DOUBLE-LOCK CON LE CE
Supponiamo di avere una CE su Fq che sia Lucy che Charlie conoscono.
Sia N il numero di punti della CE .
Lucy sceglie una chiave di cifratura, chiamiamola eA , che é un intero
coprimo con N, e supponiamo voglia mandare ”come regalo” il punto P a
Charlie. Allora calcola eA P (prodotto di punti sulla CE) e lo manda a
Charlie.
Charlie riceve eA P che non puó decifrare. Che fa? Genera una propria
chiave di cifratura eB e la applica al punto eA P ottenendo eB eA P.
Manda eB eA P a Lucy.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
50 / 90
COME FARE LA DOUBLE-LOCK CON LE CE
A questo punto, Lucy riceve eB eA P. Lucy sará in possesso di una chiave
di decifrazione dA che applica a eB eA P per ottenere eB P. Manda eB P a
Charlie!
Charlie sará in possesso della propria chiave di decifrazione dB che
applica a eB P per ottenere P.
Charlie ha ottenuto P!
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
51 / 90
PROBLEMI
1
Data una chiave di cifratura e, come si trova la chiave di decifrazione
d?
2
Data una chiave di cifratura e, é davvero cosı́ facile calcolare eP?
3
In tutti i passaggi, abbiamo supposto di conoscere il numero N dei
punti della CE . É un conto che possiamo fare in tempi ragionevoli?
4
Come facciamo a essere sicuri che la chiave e sia ”sicura”, ossia non
esistano attacchi che in breve tempo consentano di decifrarla?
5
Supponiamo che la chiave e sia ”sicura” e che ”uno” intercetti la
comunicazione, e abbia ad esempio P ed eP. In quanto tempo puó
arrivare a conoscere la chiave e?
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
52 / 90
P.1: TROVARE CHIAVE DECIFRAZIONE
Supponiamo di avere una chiave di cifratura e. Come troviamo la chiave
di decifrazione d?
Sia N il numero di punti della curva ellittica. Sappiamo che per ogni P
abbiamo NP = O, dove O é il punto all’infinito, quindi (N + 1)P = P.
Ci é dunque sufficiente trovare d tale che
ed ≡ 1 (mod N)
Questo puó essere fatto trovando un’identitá di Bezout tra N ed e tramite
l’algoritmo di Euclide esteso.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
53 / 90
P.2: CALCOLARE eP
Usare il metodo visto in precedenza (eP = P + . . . + P) puó risultare
dispendioso se la chiave e é grande.
Possiamo usare un metodo simile a quello che abbiamo usato per elevare a
potenze ”grandi” modulo p. In pratica, si continua a dividere per 2
memorizzando i resti e poi, tornando a ritroso, si moltiplica il punto per 2,
aggiungendo poi il P originario se il resto é 1.
Per esempio, vogliamo calcolare 10P. Abbiamo 10 = 5 ∗ 2 + 0,
5 = 2 ∗ 2 + 1, 2 = 2 ∗ 1 + 0. Prendiamo il P originario, moltiplichiamolo
per 2, moltiplichiamo quanto ottenuto per 2, aggiungiamo a questo il P
originario, e moltiplichiamo il tutto per 2.
10P = 2 ∗ (P + 2 ∗ (2P))
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
54 / 90
P.3: CALCOLARE N
Data una CE su Fq , c’é un modo per calcolare il numero di punti di essa?
Un approccio plausibile potrebbe essere quello di prendere ogni x ∈ Fq e
vedere se ammette o meno radici quadrate.
Prima abbiamo visto l’algoritmo di Tonelli-Shanks per il calcolo della
radice quadrata. Ma a noi in questo momento interessa solo sapere se la
radice c’é o non c’é.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
55 / 90
P.3: CALCOLARE N
Possiamo semplicemente applicare questo fatto.
Teorema
Sia n elemento non nullo di Zq . Allora n é un residuo quadratico se e solo
se
n(q−1)/2 ≡ 1 (mod q)
Dimostrazione
Se n ≡ x 2 mod q allora
n(q−1)/2 ≡ x 2(q−1)/2 ≡ x q−1 ≡ 1 mod q
per il piccolo teorema di Fermat . . .
Ció comporta, per ogni elemento di Zq , di dover calcolare la potenza
(q − 1)/2-esima . . .
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
56 / 90
P.3: CALCOLARE N. MAPPA DI FROBENIUS
Definiamo φq : E (Fq ) → E (Fq ) come
φq ((x, y )) = (x q , y q )
Questa mappa é un endomorfismo. Per vedere che mappa punti della
curva ellittica in punti della curva ellittica, ricordiamo che vale questo fatto
Teorema
Vale che (x + y )q ≡ x q + y q (mod q)
Dimostrazione
Abbiamo che
q
q
q
(x + y ) = x + y +
q−1 X
q
k=1
E ogni
q
k
k
x q−k y k
che compare nella sommatoria ha q a fattore.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
57 / 90
P.3: CALCOLARE N. MAPPA DI FROBENIUS
Se un punto (x, y ) soddisfa l’equazione
y 2 ≡ x 3 + ax + b (mod q)
Allora
y 2q ≡ (x 3 + ax + b)q (mod q)
Ma per quanto appena visto
(x 3 + ax + b)q ≡ (x q )3 + aq x q + b q
≡ (x q )3 + ax q + b (mod q)
Quindi
(y q )2 ≡ (x q )3 + ax q + b (mod q)
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
58 / 90
P.3: CALCOLARE N. ALGORITMO DI RENÉ-SCHOOF
La mappa di Frobenius ha una proprietá molto utile.
√
Sia N = #E (Fq ) = q + 1 − t dove |t| ≤ 2 q per il teorema di Hasse
(quello che diceva che il numero di punti di una CE si comportava piú o
meno come una passeggiata aleatoria).
Siamo interessati a trovare t.
La mappa di Frobenius φq e t soddisfano la seguente equazione
φ2q − tφq + q = 0
∀ P ∈ E (Fq )
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
59 / 90
P.3: CALCOLARE N. ALGORITMO DI RENÉ-SCHOOF
Intravediamo la luce: ora, l’algoritmo di Schoof prevede che si determini il
valore di t mod pi per un insieme di primi tali che
Y
√
K=
pi > 4 q
Il teorema cinese del resto é applicato per trovare l’unico t mod K tale che
√
|t| ≤ 2 q.
Ora che conosciamo t possiamo calcolare l’ordine del gruppo,
N = #E (Fq ) = q + 1 − t.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
60 / 90
P.4: ASSICURARCI DELLA SICUREZZA DI e
Abbiamo appena visto come calcolare N. N é tale che NP = O per ogni
punto P della curva.
Ma potrebbero esistere n < N tali che nP = O, ossia l’ordine di P é n.
Se un hacker prova varie chiavi di decifrazione d e per caso ed ≡ kn + 1
con k intero, cos’é che ottiene? Ottiene il messaggio in chiaro. Questo
con una probabilitá N/n volte maggiore rispetto alla probabilitá originaria
di trovare d.
Per essere sicuri che ció non accada, basta che il numero N di punti della
nostra CE in Fq sia un numero primo.
In tal caso, per il teorema di Lagrange l’ordine di ogni elemento deve
dividere N che é primo, quindi deduciamo che l’ordine debba essere N.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
61 / 90
ESEMPI: CALCOLO DI N (METODO INEFF.)
% ce y^2 = x^3 + x + 1 su F_8191
function y = n_pti()
tic
q = 8191; n_pts = 1; % il pto all’inf.
for i=0:q-1
A = mod(i^3,q); B = mod(A + i + 1,q);
if (B==0) n_pts = n_pts + 1; end
if (B~=0) C= pot_mod(B,(q-1)/2,q);
if (C==1) n_pts = n_pts + 2; end end end
y = n_pts;
toc
end
N = 8301 Elapsed time is 7.844067 seconds.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
62 / 90
ESEMPI: SCELTA DELLA CHIAVE e
% generazione chiave
N = n_pti();
e = N;
while (gcd(N,e)~=1)
e = floor(rand()*N);
end
e
e = 1054
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
63 / 90
ESEMPI: TROVARE d
N = n_pti();
e = 1054;
[A,B] = ide_bez(N,e);
d = mod(B,N)
N = 8301, e = 1054, d = 6907
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
64 / 90
ESEMPI: CODIFICA
% codifica veloce!
tic
e = 1054; x1 = 0; y1 = 1; x = 0; y = 1; A = 1; i = 0;
while (A<e)
i=i+1; B(i) = mod(floor(e/A),2); A = A*2;
end
j=i-1;
while (j>=1) x2=x; y2=y; [x,y]=sum_pts(x2,y2,x2,y2);
if (B(j)==1) x2=x; y2=y; [x,y]=sum_pts(x1,y1,x2,y2); end
j=j-1;
end
x, y
toc
(0, 1) → (1688, 7420)
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
65 / 90
ESEMPI: DECODIFICA
% decodifica veloce!
tic
d = 6907; x1 = 1688; y1 = 7420; x = 1688; y = 7420; A = 1; i =
while (A<d)
i=i+1; B(i) = mod(floor(d/A),2); A = A*2;
end
j=i-1;
while (j>=1) x2=x; y2=y; [x,y]=sum_pts(x2,y2,x2,y2);
if (B(j)==1) x2=x; y2=y; [x,y]=sum_pts(x1,y1,x2,y2); end
j=j-1;
end
x, y
toc
(1688, 7420) → (0, 1)
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
66 / 90
P.5.: PROBLEMA DEL LOGARITMO DISCRETO
Prendiamo come esempio la cifratura double-lock. Un malitenzionato
ascolta la discussione ed é a conoscenza di eA P, eB eA P e eB P.
Se si riuscisse, dati eA P ed eB eA P, a trovare eB , allora si riuscirebbe a
trovare anche dB e da eB P si potrebbe calcolare P (il punto non cifrato!)
Il problema del logaritmo discreto su curve ellittiche consiste nel
determinare n intero tale che
nP = Q sulla curva ellittica.
Questo non é un assolutamente un problema facile da risolvere.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
67 / 90
P.5.: PROBLEMA DEL LOGARITMO DISCRETO
Ricordiamo il problema del logaritmo discreto su un gruppo moltiplicativo.
Problema
Trovare x tale che
g x ≡ h (mod q)
Anche questo problema non é facile da risolvere. Tuttavia, conosciamo
alcuni algoritmi che ci permettono di risolverlo.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
68 / 90
P.5.: ALGORITMO INDEX-CALCULUS
L’algoritmo richiede una base di fattorizzazione come input. La base di
fattorizzazione é usualmente scelta in modo da essere il numero −1 e i
primi r primi partendo da 2. L’algoritmo é eseguito in tre fasi.
PRIMA FASE: si cercano di trovare r relazioni linearmente indipendenti.
Ogni relazione contribuisce a una equazione di un sistema lineare in r
incognite. Come si cercano le relazioni? Per k=1,2,. . . si cerca di
fattorizzare g k mod q usando la base di fattorizzazione: si trovano ei tali
che g k ≡ (−1)e0 2e1 . . . prer . Ogni volta che una fattorizzazione é trovata,
crea un vettore (e0 , e1 , . . . , er , k) (relazione). Se questa relazione é
linearmente indipendente dalle altre relazioni, aggiungila alla lista delle
relazioni e se ci sono almeno r + 1 relazioni, abbiamo finito.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
69 / 90
P.5.: ALGORITMO INDEX-CALCULUS
SECONDA FASE: Si considera la matrice le cui righe sono le relazioni.
Si riduce la matrice a una matrice unitaria (si risolve il sistema!). Ora, il
primo elemento dell’ultima colonna é il logaritmo discreto di −1, il
secondo elemento é il logaritmo discreto di 2 e cosı́ via.
TERZA FASE: Per s = 0, 1, 2, . . . si prova a fattorizzare g s h nella base di
fattorizzazione g s h = (−1)f0 2f1 . . . p fr . Appena si trova una
fattorizzazione, abbiamo trovato l’output che é
x = f0 logg (−1) + f1 logg (2) + . . . + fr logg (pr ) − s
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
70 / 90
P.5.: PROBLEMA DEL LOGARITMO DISCRETO
Ci chiediamo se possiamo ridurre il problema del logaritmo discreto su
curve ellittiche nP = Q a un problema di logaritmo discreto su un gruppo
moltiplicativo g x ≡ h (mod q).
La risposta é affermativa: si riesce a trovare una mappa che va da un
sottogruppo di punti della curva ellittica in un opportuno prodotto di
gruppi della forma Z∗n × Z∗nd , dove n e d sono opportuni interi.
Questo risultato é dovuto a Weil, e ci permette di applicare le tecniche
conosciute (come l’Index-Calculus) alle curve ellittiche.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
71 / 90
ATTACCO MAN-IN-THE-MIDDLE
La cifratura double-lock sembra un modo sicuro di corrispondenza. Se la
cifratura é effettuata con le CE, vista la difficoltá di risolvere il log
discreto, il tutto sembra assumere i connotati dell’inviolabilitá.
Tuttavia, c’é una falla: supponiamo che una terza persona C
(malitenzionata!) riesca a filtrare, ed eventualmente bloccare, la
corrispondenza tra A e B. A vuole mandare P a B, allora calcola eA P e lo
indirizza verso B. Peró C si inserisce e blocca il transito verso B. C
applica la sua chiave eC per ottenere eC eA P, e lo rimanda ad A.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
72 / 90
ATTACCO MAN-IN-THE-MIDDLE
A riceve eC eA P. Credendo sia stato B a rimandarglielo, si sente sicuro nel
togliere eA con dA . Poi rimanda, verso B, eC P. C intercetta e blocca il
messaggio, usa dC e ottiene P.
Questo ci dice come la cifratura double-lock, da sola, non sia sufficiente ad
assicurarci la sicurezza. É opportuno pensare a metodi come la firma
digitale per avere caratteristiche come l’autenticitá e l’integritá.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
73 / 90
CRITTOSISTEMA DI ELGAMAL
É un sistema per lo scambio di messaggi tramite un canale insicuro.
La sua realizzazione si compie in tre passaggi
FASE 1 - GENERAZIONE CHIAVE: É fatta da uno dei due
interlocutori, supponiamo Lucy. Prendiamo un punto P su una CE C .
Generiamo un intero casuale a e calcoliamo A = aP. La chiave pubblica é
(C , P, A).
FASE 2 - CIFRATURA MESSAGGIO: Charlie riceve la chiave pubblica
(C , P, A) di Lucy. Charlie sceglie un intero casuale b e si calcola la chiave
segreta condivisa K = bA(= baP) e B = bP. A questo punto, puó
mandare messaggi a Lucy.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
74 / 90
CRITTOSISTEMA DI ELGAMAL
Supponiamo che il messaggio sia Q. Allora Charlie manda a Lucy la coppia
(B, K + Q)
FASE 3 - DECIFRAZIONE MESSAGGIO: Lucy, per trovare Q, si
calcola la chiave segreta condivisa K = aB(= abP) e svolge il calcolo
(K + Q) − K → Q
L’algoritmo funziona perché entrambi si trovano la stessa chiave.
Adesso ”chi sta in mezzo” non puó piú fare niente, se non provare a
risolvere il problema del logaritmo discreto
Dati P e A, trovare a.
Dati P e B, trovare b.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
75 / 90
PRIMALITÁ E FATTORIZZAZIONE
Vedremo un paio di tecniche che si basano sulle CE per risolvere i seguenti
problemi:
1
Dato un numero n, stabilire se n é primo
2
Dato un numero n che sia composto, produrne una fattorizzazione
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
76 / 90
IDEE DI BASE
L’idea, in entrambi i casi, é quella di prendere un’equazione di CE
y 2 = x 3 + ax + b
E prenderla modulo n, dove n non é necessariamente primo, e vedere cosa
succede applicando i metodi consueti di somma dei punti e conta del
numero di primi (René-Schoof).
Potremmo non poter procedere nei calcoli, oppure trovare delle conclusioni
che non sarebbero vere se n fosse primo . . .
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
77 / 90
PRIMALITÁ
Per il problema della primalitá, esistono metodi molto buoni che non sono
trasportabili nel mondo delle CE, per esempio il metodo di Miller-Rabin
(sia nella versione probabilistica che in quella deterministica che fa uso
della GRH) e l’AKS.
Analizzeremo una tecnica, che non é stata concepita sulle CE,
trasportabile, pur senza benefici immediati, nel mondo delle CE.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
78 / 90
TEST DI PRIMALITÁ
Teorema
Sia n intero. Supponiamo esista q >
esiste un intero a tale che:
1
an−1 ≡ 1 (mod n)
2
MCD(a
n−1
q
√
n − 1 primo tale che q|n − 1. Se
− 1, n) = 1
allora n é primo.
Dimostrazione
√
Se n non é primo, allora esiste primo p ≤ n t.c. p|n. Visto che
q > p − 1, segue che MCD(q, p − 1) = 1 e quindi esiste u tale che
n−1
uq
(n−1)
q
≡ au(n−1) (mod p)
uq ≡ 1 (mod (p − 1)). Segue che a q ≡ a
grazie alla condizione 1), e quindi questo contraddice la condizione 2).
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
79 / 90
TEST DI PRIMALITÁ SU CE
Teorema
Sia n intero positivo. Sia E l’insieme dato dall’equazione y 2 = x 3 + ax + b
modulo n. Sia m un intero. Supponiamo che esista un primo q che divide
m che é piú grande di (n1/4 + 1)2 . Se esiste un punto P di E tale che:
1
mP = O
2
(m/q)P é definito e non é uguale a O
Allora n é primo.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
80 / 90
TEST DI PRIMALITÁ SU CE
Proponiamo la dimostrazione, che é concettualmente simile a quella vista
in precedenza.
Dimostrazione
√
Se n non é primo, allora esiste primo p ≤ n t.c. p|n. Sia E 0 la CE data
dalla stessa equazione di E ma considerata modulo p, e sia m0 l’ordine del
√
gruppo E 0 . Per il teorema di Hasse, abbiamo m0 ≤ p + 1 + 2 p
√
= ( p + 1)2 ≤ (n1/4 + 1)2 < q e quindi MCD(q, m0 ) = 1, ed esiste un
intero u tale che uq ≡ 1 (mod m0 ). Sia P 0 ∈ E 0 il punto P considerato
modulo p. Allora in E 0 abbiamo (m/q)P 0 = uq(m/q)P 0 = umP 0 = O, da
1), dato che mP 0 é ottenuto usando la stessa procedura di mP, cambia
solo che lavoriamo modulo p|n invece che modulo n. Ma questo
contraddice 2), dato che se (m/q)P é definito e 6= O modulo n, allora la
stessa procedura che lavora in modulo p invece che modulo n darebbe
(m/q)P 0 6= O.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
81 / 90
TEST DI PRIMALITÁ SU CE
Questo ci suggerisce un algoritmo per verificare la primalitá.
Sia P = (x, y ) un punto. Per a scelto, si determina l’equazione di CE
passante per P (bata porre b = y 2 − x 2 − ax).
1) Si considera l’ ”ipotetica” CE modulo n, e se ne calcola il numero di
punti m tramite l’algoritmo di René-Schoof. Se l’algoritmo fallisce allora n
é composto.
2) Si provi a scrivere m = kq dove q é un ”probabile primo” e k é un
intero piccolo. Se ció non riesce, si cambiano a e P e si riparte dal punto 1)
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
82 / 90
TEST DI PRIMALITÁ SU CE
3) Si provano a calcolare kQ e mP.
- se mP 6= O allora n é sicuramente composto (perché se n fosse primo, il
gruppo avrebbe ordine m, e ogni elemento di E sarebbe ”ucciso” dalla
moltiplicazione per m).
- se kP = O, caso molto sfortunato, siamo costretti a ripartire dall’inizio.
- se mP = O e kP 6= O, allora sappiamo che n é primo, supposto che q
fosse davvero primo.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
83 / 90
TEST DI PRIMALITÁ SU CE
Questo riduce il problema al provare la primalitá di q, che é circa n/2.
Quindi ripartiamo con lo stesso test con q al posto di n.
Questo é un procedimento iterativo, che termina in non piú di log2 n
iterazioni.
Il test di cui abbiamo parlato non ha applicazioni ”pratiche” e si preferisce
il test ”semplice” visto in precedenza. Questo perché
1
Per calcolare m bisogna applicare l’algoritmo di René-Schoof, che é
dispendioso.
2
Non é cosı́ frequente che m si possa scrivere nella forma m = kq con
k intero piccolo e q quasi primo.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
84 / 90
FATTORIZZAZIONE
Il problema della fattorizzazione é ancora piú importante: sulla sua
infallibilitá poggia per esempio il sistema RSA.
Anche qui si ci ispira a una tecnica di fattorizzazione non basata su CE,
per poi arrivare a una tecnica basata su CE.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
85 / 90
ALGORITMO ρ − 1 DI POLLARD
INPUT: numero n composto OUTPUT: p fattore primo |n
1
Scegli un intero k che é multiplo di tutti gli interi piú piccoli di un
certo B. Per esempio k = B!
2
Si sceglie un intero a tra 2 e n − 2. Per esempio a = 2 o a = 3.
3
Calcola ak mod n (col metodo delle potenze ripetute)
4
Calcola d = MCD(ak − 1, n) usando l’algoritmo Euclideo.
5
Se d = 1 o d = n, fai una nuova scelta di k
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
86 / 90
ALGORITMO ρ − 1 DI POLLARD
Per spiegare come funziona, supponiamo che p sia un divisore di n tale che
p − 1 sia un prodotto di primi tutti minori di B. Allora segue che k é un
multiplo di p − 1 e allora, per il piccolo teorema di Fermat, abbiamo
ak ≡ 1 mod p. Allora p|MCD(ak − 1, n).
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
87 / 90
METODO DI LENSTRA
1
Si prende un punto P (modulo n) si considera una CE (modulo n) che
lo contenga (si sceglie a e poi si pone b = y 2 − x 2 − a)
2
Si sceglie un intero e che é multiplo di tutti gli interi minori di un
certo numero B. Si calcola eP.
3
- se siamo stati capaci di finire tutti i calcoli senza problemi, allora
dobbiamo ripartire con qualche altra curva e punto di partenza.
- se troviamo kP = O in qualche passaggio allora dobbiamo, anche in
questo caso, ripartire con una nuova curva.
- se incontriamo un denominatore tale che MCD(v , n) non é né 1 né
n, allora MCD(v , n) divide n.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
88 / 90
METODO DI LENSTRA
Perché questo metodo funziona?
Se n = pq, allora y 2 = x 3 + ax + b (mod n) implica che la stessa
equazione valga anche modp e modq. Queste due curve ellittiche piú
piccole sono gruppi ”genuini”. Se questi gruppi hanno Np e Nq elementi
rispettivamente, allora per il teorema di Lagrange kP = O sulla curva
(modp) implica che k divide Np ; dunque Np P = O. Un’affermazione
analoga vale per q. Quando la curva ellittica é scelta in modo casuale,
allora Np e Nq sono numeri casuali vicini a p + 1 e q + 1 rispettivamente.
Dunque é improbabile che la maggioranza dei fattori primi di Np e Nq
sono gli stessi, ed é probabile che, quando calcoliamo eP, si incontra un
certo kP che é O (mod p) ma non (mod q), o viceversa. Se questo é il
caso, kP non esiste sulla curva originaria, e nei calcoli troviamo qualche v
con MCD(v , p) = p o MCD(v , q) = q, ma non entrambi. Quindi
gcd(v , n) é un fattore non-triviale di n.
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
89 / 90
BIBLIOGRAFIA
1
N. Koblitz, A course in Number Theory and Cryptography, second
ed., Springer-Verlag, 1994
2
John J. McGee, Ren Schoofs Algorithm, Thesis submitted to the
faculty of the Virginia Polytechnic Institute
3
Victor S. Miller, The Weil Pairing and Its Efficient Calculation,
Communicated by Arjen K. Lenstra
Alessandro Berti [email protected] (Universitá
Le Curve Ellittiche
degli Studi
in Crittografia
di Padova)
12/03/2012
90 / 90