Ecole Polytech de Marseille

Case 925
13288 Marseille cedex 9

Année 5
Option : Systèmes Informatiques Critiques et Applications

Cours de Cryptographie Avancée

Courbes Elliptiques
Application à la Cryptographie

Par
Stéphane Ballet et Alexis Bonecaze
Table des matières

Table des matières i

1 Introduction 1

2 Généralités sur les courbes elliptiques 2

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Equation de Weierstrass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.2 Discriminant et j-invariant . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Loi de groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5.1 Définition et construction . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5.2 Formules explicites de l’addition . . . . . . . . . . . . . . . . . . . . . 7
2.6 Multiplication par un entier . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.7 Isomorphismes et formes canoniques . . . . . . . . . . . . . . . . . . . . . . . 8
2.8 Les courbes elliptiques définies sur un corps fini . . . . . . . . . . . . . . . . 9
2.8.1 Cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.8.2 Structure de groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Courbes elliptiques et cryptographie 12

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Courbes elliptiques sur K = F2n . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Courbes elliptiques convenables d’un point de vue cryptographique . 13
3.2.2 Formules explicites des opérations . . . . . . . . . . . . . . . . . . . . 13
3.2.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Logarithme discret généralisé . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Problèmes liés à l’utilisation des courbes elliptiques en cryptographie 19

4.1 Généralités sur l’implémentation des opérations . . . . . . . . . . . . . . . . 19
4.2 Calcul de l’ordre d’un point et d’une courbe elliptique . . . . . . . . . . . . . 23
4.2.1 Calcul de l’ordre d’un point P . . . . . . . . . . . . . . . . . . . . . . 23
4.2.2 Calcul de l’ordre d’une courbe E(K) . . . . . . . . . . . . . . . . . . 23

5 Application des courbes elliptiques à la cryptographie 25

5.1 L’échange de clés de Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 La signature EC-DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

i
 5.3 Normes actuelles et recommandations . . . . . . . . . . . . . . . . . . . . . . 27

6 Conclusion 29

Table des figures 30

Liste des tableaux 31

Bibliographie 32

ii
Chapitre 1

Introduction

D’une manière générale la cryptographie permet l’échange sécurisé de données entre deux
entités souvent nommées Alice et Bob dans la littérature. Le développement des nouvelles
technologies de télécommunication a eu pour effet de multiplier les actions nécessitant un
certain niveau de sécurité.

De nos jours la cryptographie fait partie intégrante de notre quotidien. En effet, elle est
sous-jacente dans de nombreux domaines dont les systèmes de cartes à puces. Par exemple,
lors de l’utilisation d’une carte bancaire, pour effectuer un retrait à un guichet automa-
tique, ou un achat sur internet, après avoir été identifié comme étant le véritable titulaire
du compte à débiter. La cryptographie permet de protéger l’accès à certaines données comme
les informations bancaires, médicales, ou encore celles échangées sur le réseau internet .

L’algorithme le plus répandu de nos jours, RSA, algorithme décrit en 1977 par Rivest,
Shamir et Adleman (d’où son nom), utilise l’arithmétique modulaire (modulo un entier N de
grande taille). Sa sécurité repose sur le fait qu’il est difficile de déterminer la factorisation
en nombres premiers de N, surtout s’il est de grande taille. L’existence d’algorithmes de
factorisation rapides (dont l’algorithme ECM, Elliptic Curve Method, utilisant les courbes
elliptiques) est un problème pour ce cryptosystème. Ils entrainent le recours à des entiers N
de plus en plus grands afin de garantir la sécurité. Par conséquent RSA voit sa performance
diminuer au fil du temps.

Les systèmes cryptographiques basés sur les courbes elliptiques permettent d’obtenir un
gain en efficacité dans la gestion de clés. En effet, de tels cryptosystèmes nécessitent des
clés de taille beaucoup plus modeste (par exemple, une clé de 160 bits lorsque RSA utilise
une clé de 1024 bits, à un niveau de sécurité équivalent) ce qui représente un avantage pour
les systèmes utilisant les cartes à puces dont l’espace mémoire est très limité. De plus, les
algorithmes de calculs liés aux courbes elliptiques sont plus rapides, et ont donc un débit
de générations et d’échanges de clé beaucoup plus important.

Dans un premier temps nous présenterons la théorie des courbes elliptiques, et comment
les appliquer à la cryptographie. Nous étudierons, dans un second temps, l’aspect pratique
des courbes elliptiques.

1
Chapitre 2

Généralités sur les courbes elliptiques

2.1 Introduction

Dans cette partie nous allons dans un premier temps définir de manière succincte les
courbes elliptiques et en dégager les principales propriétés, puis dans un second temps nous
verrons comment munir ce type de courbes d’une structure de groupe abélien.
Les définitions et théorèmes cités dans ce chapitre font référence aux travaux de Marc
Joyes [2] et Reynald Lercier [3], ainsi qu’aux cours de cryptographie de Stéphane Ballet
[1] et Yves Driencourt [4].

2.2 Définitions

Définition 1
Une courbe elliptique est une paire (E, O) où :
– E est une cubique irréductible non-singulière de genre 1,
– O ∈ E.

Définition 2
Une courbe elliptique est définie sur un corps K si :
– E est une courbe sur K (i.e. donnée par l’annulation d’un polynôme de K[X, Y ]),
– O est un point de la courbe dont les coordonnées sont dans K.

Notation 3
L’ensemble des points de E à coordonnées dans K sera noté E(K).

2
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

2.3 Equation de Weierstrass

2.3.1 Définition

Définition 4
On appelle espace projectif de dimension 2 associé à un corps K, noté P2 (K), l’ensemble
des classes (X : Y : Z), appelés coordonnées homogènes de la relation d’équivalence :
∀(X, Y, Z) ∈ K3 \{0K3 }, ∀(X 0 , Y 0 , Z 0 )∈ K3 \{0K3 },
0
 X = tX

(X, Y, Z) ≡ (X 0 , Y 0 , Z 0 ) ⇔ ∃ t ∈ K∗  Y 0 = tY
 0
Z = tZ

Théorème 1
Si E est une courbe elliptique définie sur K, alors il existe Φ : E(K) → P2 (K) qui
fournit un isomorphisme de E(K) sur une courbe C(K) tel que Φ(O) = (0 : 1 : 0) donnée
par l’équation de Weierstrass suivante :
C : F (X, Y, Z) = Y 2 Z + a1 XY Z + a3 Y Z 2 − X 3 − a2 X 2 Z − a4 XZ 2 − a6 Z 3 = 0
où (a1 , ..., a4 , a6 ) ∈ K5 .

