Courbes elliptiques et cryptographie
Robert Rolland
[email protected]
C.N.R.S., Institut de Math ematiques de Luminy F13288 Marseille cedex 9, France
Courbes elliptiques et cryptographie p. 1
II-1. Cryptographie elliptique
La cryptographie elliptique repose sur le problme de logarithme discret et problmes connexes dans le groupe des points dune courbe elliptique sur un corps ni. On va donc sintresser aux questions suivantes : courbe elliptique sur un corps ni. la structure de groupe. cryptosyst` emes bas es sur les courbes elliptiques.
Courbes elliptiques et cryptographie p. 2
II-1.1 Courbe elliptique
Une courbe elliptique sur un corps ni Fq est une courbe plane sans points singuliers sur Fq , dquation afne y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 . Si on se place dans le plan projectif lquation devient Y 2 T + a1 XY T + a3 Y T 2 = X 3 + a2 X 2 T + a4 XT 2 + a6 T 3 . ` linni, le point La courbe a donc un point a O = (0 : 1 : 0).
Courbes elliptiques et cryptographie p. 3
II-1.1 Courbe elliptique (suite)
Aprs changement de variable rationnel, lquation de la courbe est Cas dun corps de caract erisique 2 : Cas non supersingulier : y 2 + xy = x3 + ax2 + b Cas supersingulier : y 2 + cy = x3 + ax + b (c = 0) (b = 0)
Courbes elliptiques et cryptographie p. 4
II-1.1 Courbe elliptique (suite)
Cas dun corps de caract erisique 3 : Cas non supersingulier : y 2 = x3 + ax2 + b Cas supersingulier : y 2 = x3 + ax + b (a = 0) Cas dun corps de caract erisique = 2, 3 : y 2 = x3 + ax + b (4a3 + 27b2 = 0). (ab = 0)
Courbes elliptiques et cryptographie p. 5
II-1.1 Courbe elliptique (suite)
Il y a deux quantits trs importantes associes une quation du type y + a1 xy + a3 y = x + a2 x + a4 x + a6 . Le discriminant : il indique si la courbe est sans point singulier sur le corps Fq . Le j-invariant : qui dnit des classes de courbes "isomorphes".
2 3 2
Courbes elliptiques et cryptographie p. 6
II-1.1.1 Le discriminant
Le discriminant est dnit par = o d2 = a2 1 + 4a2 d4 = 2a4 + a1 a3 d6 = a2 3 + 4a6
2 2 d8 = a2 a + 4 a a a a a + a a a 2 6 1 3 4 2 3 1 6 4 2 d2 d8
3 8d4
27d2 6 + 9d2 d4 d6
Courbes elliptiques et cryptographie p. 7
II-1.1.2 Le j-invariant
Le j-invariant est dni par c3 j= 4 o c4 = d2 2 24d4
Courbes elliptiques et cryptographie p. 8
II-1.2 La structure de groupe
Les points rationnels dune courbe elliptique E (i.e. les points de la courbe coordonnes dans Fq ) forment un groupe commutatif. On prend comme lment neutre le point linni O (mais a pourrait tre nimporte quel point de la courbe). et on dnit P +Q=R en construisant R = D(P, Q) E puis R = D(R , O) E . (Lorsque M = N la droite D(M, N ) est la tangente en M la courbe E ).
Courbes elliptiques et cryptographie p. 9
II-1.2 La structure de groupe (suite)
Avec cette dnition lopration est bien commutative, associative, ayant O pour lment neutre. Supposons que la courbe soit donne par son quation gnrale de Weierstrass y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 . Si P = (x1 , y1 ) = O alors P = (x1 , y1 + a1 x1 + a3 ). On se rend compte aussi que P + Q = R . Posons Q = (x2 , y2 ) = P et R = (P + Q) = (x3 , y3 ).
Courbes elliptiques et cryptographie p. 10
II-1.2 La structure de groupe (suite)
x3 = a2 + 2 + a1 x1 x2 , y3 = (x3 + ) a1 x3 a3 ; y y 2 1 si P = Q x2 x1 = y1 x1
2 + 2 a x + a a y 3 x 2 1 4 1 1 1 si P = Q 2y1 + a1 x1 + a3
Courbes elliptiques et cryptographie p. 11
II-1.2.1 Caractristique = 2, 3
y 2 = x3 + ax + b. Si P = (x1 , y1 ) et Q = (x2 , y2 ) alors P = (x1 , y1 ), si Q = P alors P + Q = O, sinon P + Q = (x3 , y3 ) o x3 = 2 x1 x2 avec = y3 = (x1 x3 ) y1
y y 2 1 si P = Q x2 x1
2 3 x 1 + a si P = Q 2y1
Courbes elliptiques et cryptographie p. 12
II-1.2.2 Caractristique 2
1) Cas non-supersingulier y 2 + xy = x3 + ax2 + b Si P = (x1 , y1 ) et Q = (x2 , y2 ) alors P = (x1 , x1 + y1 ), si Q = P alors P + Q = O, sinon P + Q = (x3 , y3 ) o x3 = 2 + + x1 + x2 + a y3 = (x1 + x3 ) + x3 + y1 avec =
y1 +y2 x1 +x2
si P = Q.
Courbes elliptiques et cryptographie p. 13
II-1.2.2 Caractristique 2 (suite)
et x3 = 2 + + a y3 = x2 1 + x3 + x3 avec y1 = x1 + x1
si P = Q.
Courbes elliptiques et cryptographie p. 14
II-1.2.3 Caractristique 3
1) Cas non-supersingulier y 2 = x3 + ax2 + b x 3 = a + 2 x 1 x 2 , y3 = (x1 x3 ) y1 ; y2 y1 si P = Q x2 x1 = ax1 si P = Q y1
Courbes elliptiques et cryptographie p. 15
II-1.2.3 Caractristique 3 (suite)
1) Cas supersingulier y 2 = x3 + ax + b x3 = 2 x1 x2 , y3 = (x1 x3 ) y1 ; y2 y1 si P = Q x2 x1 = a si P = Q 2y1
Courbes elliptiques et cryptographie p. 16
II-1.3 Ordre du groupe
Soit E une courbe elliptique sur Fq . Notons #E (q ) son nombre de points sur Fq . On dispose de la borne de Hasse q + 1 2 q #E q + 1 + 2 q. crivons que avec |t| 2 q . #E (q ) = q + 1 t
Quels sont les ordres possibles?
Courbes elliptiques et cryptographie p. 17
II-1.3.1 Existence
Si q = pm , il existe une courbe elliptique vriant #E (q ) = q + 1 t si et seulement si lune des conditions suivantes est satisfaite 1) t 0 mod p et t2 4q 2) m est impair et a) ou bien t = 0 b) ou bien t2 = 2q et p = 2 c) ou bien t2 = 3q et p = 3 3) m est pair et a) ou bien t2 = 4q b) ou bien t2 = q et p 1 mod 3 c) ou bien t = 0 et p 1 mod 4
Courbes elliptiques et cryptographie p. 18
II-1.3.2 Calcul de lordre
Si on connat #E (q ) = q + 1 t alors on peut calculer par rcurrence #E (q n ) = q + 1 tn en posant t0 = 2, t1 = t, tn = t1 tn1 qtn2 (pour n 2). Ceci arrivera en particulier si la courbe utilise a ses coefcients dans un petit corps. Sinon, on dispose de lalgorithme de Schoof et de ses variantes, ou alors des constructions de Morain pour obtenir une courbe ayant un nombre de points donn.
Courbes elliptiques et cryptographie p. 19
II-1.4 Courbes supersingulires
Soit E une courbe sur Fq ayant #E (q ) = q + 1 t points sur Fq (q = pm ). Nous dirons que E est supersinguli` ere si p divise t.
Courbes elliptiques et cryptographie p. 20
