INTRODUCTION AUX COURBESELLIPTIQUES
Abderrahmane NITAJ
Université de Caen, France

Rabat, 29 Octobre 2008

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESCONTENU
1

GENERALITES
Equations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique2

CORPS FINIS et COURBES ELLIPTIQUES
Les corps finis
Courbes elliptiques sur les corps finis

3

APPLICATIONS des COURBES ELLIPTIQUES
Primalité et Facorization
Cryptographie

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

CONTENU
1

GENERALITES
Equations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique2

CORPS FINIS et COURBES ELLIPTIQUES
Les corps finis
Courbes elliptiques sur les corps finis

3

APPLICATIONS des COURBES ELLIPTIQUES
Primalité et Facorization
Cryptographie

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Equation de Weiersrass
K est un corps (Q, R, C, Fp ,...), a1 , a2 , a3 , a4 , a6 ∈ K.
Une courbe elliptique sur K est définie par :Une équation de Weiersrass (forme projective)E:

Y 2 Z + a1 XYZ + a3 YZ 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

Un discriminant ∆ 6= 0.
Le point O = [0, 1, 0] est appelé point à l’infini.

Pour Z 6= 0, on peut écrire x = XZ , y = YZ , et l’équation deWeiersrass devient (forme affine)E:y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

L’ensemble des points K rationnels est
E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Equation de Weiersrass
K est un corps (Q, R, C, Fp ,...), a1 , a2 , a3 , a4 , a6 ∈ K.
Une courbe elliptique sur K est définie par :Une équation de Weiersrass (forme projective)E:

Y 2 Z + a1 XYZ + a3 YZ 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

Un discriminant ∆ 6= 0.
Le point O = [0, 1, 0] est appelé point à l’infini.

Pour Z 6= 0, on peut écrire x = XZ , y = YZ , et l’équation deWeiersrass devient (forme affine)E:y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

L’ensemble des points K rationnels est
E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Equation de Weiersrass
K est un corps (Q, R, C, Fp ,...), a1 , a2 , a3 , a4 , a6 ∈ K.
Une courbe elliptique sur K est définie par :Une équation de Weiersrass (forme projective)E:

Y 2 Z + a1 XYZ + a3 YZ 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

Un discriminant ∆ 6= 0.
Le point O = [0, 1, 0] est appelé point à l’infini.

Pour Z 6= 0, on peut écrire x = XZ , y = YZ , et l’équation deWeiersrass devient (forme affine)E:y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

L’ensemble des points K rationnels est
E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Equation de Weiersrass
K est un corps (Q, R, C, Fp ,...), a1 , a2 , a3 , a4 , a6 ∈ K.
Une courbe elliptique sur K est définie par :Une équation de Weiersrass (forme projective)E:

Y 2 Z + a1 XYZ + a3 YZ 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

Un discriminant ∆ 6= 0.
Le point O = [0, 1, 0] est appelé point à l’infini.

Pour Z 6= 0, on peut écrire x = XZ , y = YZ , et l’équation deWeiersrass devient (forme affine)E:y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .

L’ensemble des points K rationnels est
E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueCharactéristiue > 3
Equation de Weiersrass :E:

y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Si la caractéristique de K est différente de 2, l’équation
peut s’écrire :E:

y2 = x3 + a02 x2 + a04 x + a06 ,Si la caractéristique de K est différente de 2 et de 3,
l’équation peut s’écrire :E:

y2 = x3 + ax + b,

Le discriminant est ∆ = −16(4a3 + 27b2 ) 6= 0.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueCharactéristiue > 3
Equation de Weiersrass :E:

y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Si la caractéristique de K est différente de 2, l’équation
peut s’écrire :E:

y2 = x3 + a02 x2 + a04 x + a06 ,Si la caractéristique de K est différente de 2 et de 3,
l’équation peut s’écrire :E:

y2 = x3 + ax + b,

Le discriminant est ∆ = −16(4a3 + 27b2 ) 6= 0.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueCharactéristiue > 3
Equation de Weiersrass :E:

y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Si la caractéristique de K est différente de 2, l’équation
peut s’écrire :E:

y2 = x3 + a02 x2 + a04 x + a06 ,Si la caractéristique de K est différente de 2 et de 3,
l’équation peut s’écrire :E:

y2 = x3 + ax + b,

Le discriminant est ∆ = −16(4a3 + 27b2 ) 6= 0.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueCharactéristiue = 2 ou = 3
Si la caractéristique de K est 2, l’équation peut s’écrire :E:

y2 + xy = x3 + ax2 + b,E:y2 + ay = x3 + bx + c,ou bienSi la caractéristique de K est 3, l’équation peut s’écrire :E:

y2 = x3 + ax2 + b,E:y2 = x3 + ax + b,

ou bienAbderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueCharactéristiue = 2 ou = 3
Si la caractéristique de K est 2, l’équation peut s’écrire :E:

y2 + xy = x3 + ax2 + b,E:y2 + ay = x3 + bx + c,ou bienSi la caractéristique de K est 3, l’équation peut s’écrire :E:

y2 = x3 + ax2 + b,E:y2 = x3 + ax + b,

ou bienAbderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueUnicité
Soit E/K définie par E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Cette équation est unique modulo les changements devaribles :x = u2 X + r
y = u3 Y + su2 X + t avec r, s, t, u ∈ K.

L’équation devient alors
E0 :Y 2 + a01 XY + a03 Y = X 3 + a02 X 2 + a04 X + a06 .

Avec

ua01 = a1 + 2s
u2 a02 = a2 − sa1 + 3r − s2
u3 a03 = a3 + ra1 + 2t
u4 a04 = a4 − sa3 + 2ra2 − (t + rs)a1 + 3r2 − 2stu6 a06 = a6 + ra4 + r2 a2 + r3 − ta3 − t2 − rta1 .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueUnicité
Soit E/K définie par E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Cette équation est unique modulo les changements devaribles :x = u2 X + r
y = u3 Y + su2 X + t avec r, s, t, u ∈ K.