Ainsi, l’ensemble des points d’une courbe elliptique E définie sur K est donc équivalent
à:
E(K) = {(X : Y : Z) ∈ P2 (K), F (X, Y, Z) = 0}

Remarque 1

– Seule une classe d’équivalence de cet ensemble vérifie Z = 0, il s’agit de la classe

(0 : 1 : 0) que nous nommerons point à l’infini et noterons O. Pour toutes les autres
classes, il existe un unique représentant de la forme (X : Y : 1). C’est pourquoi nous
considérerons par la suite E(K) comme la réunion de O et de l’ensemble des couples
(x, y), où x = X/Z et y = Y /Z représentent les coordonnées non-homogènes, vérifiant
l’équation
y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,
i.e. :
E(K) = {O} ∪ {(x, y) ∈ P2 (K)/y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 }
– O est le seul point à l’infini et il n’est pas singulier car ∂F/∂Z(0, 1, 0) = 1 6= 0.

3
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

2.3.2 Discriminant et j-invariant

Voici quelques notions utiles à l’étude des courbes définies par une équation de Weiers-
trass :

Soient les quantités :

b2 = a21 + 4a2 ,
b4 = a1 a3 + 2a4 ,
b6 = a23 + 4a6 ,
b8 = b2 a6 − a1 a3 a4 + a2 a23 − a24 ,
c4 = b22 − 24b4 ,
c6 = −b32 + 36b2 b4 − 216b6 .

Définition 5
On appelle discriminant, noté ∆, la quantité ∆ = −b22 b8 − 8b34 − 27b26 + 9b2 b4 b6

Théorème 2
Soit C une courbe définie sur un corps K par une équation de Weierstrass, alors :

C non-singulière ⇐⇒ ∆ 6= 0

Définition 6
On appelle invariant modulaire ou j-invariant, et on note j, la quantité : j = c34 ∆−1

Remarque 2
Puisque qu’une courbe elliptique est non-singulière, son discriminant est tel que ∆ 6= 0.
Ainsi l’invariant modulaire d’une courbe elliptique est toujours bien défini.

Définition 7
Une courbe elliptique est dite supersingulière lorsque son j-invariant est nul, i.e. j = 0.

4
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

2.4 Exemple

Soit E la courbe elliptique définie sur R par l’équation de Weierstrass y 2 = x3 − x.

Figure 2.1 – Représentation de E

On a :

a1 = a2 = a3 = a6 = 0 et a4 = −1

On en déduit :

b2 = b6 = c6 = 0,
b4 = −2,
b8 = −1,
c4 = 48.

Le calcul du discriminant donne donc : ∆ = 64 et l’invariant modulaire vaut alors :

j = 1728, la courbe elliptique E n’est donc ni singulière ni supersingulière.

5
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

2.5 Loi de groupe

L’ensemble des points d’une courbe elliptique, comme nous allons voir dans ce qui suit,
peut être muni d’une loi de groupe commutative. Cette loi de composition interne sera no-
tée de manière additive et nous permettra de définir la multiplication d’un point par un
nombre entier. Nous disposerons alors du matériel nécessaire pour introduire le problème
du logarithme discret sur les courbes elliptiques, d’où l’enjeu de celle-ci d’un point de vue
cryptographique.

2.5.1 Définition et construction

La loi de composition interne va être définie à l’aide du théorème suivant :

Théorème 3 Règle de la sécante tangente

Soient E une courbe elliptique et D une droite, toutes deux définies sur un corps K.
Si D coupe E en deux points (comptés avec leur multiplicité) alors D coupe E en trois
points (comptés avec leur multiplicité).

De ce théorème une première loi de composition interne que nous noterons ∗ peut être
déduite. Elle servira à construire la loi de groupe sur l’ensemble des points d’une courbe
elliptique :

Définition 8 Loi de composition interne de la sécante tangente

Soit E(K) une courbe elliptique définie sur un corps K. D’après le théorème précédent,
puisqu’une courbe elliptique est irréductible et non singulière :
– Soient deux points distincts P, Q ∈ E(K), P 6= Q, alors la droite (P Q) recoupe la
courbe E(K) en un troisième point noté P ∗ Q.
– Soit un point P ∈ E(K) alors on peut définir P ∗ P comme le point d’intersection de
la courbe E(K) avec sa tangente au point P .
Dans un premier temps la loi de groupe abélien d’une courbe elliptique va être définie
d’un point de vue géométrique, comme suit. Nous verrons dans la sous section suivante
comment la définir de manière explicite.

Théorème 4 Théorème de Poincaré

Soit un corps K. Si (E, O) est une courbe elliptique définie sur K, alors la loi
+ : E(K) × E(K) −→ E(K)
(P, Q) 7−→ O ∗ (P ∗ Q)
confère à (E, O) une structure de groupe abélien d’élément neutre O.

6
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

2.5.2 Formules explicites de l’addition

Nous allons à présent donner les formules explicites permettant de calculer les coordon-
nées du point R = P + Q, résultant de l’addition de deux points P et Q d’une courbe
elliptique E(K) donnée par une équation de Weierstrass.

Bien entendu, de par la structure de groupe de (E(K),+), on sait que P +O = O+P = P

et le calcul du résultat d’une telle addition est trivial, de même que le cas O + O = O.

Les cas où O est un des deux termes de l’addition de deux points de E(K) ayant été
traités, nous allons nous intéresser au cas où celui-ci n’est aucun des deux termes de l’addi-
tion.

Puisque seules les coordonnées homogènes du point à l’infini O vérifient Z = 0, nous

travaillerons avec les coordonnées non-homogènes.

Les formules permettant le calcul des coordonnées de l’opposé d’un point s’expriment
ainsi :

Définition 9 Opposé d’un point