L’équation devient alors
E0 :Y 2 + a01 XY + a03 Y = X 3 + a02 X 2 + a04 X + a06 .

Avec

ua01 = a1 + 2s
u2 a02 = a2 − sa1 + 3r − s2
u3 a03 = a3 + ra1 + 2t
u4 a04 = a4 − sa3 + 2ra2 − (t + rs)a1 + 3r2 − 2stu6 a06 = a6 + ra4 + r2 a2 + r3 − ta3 − t2 − rta1 .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueUnicité
Soit E/K définie par E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,Cette équation est unique modulo les changements devaribles :x = u2 X + r
y = u3 Y + su2 X + t avec r, s, t, u ∈ K.

L’équation devient alors
E0 :Y 2 + a01 XY + a03 Y = X 3 + a02 X 2 + a04 X + a06 .

Avec

ua01 = a1 + 2s
u2 a02 = a2 − sa1 + 3r − s2
u3 a03 = a3 + ra1 + 2t
u4 a04 = a4 − sa3 + 2ra2 − (t + rs)a1 + 3r2 − 2stu6 a06 = a6 + ra4 + r2 a2 + r3 − ta3 − t2 − rta1 .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 1 :Soit E/R définie par
E : y2 = (x2 + x + 14)(x + 1) = x3 + 2x2 + 15x + 14.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 2 :Soit E/R définie par
E : y2 = (x2 + x + 1)(x + 5) = x3 + 6x2 + 6x + 5.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 3 :Soit E/R définie par E :y2 = (x + 1)2 (x + 5).

Ceci n’est pas une courbe elliptique car ∆ = 0.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 3 :Soit E/R définie par E :y2 = (x + 1)2 (x + 5).

Ceci n’est pas une courbe elliptique car ∆ = 0.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 4 :Soit E/R définie par E :y2 = (x + 8)(x + 1)(x − 2).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 3 :Soit E/R définie par E :y2 = (x + 2)3 .

Ceci n’est pas une courbe elliptique car ∆ = 0.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 3 :Soit E/R définie par E :y2 = (x + 2)3 .

Ceci n’est pas une courbe elliptique car ∆ = 0.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 5 :Soit E/R définie par E : y2 =(x − 1)(x + 2)(x + 5), (x2 + x + 14)(x + 5), (x2 + x + 1)(x + 5).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptiqueReprésentation graphique
Exemple 4 :Soit E/C définie par E : y2 = x3 + ax + b. La courbe elliptique
E est isomorphe à un tore complexe C/L où L est un réseau dedimension 2.
La représentation graphique de E peut être transformée en tore.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points rationnels d’une courbe elliptiqueDéfinition :Soit E/K définie par E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .
L’ensemple des points K rationnels de E est

E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Exemple 1 :Soit E la courbe elliptique définie sur Q par E : y2 + y = x3 + x.
L’ensemple des points Q rationnels de E contient les points
2 17
O, (0, 0), (0, −1), (1, 1), (3, −6), (1, −2) , (3, 5) , − , −
,
9 27

 
 

2 10
33 19533 187
− ,−
,
,−
,
,
,··· .
9 27
48
4 8Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points rationnels d’une courbe elliptiqueDéfinition :Soit E/K définie par E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .
L’ensemple des points K rationnels de E est

E(K) = (x, y) ∈ K2 , y2 · · · = · · · + a6 ∪ {O}.
Exemple 1 :Soit E la courbe elliptique définie sur Q par E : y2 + y = x3 + x.
L’ensemple des points Q rationnels de E contient les points
2 17
O, (0, 0), (0, −1), (1, 1), (3, −6), (1, −2) , (3, 5) , − , −
,
9 27

 
 

2 10
33 19533 187
− ,−
,
,−
,
,
,··· .
9 27
48
4 8Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points rationnels d’une courbe elliptique
Exemple 2 :Soit E définie par E : y2 + y = x3 − 6x + 4. L’ensemple despoints Q rationnels de E est
E(K) = {O, (−1, 3), (−1, −3), (2, −3), (2, 0), (1, −1)} .
Exemple 3 :Soit E/(Z/13Z) définie par E :sur Z/13Z :y2 = x3 − 5x + 8. Il y a 20 points

O, (1, ±2), (4, 0), (5, ±2), (6, ±5), (7, ±2), (8, ±5), (9, ±4),(10, ±3), (11, ±6), (12, ±5).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points rationnels d’une courbe elliptique
Exemple 2 :Soit E définie par E : y2 + y = x3 − 6x + 4. L’ensemple despoints Q rationnels de E est
E(K) = {O, (−1, 3), (−1, −3), (2, −3), (2, 0), (1, −1)} .
Exemple 3 :Soit E/(Z/13Z) définie par E :sur Z/13Z :y2 = x3 − 5x + 8. Il y a 20 points

O, (1, ±2), (4, 0), (5, ±2), (6, ±5), (7, ±2), (8, ±5), (9, ±4),(10, ±3), (11, ±6), (12, ±5).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

L’oposé d’un point
Soit E/K une courbe elliptique et P ∈ E(K).
Comment placer le point −P?

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

L’oposé d’un point
Pour placer le point −P.
On trace la verticale qui passe par P.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

L’oposé d’un point
Pour placer le point −P.
On obtient le point −P à l’intersection avec la courbe.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Soit E/K une courbe elliptique et P ∈ E(K).
Comment placer le point 2P si xP 6= 0?

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Pour placer le point 2P si xP 6= 0.
On trace la tangente en P.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Pour placer le point 2P si xP 6= 0.
On trace la verticale.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Pour placer le point 2P si xP 6= 0.
On obtient le point 2P.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Comment placer le point 2P si xP = 0?

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Doubler un point
Pour placer le point 2P si xP = 0.
On trace la verticale en P. On obtient 2P = O.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Additionner deux points différents
Soit E/K une courbe elliptique et P, Q ∈ E(K) avec P 6= Q.
Comment placer le point P + Q?

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Additionner deux points différents
Pour placer le point P + Q.
On trace la droite (PQ).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Additionner deux points différents
Pour placer le point P + Q.
On trace la verticale au 3ème point d’intersection.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Additionner deux points différents
Pour placer le point P + Q.
On obtient le point P + Q.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Formules explicites d’addition
Points différents et non opposés
P = (xP , yP ) et Q = (xQ , yQ ) sont deux points de E(K) avec
xP 6= xQ . Alors P + Q = R = (xR , yR ), avec
xR = λ 2 − xP − xQ ,et
λ=yQ − yP,
xQ − xP

Abderrahmane NITAJyR = −λxR − ν,

ν = yP − λxP .

INTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Formules explicites d’addition
Points différents et opposés
P = (xP , yP ) et Q = (xQ , yQ ) sont deux points de E(K) avec
xP = xQ et yP 6= yQ alors
P + Q = O.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Formules explicites d’addition
Points identiques sur l’axe
P = (xP , yP ) et Q = (xQ , yQ ) sont deux points de E(K) avec
xP = xQ et yP = yQ = 0 alors
P + Q = 2P = O.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Formules explicites d’addition
Points identiques
P = (xP , yP ) et Q(xQ , yQ ) sont deux points de E(K) avec xP = xQ
et yP = yQ 6= 0 alors P + Q = R = (xR , yR ), avec
xR = λ 2 − xP − xQ ,etλ=

3xP2 + a,
2yP

Abderrahmane NITAJyR = −λxR − ν,

ν = yP − λxP .

INTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points de torsion

Définition :Soit E/K une courbe elliptique. L’ensemple des points detorsion est
E(K)tors = {P ∈ E(K),

Abderrahmane NITAJ∃m ∈ N∗mP = O} .

INTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points de torsionThéorème (Lutz-Nagell, 1935-1937):
Soit E/Q une courbe elliptique à coefficients entiers. Si
P = (x, y) est un point de torsion de E, alors x, y ∈ Z et y = 0 ou
y2 |∆.
Théorème (Mazur, 1975):
Soit E/Q une courbe elliptique. Alors Z/mZ, m = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12
E(Q)tors ' ou
Z/2Z × Z/2mZ, m = 1, 2, 3, 4.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points de torsionThéorème (Lutz-Nagell, 1935-1937):
Soit E/Q une courbe elliptique à coefficients entiers. Si
P = (x, y) est un point de torsion de E, alors x, y ∈ Z et y = 0 ou
y2 |∆.
Théorème (Mazur, 1975):
Soit E/Q une courbe elliptique. Alors Z/mZ, m = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12
E(Q)tors ' ou
Z/2Z × Z/2mZ, m = 1, 2, 3, 4.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points de torsion
Exemple 1 :Soit E/Q définie par E :y2 = x3 + x2 − x. Alors

E(Q)tors = {O, (0, 0), (1, 1), (1, −1), (−1, 1), (−1, −1)} ' Z/6Z.
P = (−1, −1) ∈ E(Q), alors 6P = O.
Exemple 2 :Soit E/Q définie par E :y2 + y = x3 − 1070x + 7812. Alors

E(Q)tors ' Z/2Z × Z/8Z.
P = (34, 88) ∈ E(Q), alors 8P = O.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Points de torsion
Exemple 1 :Soit E/Q définie par E :y2 = x3 + x2 − x. Alors

E(Q)tors = {O, (0, 0), (1, 1), (1, −1), (−1, 1), (−1, −1)} ' Z/6Z.
P = (−1, −1) ∈ E(Q), alors 6P = O.
Exemple 2 :Soit E/Q définie par E :y2 + y = x3 − 1070x + 7812. Alors