Soit (xP , yP ) les coordonnées non-homogènes d’un point P de E(K).
Alors son opposé Q = −P a pour coordonnées :
(
xQ = xP
yQ = −yP − a1 xp − a3

Voici les formules explicites permettant d’additionner deux points distincts et non op-
posées (il convient donc de vérifier que les points à additionner ne sont pas opposés) :

Définition 10 Addition
Soient :
– E(K) une courbe elliptique donnée par l’équation de Weierstrass,
y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .
– (xP , yP ) et (xQ , yQ ) les coordonnées non-homogènes respectives de P et Q deux points
non opposés l’un de l’autre, de E(K).
– R = P + Q ∈ E(K) de coordonnées non-homogènes (xR , yR ).
(
x R = λ 2 + a1 λ − a2 − x P − x Q
Alors on a
yR = −(λ + a1 )xR + λxP − xQ
yP −yQ



 λ= xP −xQ
si xP 6= xQ
avec λ tel que :
3xP 2 +2a2 xP +a4 −a1 yP

λ= si xP = xQ


2yP +a1 xP +a3

7
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

Notons que si Q 6= −P et xP = xQ , alors P = Q. Par conséquent, l’addition de P et Q

revient à doubler le point P .

2.6 Multiplication par un entier

Comme nous l’avons vu précédemment, il est possible d’additionner deux points d’une
courbe elliptique. En revanche il n’existe pas de multiplication entre deux points. Grâce à
une succession d’additions, nous allons, cependant, pouvoir définir la multiplication d’un
point par un entier. Cette multiplication est d’autant plus importante que l’exponentiation
modulaire définie sur (Z/pZ)∗ (succession de multiplications d’un élément de (Z/pZ)∗ ) a un
équivalent sur le groupe abélien formé par la courbe elliptique.

Définition 11
Soient E(K) une courbe elliptique, un point P ∈ E(K), et un entier n ∈ N∗ .
On définit les multiples de P par n · P = P
|
+ ·{z
· · + P}.
( n fois
0N · P = O,
Cette définition peut être étendue par
−m · P = m · (−P ).

2.7 Isomorphismes et formes canoniques

L’équation d’une courbe elliptique peut prendre une forme simplifiée, dite canonique.
Cette forme canonique diffère légèrement suivant la caractéristique de K.

Théorème 5
Soient deux courbes elliptiques Ea et Eb définies sur un corps K.
Si Ea et Eb sont isomorphes alors leurs j-invariants sont égaux, ce que l’on note :
j(Ea ) = j(Eb ).

Remarque 3
La réciproque de ce théorème est vraie dès lors que K est algébriquement clos.

Proposition 6
Soit E une courbe elliptique donnée dans K par une équation de Weierstrass.
Alors il existe un isomorphisme (x, y) 7−→ (u2 x + r, u3 y + u2 sx + t) qui ramène cette
courbe à l’une des courbes dont l’équation canonique est donnée dans le tableau suivant :

8
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

Condition Equation Discriminant ∆ j-invariant

Car(K) 6= 2, 3 y = x3 + a4 x + a6
2
−16(4a34 + 27a26 ) 1728 · 4a34 /(4a34 + 27a26 )
j = 0 y 2 + a3 y = x3 + a4 x + a6 a43 0
Car(K) = 2 E
jE 6= 0 y 2 + xy = x3 + a2 x2 + a6 a6 1/a6
j =0 y 2 = x3 + a4 x + a6 −a34 0
Car(K) = 3 E
jE 6= 0 y 2 = x 3 + a2 x 2 + a6 −a32 a6 3
−a2 /a6

Table 2.1 – Equation de Weierstrass et caractéristique du corps de définition

Remarque 4
Cet isomorphisme conserve les propriétés de la courbe.

2.8 Les courbes elliptiques définies sur un corps fini

Nous considèrerons par la suite connues les notions élémentaires sur les corps, à savoir
celles concernant les lois et la caractéristique d’un corps, les isomorphismes de corps ainsi
que le théorème de Wedderburn, énonçant que les corps finis sont commutatifs.

2.8.1 Cardinalité

Définition 12
Le nombre de points du groupe E(Fq ), appelé cardinalité de la courbe elliptique et noté
Card(E(Fq )), est le nombre de solutions de l’équation de Weierstrass (cf p. 3).

Vu comme un polynôme de Fq [Y ], l’équation de Weierstrass est du second degré. De ce

fait il existe, pour chaque valeur de x, au plus deux valeurs de y telles que le couple (x, y)
vérifie cette équation. Puisque x ∈ Fq , il y a q choix de valeurs possibles pour x, et donc en
comptant O, au plus 2q + 1 couples sont solutions de l’équation de Weierstrass.

En moyenne on a une chance sur deux pour que, x étant fixé, l’équation en y admette
des solutions dans Fq .

Ceci est résumé par le théorème suivant :

Théorème 7 Théorème de Hasse

Soit E(Fq ), où q = pn ∈ N, une courbe elliptique.
On a alors :

9
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

√
Card(E(Fq )) = q + 1 ± 2 q

Ce théorème ne fournit qu’un encadrement du nombre de points de la courbe. Or en

cryptographie, il est essentiel de connaître le nombre précis de points de la courbe elliptique
manipulée. Des algorithmes ont donc été construits dans le but de connaître le nombre exact
de points d’une courbe elliptique.

Algorithme de comptage

Les algorithmes de comptage sont devenus un enjeu de taille dans la recherche en crypto-
graphie. Schoof, en 1985, fut le premier à proposer un algorithme de complexité polynômiale
en log q : O(log 8 q). Les travaux d’Atkin, Elkies, puis Couveignes aboutissent à un algorithme
de complexité en O(log 5 q). Le principe de ces algorithmes est donné dans la sous-section
4.2.2.

Théorème 8
Une courbe elliptique E(Fq ), où q = pn , de cardinal q + 1 − t est supersingulière si et
seulement si t ≡ 0 mod(p)

2.8.2 Structure de groupe

Théorème 9 Théorème de Kronecker

Soit G un groupe abélien d’ordre fini, alors il existe une suite (an )n∈N tel que :

– ∀ i ∈ {1, . . . , s − 1}, ni+1 | ni ,

– G∼
= Z/n1 Z ⊕ · · · ⊕ Z/ns Z , où s ≥ 2.

Le groupe G est alors dit de type (n1 , . . . , ns ) et de rang s.

Voici un corollaire de ce théorème appliqué aux courbes elliptiques :

Corollaire 10
E(Fq ) est un groupe abélien de rang 1 ou 2, dit cyclique ou bicyclique.
Le type de ce groupe est (n1 , n2 ) :
i.e. E(Fq ) = Z/n1 Z ⊕ Z/n2 Z avec n2 | n1 et n2 | q − 1.

Théorème 11
E(Fq ) est un groupe de torsion i.e. ∀ P ∈ E(Fq ), ∃ k ∈ N∗ , k · P = O.

10
 CHAPITRE 2. GÉNÉRALITÉS SUR LES COURBES ELLIPTIQUES

Définition 13
On appelle point de m-torsion un point P ∈ E(Fq ), où Fq est la clôture algébrique de
Fq , tel que m · P = O.

Notation 14
On notera E[m] le sous-groupe de E(Fq ) des points de m-torsion, et E(Fq )[m] le sous-
groupe de E[m] des points de m-torsion contenus dans E(Fq ).

La structure de E[m] est donnée par le théorème suivant :

Théorème 12
Soient E(Fq ) une courbe elliptique définie sur Fq , et m un entier naturel.

– Si m est premier avec la caractéristique de Fq , alors :

E[m] = Z/mZ ⊕ Z/mZ.
– Si m est une puissance(de la caractéristique de Fq , alors :
E[m] = {O} si E est supersingulière,
E[m] = Z/mZ sinon.

11
Chapitre 3

Courbes elliptiques et cryptographie

3.1 Introduction

Dans la pratique, les courbes elliptiques destinées à des applications cryptographiques

doivent être définies sur un corps premier Fp ou sur un corps fini F2n .

Les cryptosystèmes utilisant les courbes elliptiques définies sur F2n doivent se plier à
certaines exigences pour garantir une meilleure sécurité. De telles courbes sont cependant
de moins en moins utilisées car le corps F2n est considéré comme trop structuré. Cependant
les calculs sur de tels cryptosystèmes ont l’avantage d’être plus faciles à implémenter.

Les cryptosystèmes utilisant les courbes elliptiques définies sur les corps finis de la forme
Fp peuvent être compromis par l’attaque MOV évoquée dans la section suivante. La taille
des clés utilisées doit alors respecter les critères de sécurité appliqués au problème du loga-
rithme discret dans un corps fini, on perd alors l’intérêt d’utiliser les courbes elliptiques.

Le contenu de ce chapitre a pu être rédigé notamment grâce aux études de Reynald

Lercier [3] et Marc Joyes [2] ainsi que le cours d’Yves Driencourt [4].

12
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

3.2 Courbes elliptiques sur K = F2n

3.2.1 Courbes elliptiques convenables d’un point de vue crypto-

graphique

Dans le cadre des courbes elliptiques définies sur F2n , corps de caractéristique 2, il existe
deux formes simplifiées de l’équation de Weierstrass :

y 2 + xy = x3 + a2 x2 + a6 mod(2n ) (3.1)
y 2 + a3 y = x3 + a4 x + a6 mod(2n ) (3.2)

D’après le tableau 2.1 p.9 donnant les discriminants et les j-invariants de chacune de
ces deux équations, on s’aperçoit que la seconde équation est celle d’une courbe supersingu-
lière (son j-invariant est nul), or les courbes supersingulières sont sujettes à l’attaque MOV :

Attaque MOV

Les travaux menés en 1993 par Menezes, Okamoto et Vanstone, qui ont donné leurs
noms à l’attaque MOV, montrent que le problème du logarithme discret sur E(Fp ) peut être
ramené à celui du logarithme discret dans (Fpk )∗ . En particulier dans le cas de courbes super-
singulières, il peut être ramené à celui du logarithme discret sur Fpk avec k ∈ {1, 2, 3, 4, 6},
généralement k = 2. Cela induit un risque car la réduction à un tel problème se fait en
temps polynomial en O(log p), et la résolution du problème du logarithme discret est alors
réalisable par un algorithme probabiliste sous-exponentiel.

En conclusion, les courbes elliptiques décrites par l’équation (3.2) sont donc à éviter d’où
la définition suivante :

Définition 15
On dira d’une courbe elliptique qu’elle est convenable sur F2n lorsque son équation ca-
nonique est du type (3.1).

3.2.2 Formules explicites des opérations

Opposé
Soit P (xP , yP ) un point d’une courbe
( elliptique E(F2n ).
xQ = x P
Son opposé Q a pour coordonnées :
y Q = xP + y P

13
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

Addition
Soient :
– E(F2n ) une courbe elliptique convenable sur F2n ,

– Deux points de E(F2n ), P (xP , yP ) et Q (xQ , yQ ) non opposés.

Alors si R = (xR , yR ) = P + Q :
(
xR = λ2 + λ + a2 + xP + xQ
yR = (λ + 1) · xR + λ · xP + yP
yP +yQ

 λ= xP +xQ
si xP 6= xQ
où x2P +yP
 λ= xP
si xP = xQ

Multiplication par un entier n ∈ N

Soient E(F2n ) une courbe elliptique, un point P ∈ E(F2n ), et un entier n ∈ N∗ .
Comme précédemment
 nous allons définir la multiplication par un entier par une suc-



n · P =P|
+ ·{z
· · + P}

n fois
cession d’additions : 0N · P = O


(−m) · P = m · (−P )



3.2.3 Exemple

Soient :

– Le corps fini F24 = F2 /< X 4 + X + 1 >

– α ∈ F24 tel que F24 =< α > et racine du polynôme X 4 + X + 1 irréductible sur F24

– La courbe elliptique E(F24 ) définie par l’équation de Weierstrass y 2 + x · y = x3 + α4 ·

x2 + 1

Notons tout d’abord que par construction le corps F24 est tel que

F24 = {[x3 x2 x1 x0 ], (x0 , x1 , x2 , x3 ) ∈ F24 }

où [x3 x2 x1 x0 ] = x3 · α3 + x2 · α2 + x1 · α1 + x0 · α0 .
Il possède donc 16 éléments. En effet, il est constitué de 4 − uplets d’éléments de F2 .
[x3 x2 x1 x0 ] sera appelé écriture vectorielle dans la base canonique B = {α3 , α2 , α1 , α0 }.

Explicitons F24 en fonction de α :

Puisque F24 est un corps de caractéristique 2, (α + 1)2 = α2 + 1. De plus α est une racine
du polynôme X 4 + X + 1, donc α4 + α + 1 = 0, d’où α4 = α + 1.

14
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

Rappelons aussi que |(F24 )∗ | = 15 donc αn = αn mod(15)

.

α5 = α4 · α = (α + 1) · α = α2 + α
α6 = α5 · α = α3 + α2
α7 = α6 · α = α4 + α3 = α3 + α + 1
α8 = (α4 )2 = (α + 1)2 = α2 + 1
α9 = α8 · α = α3 + α
α10 = α9 · α = α4 + α2 = α2 + α + 1
α11 = α10 · α = α3 + α2 + α
α12 = α11 · α = α4 + α3 + α2 = α3 + α2 + α + 1
α13 = α4 + α3 + α2 + α = α3 + α2 + 1
α14 = α4 + α3 + α = α3 + α + α + 1 = α3 + 1

Le tableau suivant donne les correspondances entre l’écriture des éléments de F24 sous
la forme d’une puissance de α, d’une combinaison linéaire d’éléments de B, ainsi que sous
leur forme vectorielle :

Ecriture sous forme Ecriture en combinaison linéaire Ecriture vectorielle

de puissance de α de {α0 , α1 , α2 , α3 } dans la base B
0 0 [0 0 0 0]
α0 1 [0 0 0 1]
1
α α [0 0 1 0]
2 2
α α [0 1 0 0]
3 3
α α [1 0 0 0]
α4 α+1 [0 0 1 1]
5 2
α α +α [0 1 1 0]
6 3 2
α α +α [1 1 0 0]
α7 α3 + α + 1 [1 0 1 1]
8 2
α α +1 [0 1 0 1]
9 3
α α +α [1 0 1 0]
10 2
α α +α+1 [0 1 1 1]
α11 α3 + α2 + α [1 1 1 0]
12 3 2
α α +α +α+1 [1 1 1 1]
13 3 2
α α +α +1 [1 1 0 1]
α14 α3 + 1 [1 0 0 1]

Table 3.1 – Correspondances entre les différentes écritures des éléments de F24

Soit P (1, α6 ) un point de F24 × F24 .

15
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

Montrons que P est un point de la courbe elliptique E(F24 ). Pour cela il suffit de prouver
que leurs coordonnées vérifient l’équation y 2 + xy = x3 + α4 x2 + 1 :

yP2 + xP yP = (α6 )2 + α6 x3P + α4 x2P + 1 = 1 + α4 + 1

= α12 + α3 + α2 = α4
=α+1 =α+1

d’où yP2 + xP yP = x3P + α4 x2P + 1 ⇔ P ∈ E(F2 ).

Nous allons maintenant déterminer les coordonnées du point R = 3 · P :

Dans un premier temps nous calculerons les coordonnées du point Q = 2 · P , puis dans
un second temps nous obtiendrons R = 3 · P par le calcul R = P + Q.

Voici le calcul des coordonnées du point Q = 2P :

Commençons par calculer le terme λ défini plus haut (dans le cas "P = Q") :

12 + α6
λ = = α6 + 1 = α3 + α2 + 1 = α13
1

On a donc :

( (
xQ = (α13 )2 + α13 + α4 xQ = α11 + α3 + α2 + 1 + α + 1
⇔
yQ = (α13 + 1)xQ + α13 + α6 y = α 6 xQ + α 3 + α 2 + 1 + α 3 + α 2
( Q
xQ = 0
⇔
yQ = 1

Vérifions que le point Q (0, 1) appartient également à la courbe E(F24 ) :

2
yQ + xQ y Q =1 x3Q + α4 x2Q + 1 =1

Calculons ensuite le point R = 3 · P = P + Q :

Le calcul du terme λ (dans le cas "P 6= Q") donne :

1 + α6
λ = = α6 + 1 = α3 + α2 + 1 = α13
1+0

16
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

( (
xR = (α13 )2 + α13 + α4 + 1 xR = α11 + α3 + α2 + 1 + α
⇔
yR = (α13 + 1)xR + α13 · 1 + α6 y = (α3 + α2 )xR + α3 + α2 + 1 + α3 + α2
( R
xR = α 3 + α 2 + α + α 3 + α 2 + α + 1
⇔
y = α 6 xR + 1
( R
xR = 1
⇔
y
( R
= α6 + 1
xR = 1
⇔
yR = α13

Le point R (1, α13 ) appartient lui aussi à la courbe E(F24 ) :

yR2 + xR yR = (α13 )2 + α13 x3R + α4 x2R + 1 = 1 + α4 + 1

= α11 + α3 + α2 + 1 = α4
=α+1 =α+1

3.3 Logarithme discret généralisé

Définition 16 Logarithme discret

Soient (G, ◦) un groupe cyclique d’ordre n et γ un élément générateur de G.
Tout élément g du goupe G s’écrit alors comme une puissance de γ (si la loi ◦ est noté
multiplicativement) i.e.

∀g ∈ G, ∃! k ∈ Z/nZ, g = γ k .

On peut ainsi construire un isomorphisme logγ de G dans Z/nZ. Cet isomorphisme est
appelé logarithme discret de base γ.
On appelle alors problème du logarithme discret le problème qui consiste à déterminer
k connaissant γ et g = γ k .

Définition 17 Problème du logarithme discret généralisé

Soient :
– (G, ◦) un groupe fini d’ordre n,
– γ un élément de G,
– H =< γ >= {γ i = γ ◦ . . . ◦ γ , i ≥ 0} le sous groupe de G engendré par γ,
| {z }
i fois
– δ un élément de H

( problème du logarithme discret généralisé consiste à déterminer l’unique n ∈ N tel

Le
0 ≤ n ≤ |H| − 1
que
γn = δ

17
 CHAPITRE 3. COURBES ELLIPTIQUES ET CRYPTOGRAPHIE

Remarque 5
Lorsque la loi de groupe est notée additivement, ce qui est le cas des groupes qui nous
concernent, on note alors la succession d’opérations par une multiplication et non une puis-
sance.
Ce problème peut être difficile suivant le groupe dans lequel il est posé. Ainsi le niveau
de sécurité du cryptosystème basé sur les courbes elliptique dépend de la courbe elliptique
utilisée.

Voici le problème du logarithme discret généralisé écrit avec les notations propres aux
groupes des points de courbes elliptiques :

Définition 18 Problème du logarithme discret généralisé appliqué aux courbes elliptiques

Soient :
– (E(K), +) le groupe des points d’une courbe elliptique,
– P un point de E(K) d’ordre (n,
Q=k·P
– Q un point de E(K) tel que
k≤n
Connaissant la courbe E(K) et les points P et Q de E(K), déterminer l’entier k.

18
Chapitre 4

Problèmes liés à l’utilisation des

courbes elliptiques en cryptographie

Les travaux de Tanja Lange et David Bernstein [10], ceux de Samuel Grau [9] et
de Pierrick Gaudry [12], mais également les rapports de stage de Christophe Arene [8] et
Miguel Garcia [11], ont permis la rédaction de ce chapitre.

Comme nous allons le voir par la suite, l’implémentation des opérations sur une courbe
elliptique varie suivant le choix de la représentation utilisée pour définir cette courbe. L’ef-
ficacité des algorithmes de calcul de l’ordre d’un point dépend de cette implémentation. Ce
choix est donc primordial.

Naturellement la sélection de la courbe elliptique est elle aussi décisive pour assurer un
niveau de sécurité suffisant. Nous évoquerons donc les recommandations du NIST.

4.1 Généralités sur l’implémentation des opérations

Dans cette partie nous présenterons les algorithmes de calculs sur les points d’une courbe
elliptique.

Quel que soit le corps de définition d’une courbe elliptique, les formules explicites des
opérations sur les points sont similaires.
Pour plus de clarté nous étudierons donc le cas d’une courbe définie sur F2n , les notations
associées étant plus simples.

Soit E(F2n ) une courbe elliptique représentée en coordonnées affines (ou non-homogènes)
et donnée par l’équation :

y 2 + xy = x3 + a2 x2 + a6 .

Lorsque le modèle de Weierstrass est utilisé, l’addition définie sur une courbe elliptique
est décomposée en deux cas suivant que l’on additionne deux points distincts ou qu’on

19
 CHAPITRE 4. PROBLÈMES LIÉS À L’UTILISATION DES COURBES ELLIPTIQUES EN
CRYPTOGRAPHIE

double un point. Deux algorithmes sont donc employés pour l’addition.

Voici deux algorithmes effectuant chacun une de ces opérations sur la courbe elliptique
E(F2n ), le premier additionnant deux points distincts, le second doublant un point :

Addition de 2 points distincts

Entrées : P = (xP , yP ), Q = (xQ , yQ ) ∈ E(F2n ).
Sorties : R = P + Q = (xR , yR ) ∈ E(F2n ).
Début
X ← xP + xQ ;
y +y
λ ← PX Q ;
x R ← λ 2 + λ + X + a2 :
yR ← (λ + 1)xR + λxP + yP ;
Retourner (xR , yR ) ;
Fin

Table 4.1 – Algorithme d’addition de deux points distincts

Double d’un point

Entrées : P = (xP , yP ) ∈ E(F2n ).
Sorties : R = 2P = (xR , yR ) ∈ E(F2n ).
Début
λ ← xP + xyPP ;
xR ← λ2 + λ + a2 :
yR ← x2P + λxR + xR ;
Retourner (xR , yR ) ;
Fin

Table 4.2 – Algorithme de doublement d’un point

Le calcul de l’opposé d’un point d’une courbe elliptique peut être exécuté par l’algorithme
suivant :

Opposé d’un point

Entrées : P = (xP , yP ) ∈ E(F2n ).
Sorties : R = −P ∈ E(F2n ).
Début
xP ← xP :
y P ← xP + y P ;
Retourner (xP , yP ) ;
Fin

Table 4.3 – Algorithme de calcul de l’opposé d’un point

20
 CHAPITRE 4. PROBLÈMES LIÉS À L’UTILISATION DES COURBES ELLIPTIQUES EN
CRYPTOGRAPHIE

L’algorithme suivant, qui utilise ceux décrits précédemment, permet de traiter l’addition
dans un cadre plus général :

Addition de 2 points
Entrées : P = (xP , yP ), Q = (xQ , yQ ) ∈ E(F2n ).
Sorties : R = P + Q = (xR , yR ) ∈ E(F2n ).
Début
Si (P = O) alors
Retourner Q = (xQ , yQ ) ;
FinSi
Si (Q = O) alors
Retourner P = (xP , yP ) ;
FinSi
Si (P =Opposé d’un point(Q)) alors
Retourner O ;
FinSi
Si (P = Q) alors
Retourner Double d’un point(P ) ;
Sinon
Retourner Addition de 2 points distincts(P, Q) ;
FinSi
Fin

Table 4.4 – Algorithme généralisé du calcul d’une addition

Un autre calcul, très important dans le cadre de la cryptographie, est celui qui permet
la multiplication d’un point par un entier. En effet, cette opération est indispensable pour
appliquer le problème du logarithme discret. Voici un algorithme qui effectue ce calcul :

Multiple d’un point

Entrées : k = (kt , . . . , k1 , k0 )2 ∈ N, P = (xP , yP ) ∈ E(F2n ).
Sorties : R = kP = (xR , yR ) ∈ E(F2n ).
Début
Q ← O;
Pour i de t à 0 faire
Q ← 2Q ;
Si ki = 1 alors
Q←Q+P ;
FinSi
FinPour
Retourner Q ;
Fin

Table 4.5 – Algorithme du calcul d’un multiple d’un point

21
 CHAPITRE 4. PROBLÈMES LIÉS À L’UTILISATION DES COURBES ELLIPTIQUES EN
CRYPTOGRAPHIE

Comme nous pouvons le constater, le calcul de l’addition de deux points ainsi que le
doublement d’un point consiste à effectuer un inverse, deux multiplications et une élévation
au carré. Cependant, calculer l’inverse d’un élément de F2n est obtenu à l’aide d’un algo-
rithme dont la complexité est élévée.

Ce problème peut être contourné en choisissant de représenter cette courbe elliptique à

l’aide, par exemple, des coordonnées projectives (ou homogènes). Elle est alors définie par
l’équation :

Y 2 Z + XY Z = X 3 + a2 X 2 Z + a6 Z 3 .

En effet, le résultat R (XR : YR : ZR ) de l’addition de deux points de la courbe elliptique

P (XP : YP : ZP ) et Q (XQ : YQ : ZQ ) est donné par :





A = YP ZQ + YQ ZP
XR = BE B = XP ZQ + XQ ZP



 

YR = C(AXP + BYP )ZQ + (A + B)E où C = B2
ZR = B 3
 
 


 D = ZP ZQ
E = (A2 + AB + a2 C)D + BC



Les coordonnées du point Q = 2P , doublement du point P , s’obtient à l’aide des formules

suivantes :





A = XP2
XQ = CE B = A + YP ZP



 

YQ = BE + C(E + A2 ) où C = XP ZP
D = C2
 

ZQ = CD 



E = B(B + C) + a2 D



En coordonnées projectives il n’y a donc pas de calcul d’inverse pour l’addition ni pour
le doublement d’un point.
Une addition nécessite alors seize multiplications et deux élévations au carré, un double-
ment demande quant à lui huit multiplications et trois élévations au carré.
Dans chacun de ces deux cas, le calcul de l’opposé ne nécessite qu’une somme.

Le fait que l’addition de deux points P et Q d’une courbe elliptique nécessite des formules
distinctes selon que P soit égal ou non à Q peut rendre le cryptosystème sensible à l’attaque
nommée side-channel attack. Celle-ci consiste, en effet, à détecter de manière physique une
différence entre les deux cas, basée sur le temps de calcul, l’énergie consommée, voire même
le son produit lors des calculs.

Depuis peu, l’apparition d’un nouveau modèle de courbes elliptiques, le modèle d’Ed-
wards, unifiant les formules d’addition et de doublement, a permis de réduire le temps de
calcul des opérations et de faire face à ce type d’attaque.

22
 CHAPITRE 4. PROBLÈMES LIÉS À L’UTILISATION DES COURBES ELLIPTIQUES EN
CRYPTOGRAPHIE

4.2 Calcul de l’ordre d’un point et d’une courbe ellip-

tique

4.2.1 Calcul de l’ordre d’un point P

Déterminer les coordonnées d’un point P d’une courbe elliptique E(K) revient à fixer
aléatoirement un élément x de K et vérifier que l’équation de Weierstrass définissant cette
courbe, alors ramenée à une équation du second degré, admet une solution y ∈ K. De par la
structure de corps de K, les formules de résolution des racines d’un trinôme sont valables,
On peut donc facilement déterminer y ∈ K.

Connaissant les coordonnées d’un point P et la factorisation en produit de facteurs pre-

miers de l’ordre de E(K), il est possible de déterminer l’ordre de P en temps polynomial.

Voici un algorithme qui nous permet un tel de calcul :

Ordre d’un point

Entrées : P = (xP , yP ) ∈ E(F2n ), #E = p1 e1 · . . . · pr er .
Sorties : k ∈ N
Début
m ← #E
Pour i de 1 à r faire
m ← m/pi ei ;
Q ← mP ;
Tant que Q 6= 0 faire
Q ← pi Q ;
m ← mpi ;
FinTantQue
FinPour
Retourner m ;
Fin

Table 4.6 – Algorithme du calcul de l’ordre d’un point d’une courbe elliptique

4.2.2 Calcul de l’ordre d’une courbe E(K)

Le théorème de Hasse (énoncé p 9) sur le nombre de points d’une courbe elliptique

fournit l’approximation :
√
|E(Fq )| = q + 1 ± 2 q

23
 CHAPITRE 4. PROBLÈMES LIÉS À L’UTILISATION DES COURBES ELLIPTIQUES EN
CRYPTOGRAPHIE

Afin de trouver le nombre exact de points, il est suffisant de trouver ce nombre modulo
√
R > 4 q.

L’algorithme de Schoof calcule donc

q + 1 − |E(Fq )| (mod ri )
Q
pour plusieurs petits nombres premiers ri , où ri = R. Le résultat final est obtenu par
combinaison via le théorème des restes chinois.

24
Chapitre 5

Application des courbes elliptiques à

la cryptographie

5.1 L’échange de clés de Diffie-Hellman

EC-DH (Elliptic Curve Diffie Hellman) est un protocole d’échange de clés secrètes.

En voici une description :

Alice et Bob souhaite disposer d’une clé secrète commune. Il se mettent d’accord sur le
choix d’une courbe elliptique E(K) où K est un corps fini, et sur le choix d’un point P de
cette courbe. Ces choix sont connus de tous.
Ils choisissent alors respectivement un entier a et un entier b. Ces entiers constitueront
leurs clés privées.
Chacun d’eux calcule alors respectivement A = aP et B = bP .
Alice envoie alors à Bob le point A et celui-ci lui envoie le point B.
Alice effectue alors le calcul aB = abP et Bob le calcul bA = abP . Ils disposent mainte-
nant d’une clé secrète commune abP .

Si quelqu’un, que nous appelerons Oscar, espionne leurs communications et intercepte

les points A et B, le problème du logarithme discret garantit qu’il ne sera pas en mesure de
déterminer les entiers a et b. Il ne pourra donc pas reconstituer la clé abP commune à Alice
et Bob.

Oscar dispose cependant d’une manière d’espionner ces conversations s’il est en mesure
de substituer un nouveau message à celui d’Alice puis à celui de Bob :
La courbe E(K) et le point P étant connus de tous, il peut choisir un entier c et calculer
le point C = cP .

25
 CHAPITRE 5. APPLICATION DES COURBES ELLIPTIQUES À LA CRYPTOGRAPHIE

Oscar intercepte le message d’Alice, récupère le point A et le remplace par C.

De même il intercepte le message de Bob, récupère le point B et le remplace par C.
Il calcule alors les points QA = cA = caP et QB = cB = cbP .
De leurs côtés Alice et Bob ont reçu tous les deux le point C = cP et ont alors calculé
respectivement les points aC = acP = QA et bC = bcP = QB .
Lorsque Alice envoie un message à Bob, elle le chiffre alors avec la clé QA .
Oscar intercepte ce message, le déchiffre car il est en possession de la clé QA , puis le
rechiffre à l’aide de la clé QB . Il envoie le message chiffré, modifié ou non, à Bob qui le
déchiffre grâce à sa clé QB .

Oscar doit alors intercepter toutes les conversations entre Alice et Bob pour ne pas que
ceux-ci s’aperçoivent de sa présence. En effet ne disposant pas de clé commune, Alice et Bob
ne sont plus en mesure de déchiffrer ces messages sans l’intervention d’Oscar.

La faiblesse de ce protocole réside donc dans le fait qu’il ne permet pas d’authentifier les
auteurs des messages émis.

5.2 La signature EC-DSA

Nous allons maintenant présenter une utilisation des courbes elliptiques : Le schéma de
signature électronique EC-DSA (Elliptic Curve Digital Signature Algorithm) dont le fonc-
tionnement est similaire à la signature DSA.

Le mécanisme DSA (Digital Signature Algortihm) repose sur le problème du logarithme

discret sur les corps finis. Comme nous l’avons vu précédemment, il peut donc être appli-
qué aux courbes elliptiques. L’intérêt de cette pratique provient du fait que, à un niveau
de sécurité équivalent, l’utilisation des courbes elliptiques permet des calculs plus rapides
et réclame moins de mémoire par rapport à l’utilisation d’un corps fini. En effet, pour un
niveau de sécurité équivalent, cet algorithme travaille avec des clés de plus petite taille, par
exemple 160 bits au lieu de 1024 pour le DSA classique, tout en conservant les tailles des
signatures.

Rappelons l’algorithme DSA appliqué aux courbes elliptiques :

Soient :
– un point P d’une courbe elliptique E(K) d’ordre n premier où K est un corps fini,
– H une fonction de hachage,
– m le message à signer.

La mise en place du schéma EC-DSA nécessite une paire de clés, l’une publique, l’autre
privée. La clé publique est accessible à tous et permet à chacun de vérifier l’intégrité du
message et l’authenticité de l’entité qui l’a envoyé.

Préparation des clés :

26
 CHAPITRE 5. APPLICATION DES COURBES ELLIPTIQUES À LA CRYPTOGRAPHIE

Alice souhaite envoyer un message m signé par le protocole EC-DSA à Bob. Pour cela
elle va choisir une paire de clé (clé publique, clé privée) en procédant comme suit :
– Elle choisit un entier s entre 1 et n − 1.
– Elle calcule Q = sP .
– Sa clé publique sera Q et sa clé privée s = logP (Q).

On remarque que c’est le problème du logarithme discret de base P qui garantit la dif-
ficulté de déterminer la clé privée s connaissant la clé publique Q.

Signature :
Alice dispose maintenant de la paire de clés dont elle a besoin. Pour signer son message
elle procède ainsi :
– Elle choisit de manière aléatoire un nombre k entre 1 et n − 1.
– Elle calcule :
– kP = (x, y)
– u = x mod n
– v = H(m)+su
k
mod n où H(m) est une fonction de hachage
– Si u ou v sont nulles, elle recommence, sinon la signature est la paire (u, v).

Vérification :
Bob reçoit le message m signé par le couple (u,v), il doit :
– contrôler que u et v sont bien entre 1 et n − 1.
– vérifier que u = x mod n sachant que (x, y) = ( H(m)
v
mod n)P + ( uv mod n)Q.
– vérifier que Q est différent de (0, 0) et que Q appartient bien à la courbe elliptique
E(K).
– vérifier que nQ donne (0, 0).
Justification :
Quiquonque voudrait se faire passer pour Alice devrait être en mesure d’envoyer un
couple (u, v) vérifiant :

(
u = x mod n
(x, y) = ( H(m)
v
mod n)P + ( uv mod n)Q.
Pour cela il devra alors être capable de déterminer s connaissant Q, et donc résoudre le
problème du logarithme discret.

5.3 Normes actuelles et recommandations

Dans le cadre de son programme de modernisation cryptographique, l’Agence de Sécurité

Nationale des Etats-Unis (NSA) a promulgué un ensemble d’algorithmes cryptographiques

27
 CHAPITRE 5. APPLICATION DES COURBES ELLIPTIQUES À LA CRYPTOGRAPHIE

appelé Suite B.

Suite B contient les indications suivantes :

– pour la signature : ECDSA, avec les courbes construites sur un corps premier Fp où p
est un entier respectivement de taille 256 bits et 384 bits, approuvées par FIPS 186-2
– pour l’échange de clé : ECDH ou ECMQV, avec les mêmes courbes que précédemment,
recommandées par NIST Special Publication 800-56A

28
Chapitre 6

Conclusion

Les cryptosystèmes basés sur les courbes elliptiques se posent en alternative efficace face
à l’incontournable RSA. En effet, ils exploitent un problème mathématique différent, qui est
réputé pour sa solidité égale à RSA pour des clés de longueur bien inférieure. Cela les rend
parfaitement adaptés aux utilisations embarquées, comme les cartes à puce par exemple, où
la mémoire et la puissance des processeurs ne sont pas suffisants pour réaliser en un temps
convenable les calculs exigés par RSA.

De nos jours la cryptographie est en perpétuelle évolution afin de pouvoir répondre aux
besoins de sécurisation des données qui ne cessent d’augmenter. En effet, les cryptosystèmes
se doivent d’être performants face à des attaques de plus en plus nombreuses. C’est pourquoi
nous ne pouvons pas prédire combien de temps les cryptosystèmes basés sur les courbes
elliptiques seront les plus efficaces au niveau sécurité. Cependant, l’univers des courbes
elliptiques étant très vaste, ces dernières font toujours l’objet de recherches en cryptologie
ainsi que dans d’autres domaines tels que la mécanique.

29
Table des figures

2.1 Représentation de E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

30
Liste des tableaux

2.1 Equation de Weierstrass et caractéristique du corps de définition . . . . . . 9

3.1 Correspondances entre les différentes écritures des éléments de F24 . . . . . 15

4.1 Algorithme d’addition de deux points distincts . . . . . . . . . . . . . . . . . 20

4.2 Algorithme de doublement d’un point . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Algorithme de calcul de l’opposé d’un point . . . . . . . . . . . . . . . . . . 20
4.4 Algorithme généralisé du calcul d’une addition . . . . . . . . . . . . . . . . . 21
4.5 Algorithme du calcul d’un multiple d’un point . . . . . . . . . . . . . . . . . 21
4.6 Algorithme du calcul de l’ordre d’un point d’une courbe elliptique . . . . . . 23

31
Bibliographie

[1] Stéphane Ballet, Cours de cryptographie, M2 MINT, Université de la Méditerranée

Aix-Marseille II, 2008.

[2] Marc Joye, Introduction élémentaire à la théorie des courbes elliptiques, UCL Crypto
Group Technical Report Series, 1995.
http : //sciences.ows.ch/mathematiques/CourbesElliptiques.pdf

[3] Reynald Lercier, Courbes elliptiques et cryptographie, Sécurité des systèmes d’infor-
mation, 2004.
http : //www.chear.def ense.gouv.f r/f r/think_tank/archives/rstd/64/rstd64p59.pdf

[4] Yves Driencourt, Le problème du logarithme discret et les courbes elliptiques, Cours
de DEA, Université de la Méditerranée Aix-Marseille II, 2001.
http : //math.univ − bpclermont.f r/ rebolledo/page − f ichiers/projetM ichael.pdf

[6] Benjamin Jeanne et Thierry Pern sous la direction de Jean-Marc Couveignes,

Courbes elliptiques et leurs applications à la cryptographie, GRIM Université de
Toulouse II Le Mirail et ESM Saint-Cyr, 1999.

[7] Douglas Stinson, Cryptographie : Théorie et pratique, International Thomson Publi-

shing France, 1995.

[8] Christophe Arene, Etude d’un nouveau modèle pour les courbes elliptiques, Rapport
de stage M2 MDFI, Université de la Méditerranée Aix-Marseille II, 2008.

[9] Samuel Grau, Courbes elliptiques Implémentation de la signature électronique,

Université de Rouen, 2004/2005.
http : //www.scribd.com/doc/5078124/Courbes − Elliptiques − Implementation −
de − la − Signature − Electronique

[10] Tanja Lange et David Bernstein, Faster addition and doubling on elliptic curves,
Asiacrypt, 2007.
http : //cr.yp.to/newelliptic/newelliptic − 20070906.pdf

32
 BIBLIOGRAPHIE

[11] Miguel Garcia, Développement sur les courbes de Koblitz, Rapport de stage M2
MINT, Université de la Méditerranée Aix-Marseille II, 2008.

[12] Pierrick Gaudry, Algorithmes de comptage de points d’une courbe définie sur un
corps fini, LORIA CNRS Nancy 2006.
http : //www.loria.f r/ gaudry/publis/pano.pdf

[13] Wikipedia, Elliptic Curve Digital Signature Algorithm (ECDSA).

http : //f r.wikipedia.org/wiki/Courbe_elliptique

[14] NSA, NSA Suite B Cryptography.

http : //www.nsa.gov/ia/programs/suitebc ryptography/index.shtml

[15] Pierre Barthélémy, Robert Rolland et Pascal VéronCryptographie, principes et

mises en oeuvre, Lavoisier, 2005.

33