E(Q)tors ' Z/2Z × Z/8Z.
P = (34, 88) ∈ E(Q), alors 8P = O.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Structure de E(K)Théorème (Mordell-Weil (1922-1928):
Soit E/K une courbe elliptique. Alors il existe un nombre fini depoints P1 , P2 , · · · , Pn ∈ E(K) tels que tout point P de E(K) s’écritsous la forme
P = m1 P1 + m2 P2 + · · · + mn Pnavec

m1 , m2 , · · · , mn ∈ Z.

On a donc
E(K) ' Zr ⊕ E(K)tors
avec r ∈ N, appelé rang de E.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Structure de E(K)

Exemple 1 :Soit E/K définie par E :rationnels de E est

y2 = x3 − 2x. L’ensemple des points Q

E(Q) = h(0, 0), (−1, −1)i ,où (0, 0) est un point d’ordre 2 et (−1, −1) est un point d’ordre
infini. Alors
E(Q) = Z ⊕ Z/2Z

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Structure de E(K)

Exemple 2 :Soit E/Q définie par E :rationnels de E est

y2 = x3 + 4x. L’ensemple des points Q
E(Q) = h(2, 4)i ,où (2, 4) est un point d’ordre 4. Alors
E(Q) = Z/4Z

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Structure de E(K)

Exemple 3 :Soit E/Q définie par E :Q rationnels de E est

y2 = x3 − 82x. L’ensemple des points

E(Q) = h(0, 0), (−8, 12), (−1, −9), (−9, −3)i ,où (0, 0) est un point d’ordre 2 et les autres d’ordre infini. Alors
E(Q) = Z3 ⊕ Z/2Z,
i.e. E est de rang 3.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Le rang d’une courbe elliptiqueConjecture ”folklorique”
Il existe des courbes elliptiques E/Q de n’importe quel rang.
Exemple 1 (N. Elkies, 2006):
Soit E/Q définie parE:

y2 + xy + y=x3 − x2−2006776241557552658503320820
9338542750930230312178956502x+3448161179503055646703298569
0390720374855944359319180361266008
296291939448732243429.

Alors E(Q) = Zr ⊕ {O}, avec r ≥ 28, i.e. E est de rang ≥ 28.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUESEquations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique

Le rang d’une courbe elliptiqueConjecture ”folklorique”
Il existe des courbes elliptiques E/Q de n’importe quel rang.
Exemple 1 (N. Elkies, 2006):
Soit E/Q définie parE:

y2 + xy + y=x3 − x2−2006776241557552658503320820
9338542750930230312178956502x+3448161179503055646703298569
0390720374855944359319180361266008
296291939448732243429.

Alors E(Q) = Zr ⊕ {O}, avec r ≥ 28, i.e. E est de rang ≥ 28.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

CONTENU
1

GENERALITES
Equations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique2

CORPS FINIS et COURBES ELLIPTIQUES
Les corps finis
Courbes elliptiques sur les corps finis

3

APPLICATIONS des COURBES ELLIPTIQUES
Primalité et Facorization
Cryptographie

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis

Les corps premiers Fp
Soit p dun nombre premier. Alors Fp = Z/pZ = Z (mod p) est
un corps fini.
ExemplesF2 = Z/2Z = Z (mod 2) = {0, 1}.
F3 = Z/3Z = Z (mod 3) = {−1, 0, 1}.
F5 = Z/5Z = Z (mod 5) = {−2, −1, 0, 1, 2}.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis

Les corps premiers Fp
Soit p dun nombre premier. Alors Fp = Z/pZ = Z (mod p) est
un corps fini.
ExemplesF2 = Z/2Z = Z (mod 2) = {0, 1}.
F3 = Z/3Z = Z (mod 3) = {−1, 0, 1}.
F5 = Z/5Z = Z (mod 5) = {−2, −1, 0, 1, 2}.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Le corps fini F23
On considère le polynôme P(X) = X 3 + X + 1 de F2 [X].
Alors
P est iréductible car P(0) = P(1) = 1.
F2 [X]/(P(X)) est un corps.
F2 [X]/(P(X)) = {aX 2 + bX + c,

a, b, c ∈ F2 }.
2F2 [X]/(P(X)) = {0, 1, X, X , 1 + X, 1 + X 2 , X + X 2 , 1 + X + X 2 }.
#F2 [X]/(P(X)) = 8 = 23 .
F2 [X]/(P(X)) = F23 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Le corps fini F23
On considère le polynôme P(X) = X 3 + X + 1 de F2 [X].
Alors
P est iréductible car P(0) = P(1) = 1.
F2 [X]/(P(X)) est un corps.
F2 [X]/(P(X)) = {aX 2 + bX + c,

a, b, c ∈ F2 }.
2F2 [X]/(P(X)) = {0, 1, X, X , 1 + X, 1 + X 2 , X + X 2 , 1 + X + X 2 }.
#F2 [X]/(P(X)) = 8 = 23 .
F2 [X]/(P(X)) = F23 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Le corps fini F23
On considère le polynôme P(X) = X 3 + X + 1 de F2 [X].
Alors
P est iréductible car P(0) = P(1) = 1.
F2 [X]/(P(X)) est un corps.
F2 [X]/(P(X)) = {aX 2 + bX + c,

a, b, c ∈ F2 }.
2F2 [X]/(P(X)) = {0, 1, X, X , 1 + X, 1 + X 2 , X + X 2 , 1 + X + X 2 }.
#F2 [X]/(P(X)) = 8 = 23 .
F2 [X]/(P(X)) = F23 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Le corps fini F23
On considère le polynôme P(X) = X 3 + X + 1 de F2 [X].
Alors
P est iréductible car P(0) = P(1) = 1.
F2 [X]/(P(X)) est un corps.
F2 [X]/(P(X)) = {aX 2 + bX + c,

a, b, c ∈ F2 }.
2F2 [X]/(P(X)) = {0, 1, X, X , 1 + X, 1 + X 2 , X + X 2 , 1 + X + X 2 }.
#F2 [X]/(P(X)) = 8 = 23 .
F2 [X]/(P(X)) = F23 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Le corps fini F23
On considère le polynôme P(X) = X 3 + X + 1 de F2 [X].
Alors
P est iréductible car P(0) = P(1) = 1.
F2 [X]/(P(X)) est un corps.
F2 [X]/(P(X)) = {aX 2 + bX + c,

a, b, c ∈ F2 }.
2F2 [X]/(P(X)) = {0, 1, X, X , 1 + X, 1 + X 2 , X + X 2 , 1 + X + X 2 }.
#F2 [X]/(P(X)) = 8 = 23 .
F2 [X]/(P(X)) = F23 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 se fait modulo 2 avec 1 + 1 = 0. Exemples :(1 + X 2 ) + (X + X 2 ) = 1 + X,

(1 + X 2 ) + (1 + X 2 ) = 0.

Multiplication
La multiplication dans F23 se fait modulo 2 et X 3 + X + 1, avec
X 3 = −X − 1 = X + 1. Exemple :(1 + X 2 ) × (X + X 2 ) = X + X 2 + X 3 + X 4= X + X 2 + (X + 1) + (X 2 + X)
= 1 + X.
L’addition est simple mais la multiplication est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 se fait modulo 2 avec 1 + 1 = 0. Exemples :(1 + X 2 ) + (X + X 2 ) = 1 + X,

(1 + X 2 ) + (1 + X 2 ) = 0.

Multiplication
La multiplication dans F23 se fait modulo 2 et X 3 + X + 1, avec
X 3 = −X − 1 = X + 1. Exemple :(1 + X 2 ) × (X + X 2 ) = X + X 2 + X 3 + X 4= X + X 2 + (X + 1) + (X 2 + X)
= 1 + X.
L’addition est simple mais la multiplication est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 se fait modulo 2 avec 1 + 1 = 0. Exemples :(1 + X 2 ) + (X + X 2 ) = 1 + X,

(1 + X 2 ) + (1 + X 2 ) = 0.

Multiplication
La multiplication dans F23 se fait modulo 2 et X 3 + X + 1, avec
X 3 = −X − 1 = X + 1. Exemple :(1 + X 2 ) × (X + X 2 ) = X + X 2 + X 3 + X 4= X + X 2 + (X + 1) + (X 2 + X)
= 1 + X.
L’addition est simple mais la multiplication est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Racines de P(T) = T 3 + T + 1 dans F23
On peut vérifier :(X)3 + (X) + 1 = 0

et(X 2 )3 + (X 2 ) + 1 = 0.

Ainsi P a deux racines dans F23 . On note ω = X. Alorsω 1 = X,

ω2 = X2,

ω5 = 1 + X + X2,

ω 3 = X + 1,
ω6 = 1 + X2,

ω4 = X + X2,
ω 7 = 1,

ω 8 = X.

Ainsi
F23 = hωi .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 = hωi.
Exemple :(1 + X 2 ) + (X + X 2 ) = 1 + X ⇔ ω 6 + ω 4 = ω 3 .
Multiplication
La multiplication dans F23 = hωi se fait modulo 7 pour les
exposants. Exemple :(1 + X 2 ) × (X + X 2 ) = 1 + X ⇔ ω 6 × ω 4 = ω 10 = ω 3 .
La multiplication est simple mais l’addition est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 = hωi.
Exemple :(1 + X 2 ) + (X + X 2 ) = 1 + X ⇔ ω 6 + ω 4 = ω 3 .
Multiplication
La multiplication dans F23 = hωi se fait modulo 7 pour les
exposants. Exemple :(1 + X 2 ) × (X + X 2 ) = 1 + X ⇔ ω 6 × ω 4 = ω 10 = ω 3 .
La multiplication est simple mais l’addition est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le corps fini F23
Addition
L’addition dans F23 = hωi.
Exemple :(1 + X 2 ) + (X + X 2 ) = 1 + X ⇔ ω 6 + ω 4 = ω 3 .
Multiplication
La multiplication dans F23 = hωi se fait modulo 7 pour les
exposants. Exemple :(1 + X 2 ) × (X + X 2 ) = 1 + X ⇔ ω 6 × ω 4 = ω 10 = ω 3 .
La multiplication est simple mais l’addition est plus
compliquée.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description
Le théorème de WedderburnTout corps fini est commutatif : xy = yx.
La caractéristique
Si F est un corps fini, alors il existe un nombre premier p tel que
p.1 = 0 dans F.
On dit que p est la caractéristique de F.
F est un espace vectoriel
Si F est un corps fini de caractéristique p, alors
F est un Fp -espace vectoriel de dimension finie n ≥ 1.
#F = pn .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description
Le théorème de WedderburnTout corps fini est commutatif : xy = yx.
La caractéristique
Si F est un corps fini, alors il existe un nombre premier p tel que
p.1 = 0 dans F.
On dit que p est la caractéristique de F.
F est un espace vectoriel
Si F est un corps fini de caractéristique p, alors
F est un Fp -espace vectoriel de dimension finie n ≥ 1.
#F = pn .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description
Le théorème de WedderburnTout corps fini est commutatif : xy = yx.
La caractéristique
Si F est un corps fini, alors il existe un nombre premier p tel que
p.1 = 0 dans F.
On dit que p est la caractéristique de F.
F est un espace vectoriel
Si F est un corps fini de caractéristique p, alors
F est un Fp -espace vectoriel de dimension finie n ≥ 1.
#F = pn .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description

L’ordre d’un élément
Soit F un corps fini avec #F = pn et a ∈ F∗ . Alors il existe unentier m ≥ 1 tel que
am = 1.
m|(pn − 1).
Xm − 1 =m−1Y
X − ai .

i=0

Le nombre m s’appelle l’ordre de a.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description
L’ordre d’un élément
Soit F un corps fini avec #F = pn . Alors
Si m|(pn − 1), il existe a ∈ F d’ordre m.
En particulier, il existe ω ∈ F d’ordre pn − 1.
On dit que ω est un élément primitif.
F∗ est cyclique
Soit F un corps fini avec #F = pn et ω un élément primitif. AlorsF∗ = hωi.
F∗ est un groupe cyclique.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis : description
L’ordre d’un élément
Soit F un corps fini avec #F = pn . Alors
Si m|(pn − 1), il existe a ∈ F d’ordre m.
En particulier, il existe ω ∈ F d’ordre pn − 1.
On dit que ω est un élément primitif.
F∗ est cyclique
Soit F un corps fini avec #F = pn et ω un élément primitif. AlorsF∗ = hωi.
F∗ est un groupe cyclique.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis

Les corps finis Fq
Soit K un corps fini. Alors le cardinal de K est une
puissance d’un nombre premier:
K = Fqavec

q = pn , n ≥ 1.

Soit q = pn une puissance d’un nombre premier. Alors ilexiste un corps fini unique (à isomorphisme près) avec qéléments.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis

Les corps finis Fq
Soit K un corps fini. Alors le cardinal de K est une
puissance d’un nombre premier:
K = Fqavec

q = pn , n ≥ 1.

Soit q = pn une puissance d’un nombre premier. Alors ilexiste un corps fini unique (à isomorphisme près) avec qéléments.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finisGroupes multiplicatifs (F∗p , ×)
Soit p un nombre premier. Le groupe (F∗p , ×) est cyclique. C’est
le groupe des racines (p − 1)-èmes de l’unité :F∗p = ω, ω 2 , · · · , ω p−1 = 1 .
ExemplesPour F∗2 , ω = 1.
Pour F∗3 , ω = 2.
Pour F∗5 , ω = 2.
Pour F∗17 , ω = 3.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finisGroupes multiplicatifs (F∗p , ×)
Soit p un nombre premier. Le groupe (F∗p , ×) est cyclique. C’est
le groupe des racines (p − 1)-èmes de l’unité :F∗p = ω, ω 2 , · · · , ω p−1 = 1 .
ExemplesPour F∗2 , ω = 1.
Pour F∗3 , ω = 2.
Pour F∗5 , ω = 2.
Pour F∗17 , ω = 3.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Les corps finis Fq
Soit p un nombre premier et q = pn . Le corps finis Fq est
cyclique. C’est l’ensemble des racines du polynôme X q − X etadmet un élément ω d’ordre maximal q − 1, appelé élément
primitif :Fq = 0, ω, ω 2 , · · · , ω q−1 = 1 .
ExemplesPour F∗22 , ω est une racine de X 2 + X + 1.
Pour F∗23 , ω est une racine de X 3 + X + 1.
Pour F∗32 , ω est une racine de X 2 + 1.
Pour F∗24 , ω est une racine de X 4 + X + 1.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Les corps finis Fq
Soit p un nombre premier et q = pn . Le corps finis Fq est
cyclique. C’est l’ensemble des racines du polynôme X q − X etadmet un élément ω d’ordre maximal q − 1, appelé élément
primitif :Fq = 0, ω, ω 2 , · · · , ω q−1 = 1 .
ExemplesPour F∗22 , ω est une racine de X 2 + X + 1.
Pour F∗23 , ω est une racine de X 3 + X + 1.
Pour F∗32 , ω est une racine de X 2 + 1.
Pour F∗24 , ω est une racine de X 4 + X + 1.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Construction pratique de Fq
Soit p un nombre premier et q = pn . Le corps finis Fq est
l’ensemble des racines du polynôme X q − X. Pour construire Fq
On factorise le polynôme X q − X dans Fp [X] (algorithme
Cantor-Zassenhaus ou de Berlekamp).
On détermine une racine ω d’un d’un polynôme irréductible
P de Fp [X] de degré n.
En résumé : q = pn
Fq = hωi ∪ {0}.
Fq = Fp [X]/P(X), P est irréductible sur Fp et de degré n.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Les corps finis
Construction pratique de Fq
Soit p un nombre premier et q = pn . Le corps finis Fq est
l’ensemble des racines du polynôme X q − X. Pour construire Fq
On factorise le polynôme X q − X dans Fp [X] (algorithme
Cantor-Zassenhaus ou de Berlekamp).
On détermine une racine ω d’un d’un polynôme irréductible
P de Fp [X] de degré n.
En résumé : q = pn
Fq = hωi ∪ {0}.
Fq = Fp [X]/P(X), P est irréductible sur Fp et de degré n.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Retour aux courbes elliptiques. Un exemple sur F24

Soit E la courbe elliptique définie sur F24 par
E : y2 + xy = x3 + ω 2 x + ω 3 avec ω 4 = ω + 1.
Propriétés#E(Fq ) = 12.
E(Fq ) =

14
7
10
13
10 ), (ω, ω 10 ), (ω 12 , ω 10 )O, (ω 9, ω ),12(ω 3, 1), (ω 8 , ω 13
∪ (0, ω ), (ω , ω ), (ω, ω ), (ω , ω 9 ), (ω 10 , ω 5 ), (ω 14 , ω)P = (ω 12 , ω 10 ), Q = (ω, ω 8 ). Alors P + Q = (ω 14 , ω 7 ).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le nombre de points#E(Fq )
Soit p un nombre premier et q = pn . AlorsX#E(Fq ) = 1 + q +χ x3 + ax + b ,x∈Fqoù χ est le caractère quadratique :
+1 si r est un carré dans Fq ,χ(r) = 0
si r = 0,−1 si r n’est pas un carré dans Fq .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Structure de E(Fq )Théorème [Deuring (1941)]
Soit p un nombre premier et q = pn . Alors E(Fq ) est un groupe
cyclique ou le produit de deux groupes cycliques : Z/MZ, avec M = #E(Fq )∼E(Fq ) =ou
Z/MZ × Z/LZ, avec M|L, ML = #E(Fq ).
Exemple 1:
Soit E la courbe définie sur (F72 ) par E :y2 = x3 + 2x + 4. Alors

E(Fq ) ∼= Z/2Z × Z/30Z = h(1, 0), (ω 19 , ω 2 )i,où ω est un générateur de (F72 ).
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Structure de E(Fq )Théorème [Deuring (1941)]
Soit p un nombre premier et q = pn . Alors E(Fq ) est un groupe
cyclique ou le produit de deux groupes cycliques : Z/MZ, avec M = #E(Fq )∼E(Fq ) =ou
Z/MZ × Z/LZ, avec M|L, ML = #E(Fq ).
Exemple 1:
Soit E la courbe définie sur (F72 ) par E :y2 = x3 + 2x + 4. Alors

E(Fq ) ∼= Z/2Z × Z/30Z = h(1, 0), (ω 19 , ω 2 )i,où ω est un générateur de (F72 ).
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le théorème de Hasse
Théorème (Hasse, 1933)
Soit p un nombre premier et q = pk . Soit E une courbe elliptiquedéfine parE:

y2 = x3 + ax + b,

avec

a, b ∈ Fq .

Alors le nombre #E(Fq ) de points de E(Fq ) vérifie√|#E(Fq ) − (q + 1)| < 2 q.
Exemple :Soit E définie sur (Z/13Z) par E : y2 = x3 − 5x + 8.
Alors #E(F13 ) = 20 et on a bien√|#E(F13 ) − (13 + 1)| = |20 − 14| = 6 < 2 13.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Le théorème de Hasse
Théorème (Hasse, 1933)
Soit p un nombre premier et q = pk . Soit E une courbe elliptiquedéfine parE:

y2 = x3 + ax + b,

avec

a, b ∈ Fq .

Alors le nombre #E(Fq ) de points de E(Fq ) vérifie√|#E(Fq ) − (q + 1)| < 2 q.
Exemple :Soit E définie sur (Z/13Z) par E : y2 = x3 − 5x + 8.
Alors #E(F13 ) = 20 et on a bien√|#E(F13 ) − (13 + 1)| = |20 − 14| = 6 < 2 13.
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Calcul de #E(Fp )Recherche exhaustive
Soit E défine sur E(Fp ) par E : y2 = x3 + ax + b.
Pour chaque x = 1, 2, · · · , p − 1, on peut tester si x3 + ax + b est
un carré dans Fp par le critère d’Euler :dest un carré modulo p

p−1⇐⇒ d 2 ≡ 1 (mod p).

Cette méthode a une complexité de O(p log p) = O(p1+ε ).
Faisabilité
Cette méthode est assez efficace pour de très petites valeursp < 200.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Calcul de #E(Fp )La méthode de Shanks (1971)
1

Cette méthode a une complexité de O(p 4 +ε ).
Faisabilité
Assez efficace pour des petites valeurs p < 1020 .
La méthode de Schoof (1985) [+Atkin (1988)+Elkies (1991)⇐⇒ Méthode SEA.
Cette méthode a une complexité de O((log p)6 ).
Faisabilité
Assez efficace pour les grandes valeurs 1020 < p < 10?? .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Calcul de #E(Fp )La méthode de Shanks (1971)
1

Cette méthode a une complexité de O(p 4 +ε ).
Faisabilité
Assez efficace pour des petites valeurs p < 1020 .
La méthode de Schoof (1985) [+Atkin (1988)+Elkies (1991)⇐⇒ Méthode SEA.
Cette méthode a une complexité de O((log p)6 ).
Faisabilité
Assez efficace pour les grandes valeurs 1020 < p < 10?? .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Calcul de #E(Fp )La méthode de Shanks (1971)
1

Cette méthode a une complexité de O(p 4 +ε ).
Faisabilité
Assez efficace pour des petites valeurs p < 1020 .
La méthode de Schoof (1985) [+Atkin (1988)+Elkies (1991)⇐⇒ Méthode SEA.
Cette méthode a une complexité de O((log p)6 ).
Faisabilité
Assez efficace pour les grandes valeurs 1020 < p < 10?? .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Calcul de #E(Fp )La méthode de Shanks (1971)
1

Cette méthode a une complexité de O(p 4 +ε ).
Faisabilité
Assez efficace pour des petites valeurs p < 1020 .
La méthode de Schoof (1985) [+Atkin (1988)+Elkies (1991)⇐⇒ Méthode SEA.
Cette méthode a une complexité de O((log p)6 ).
Faisabilité
Assez efficace pour les grandes valeurs 1020 < p < 10?? .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Points de torsion de Fq
Définition
Soit E une courbe elliptique défine sur E(Fq ). Soit n ∈ Z.
L’ensemble des points de n torsion est
E[n] = {P ∈ E(Fq ),nP = O}.

Théorème
Pour chaque n ∈ Z, E[n] est fini.
Si gcd(q, n) = 1, alors #E[n] = n2 .
E[n] ∼= Z/nZ × Z/nZ.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Les corps finis
Courbes elliptiques sur les corps finis

Points de torsion de Fq
Définition
Soit E une courbe elliptique défine sur E(Fq ). Soit n ∈ Z.
L’ensemble des points de n torsion est
E[n] = {P ∈ E(Fq ),nP = O}.

Théorème
Pour chaque n ∈ Z, E[n] est fini.
Si gcd(q, n) = 1, alors #E[n] = n2 .
E[n] ∼= Z/nZ × Z/nZ.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

CONTENU
1

GENERALITES
Equations de Weiersraß
Représentations graphiques
Points d’une courbe elliptique2

CORPS FINIS et COURBES ELLIPTIQUES
Les corps finis
Courbes elliptiques sur les corps finis

3

APPLICATIONS des COURBES ELLIPTIQUES
Primalité et Facorization
Cryptographie

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Test de primalité
Théorème [Goldwasser-Kilian, (1986)]
Soit N un nombre entier premier avec 6. S’il existe un entier met un point P de la courbe elliptique définie par le point O et parl’équation
Y 2 = x3 + ax + b (mod N),vérifiant
 1
2
m a un facteur premier d > N 4 + 1 ,mP = O,m
d P 6= O,alors N est un nombre premier.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Test de primalité
ECPP [Atkin-Morain, (1990)]
Le test de primalité ECPP (Elliptic Curve Primality Proving) est
basé sur le critère de Goldwasser-Kilian et est très efficace etsa complexité est polynômiale:
O (log N)4 .
Un bel exemple de nombre premier avec ECPP (2004)
Le nombre suivant est premier (≈ 1015071 ) :26384405 + 44052638 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Test de primalité
ECPP [Atkin-Morain, (1990)]
Le test de primalité ECPP (Elliptic Curve Primality Proving) est
basé sur le critère de Goldwasser-Kilian et est très efficace etsa complexité est polynômiale:
O (log N)4 .
Un bel exemple de nombre premier avec ECPP (2004)
Le nombre suivant est premier (≈ 1015071 ) :26384405 + 44052638 .

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Factorisation
La méthode ECM [H.W. Lenstra, (1986)]
La méthode ECM (Elliptic Curve Method) est unegénéralisation de la méthode p − 1 de Polard. Le domaine decalcul est E(Z/NZ) où E est une courbe elliptique aléatoirement
choisie. Pour P ∈ E(Z/NZ), la méthode consiste à calculer despoints mP jusqu’à ce que un dénominateur contienne un facteurde N . Elle permet de trouver les petits facteurs d’un entier N.
Un record avec ECM
Avec ECMNET project de l’INRIA-Loria, un grand facteur
premier a été déterminé par B. Dodson en 2006:p ≈ 1067 ,Abderrahmane NITAJ

p|10381 + 1.
INTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Factorisation
La méthode ECM [H.W. Lenstra, (1986)]
La méthode ECM (Elliptic Curve Method) est unegénéralisation de la méthode p − 1 de Polard. Le domaine decalcul est E(Z/NZ) où E est une courbe elliptique aléatoirement
choisie. Pour P ∈ E(Z/NZ), la méthode consiste à calculer despoints mP jusqu’à ce que un dénominateur contienne un facteurde N . Elle permet de trouver les petits facteurs d’un entier N.
Un record avec ECM
Avec ECMNET project de l’INRIA-Loria, un grand facteur
premier a été déterminé par B. Dodson en 2006:p ≈ 1067 ,Abderrahmane NITAJ

p|10381 + 1.
INTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le problème du logarithme discret

Soit E une courbe elliptique définie sur Fp . Soit P et Q deux
points de E(Fp ) tels que Q ∈ hPi.
DLP.
Déterminer un entier n tel que Q = nP.
Si #E(Fp ) ≈ 1060 est premier, ce problème est difficile.
La cryptograhie des téléphones cellulaires est basée surce problème.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème El Gamal

Principe [Taher El Gamal (1985)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème El Gamal.
Préparation de Baba
Baba choisit une courbe elliptique E : y2 = x3 + Ax + B
sur corps fini Fq et un point P de E(Fq ).
Baba choisit un entier b et calcule bP.
Baba publie q, E, P et bP et garde secret la clé b.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème El Gamal

Principe [Taher El Gamal (1985)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème El Gamal.
Préparation de Baba
Baba choisit une courbe elliptique E : y2 = x3 + Ax + B
sur corps fini Fq et un point P de E(Fq ).
Baba choisit un entier b et calcule bP.
Baba publie q, E, P et bP et garde secret la clé b.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème El Gamal
Principe [Taher El Gamal (1985)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème El Gamal.
Cryptage de Ali
Ali transforme son message secret M en un entier m.
Ali calcule une valeur y à l’aide de la courbe elliptiuqe deBaba : y2 = m3 + Am + B.
Ali choisit un entier k et calcule kP, kbP et m + kbP.
Ali envoie à Baba les quantités kP et (m, y) + kbP et garde
secret la clé k (et son mesage secret clair m).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème El Gamal
Principe [Taher El Gamal (1985)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème El Gamal.
Décyptage de Baba
Baba reçoit kP et (m, y) + kbP.
Baba calcule bkP, −bkP puis retrouve(m, y) = (−bkP) + ((m, y) + kbP).
Sécurité du cryptosystème El Gamal
La sécurité de ce système est basée sur le problème dulogarithme discrer. En effet, les quantités bP et kP peuvent êtreinterceptées, mais il est très difficile de calculer k, b ou mêmekbP (Problème de Diffie-Hellman).
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème El Gamal
Principe [Taher El Gamal (1985)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème El Gamal.
Décyptage de Baba
Baba reçoit kP et (m, y) + kbP.
Baba calcule bkP, −bkP puis retrouve(m, y) = (−bkP) + ((m, y) + kbP).
Sécurité du cryptosystème El Gamal
La sécurité de ce système est basée sur le problème dulogarithme discrer. En effet, les quantités bP et kP peuvent êtreinterceptées, mais il est très difficile de calculer k, b ou mêmekbP (Problème de Diffie-Hellman).
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème ECES
Principe [Menezes-Qu-Vanstone (1995)]
ECES=Elliptic Curve Encryption System
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème ECES.
Préparation de Baba
Baba choisit une courbe elliptique E : y2 = x3 + Ax + B
sur corps fini Fq et un point P de E(Fq ).
Baba choisit un entier b et calcule bP.
Baba publie q, E, P et bP et garde secret la clé b.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème ECES
Principe [Menezes-Qu-Vanstone (1995)]
ECES=Elliptic Curve Encryption System
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème ECES.
Préparation de Baba
Baba choisit une courbe elliptique E : y2 = x3 + Ax + B
sur corps fini Fq et un point P de E(Fq ).
Baba choisit un entier b et calcule bP.
Baba publie q, E, P et bP et garde secret la clé b.

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème ECES
Principe [Menezes-Qu-vanstone (1995)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème ECES.
Cryptage de Ali
Ali transforme son message secret M en un entier m avec
1 ≤ m < q.
Ali choisit un entier k et calcule kP, kbP = (xA , yA ).
Ali calcule c = mxA (mod q).
Ali envoie à Baba les quantités kP et c et garde secret laclé k (et son mesage secret clair m).

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème ECES
Principe [Menezes-Qu-vanstone (1995)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème ECES.
Décyptage de Baba
Baba reçoit kP et c.
Baba calcule bkP = (xA , yA ).
Baba calcule m = cxA−1 (mod q).
Sécurité du cryptosystème ECES
Sa sécurité est basé sur le problème du logarithme discrer. En
effet, les quantités bP, kP et mxA (mod q) peuvent êtreinterceptées, mais il est très difficile de calculer k, b, m ou xA .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Le cryptosystème ECES
Principe [Menezes-Qu-vanstone (1995)]
Ali veut envoyer un message secret à Baba, en utilisant lecryptosystème ECES.
Décyptage de Baba
Baba reçoit kP et c.
Baba calcule bkP = (xA , yA ).
Baba calcule m = cxA−1 (mod q).
Sécurité du cryptosystème ECES
Sa sécurité est basé sur le problème du logarithme discrer. En
effet, les quantités bP, kP et mxA (mod q) peuvent êtreinterceptées, mais il est très difficile de calculer k, b, m ou xA .
Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUESGENERALITESCORPS FINIS et COURBES ELLIPTIQUESAPPLICATIONS des COURBES ELLIPTIQUES

Primalité et Facorization
Cryptographie

Merci

Abderrahmane NITAJINTRODUCTION AUX COURBES ELLIPTIQUES