Courbes elliptiques

-

Livres
274 pages
Lire un extrait
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Cet ouvrage propose une introduction aux courbes elliptiques pour la cryptographie. Il décrit leur utilisation pour la protection de l'information et présente les développements les plus récents, en particulier la cryptographie bilinéaire, rendant des services de sécurité avancés comme le chiffrement avec l'identité.
Cette approche didactique de la géométrie algébrique est accessible aux étudiants en mathématiques qui trouveront dans l'ouvrage courbes elliptiques les démonstrations de tous les résultats. Les cryptologues y puiseront les éléments et les algorithmes nécessaires aux réalisations les plus sûres et les plus efficaces de cryptographie elliptique.
Introduction. Chapitre 1. La cryptographie elliptique. Chapitre 2. Fonctions et diviseurs. Chapitre 3. Morphismes. Chapitre 4. Points de torsion. Chapitre 5. L'accouplement de Weil. Chapitre 6. Dénombrement des points. Chapitre 7. Le problème du logarithme discret. Chapitre 8. Loi de réciprocité de Weil. Chapitre 9. Isogénies. Exercices. Solutions des exercices. Bibliographie. Index.

Sujets

Informations

Publié par
Date de parution 08 février 2010
Nombre de visites sur la page 43
EAN13 9782746240551
Langue Français

Informations légales : prix de location à la page 0,0382 €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème




































Courbes elliptiques

















© LAVOISIER, 2010
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2392-9
ISSN 1242-7691


Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part,
que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
didentification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, March 2010.





































Courbes elliptiques
une présentation élémentaire

pour la cryptographie

Philippe Guillot



Collection dirigée par Jean-Charles Pomerol



CHRISMENTClaudeet al.–Bases de données relationnelles, 2008.

BANÂTREMichelet al.–Informatique diffuse, 2007.

BARTHÉLEMYPierre, ROLLANDRobert et VÉRONPascal –Cryptographie, 2005.

CARDONAlain –La complexité organisée : systèmes adaptatifs, 2004.

FOURNIERJean-Claude –Théorie des graphes et applications, 2005.

PARISStéphane –Le multimédia et la compression, 2009.

PARISStéphane –Le multimédia,2009.

PIERSONJacky –La biométrie, 2007.

POLIAlain et GUILLOTPhilippe –Algèbre, confidentialité et intégrité en
multimédia, 2009.

POLIAlain et GUILLOTPhilippe –Algèbre et protection de l’information, 2005.

VARRETTESébastien et BERNARDNicolas –Programmation avancée en C
avec exercices corrigés, 2006.

VERDRETPhilippe –De Perl à Java : programmation des expressions régulières,
2004.

Introduction

Table des matières

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 1. La cryptographie elliptique. . . . . . . . . . . . . . . . . . . . .
1.1. Cryptographieavec un groupe. . . . . . . . . . . . . . . . . . . . . . .
1.2. Groupedes points d’une courbe elliptique. . . . . . . . . . . . . . . .
1.3. Algorithmespour la multiplication .. . . . . . . . . . . . . . . . . . . .

Chapitre 2. Fonctions et diviseurs. . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Fonctionsrationnelles sur la droite projective .. . . . . . . . . . . . . .
2.2. Fonctionspolynomiales surE. . . . . . . . . . . . . . . . . . . . . . .
2.3. Fonctionrationnelle surE. . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. Diviseurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Droites. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6. Réductiond’un diviseur. . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7. Associativitéde l’addition des points. . . . . . . . . . . . . . . . . . .
2.8. Sommed’un diviseur. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 3. Morphismes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1. Applicationrationnelle .. . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Valeurd’un morphisme. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Indicede ramification. . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Isogénies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Lesmorphismes ont une ramification constante. . . . . . . . . . . . .
3.6. Isogéniesséparables, degré d’une isogénie. . . . . . . . . . . . . . . .

Chapitre 4. Points de torsion. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1. Legroupe den–torsion .. . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Lamultiplication parn. . . . . . . . . . . . . . . . . . . . . . . . . . .

9

11
11
15
24

35
36
41
44
53
55
57
58
63

65
65
66
68
71
73
74

77
77
78

6

Courbes elliptiques

4.3. Structuredu groupe den-torsion . . . . . . . . . . . . . . . . . . . . . .
4.4. Lespolynômes de division. . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 5. L’accouplement de Weil. . . . . . . . . . . . . . . . . . . . . . .
5.1. Construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Uneautre expression de l’accouplement de Weil. . . . . . . . . . . . .
5.4. Calculde l’accouplement de Weil. . . . . . . . . . . . . . . . . . . . .
5.5. Echangede clé tripartite .. . . . . . . . . . . . . . . . . . . . . . . . . .
5.6. Chiffrementavec l’identité. . . . . . . . . . . . . . . . . . . . . . . . .
5.7. Signaturescourtes avec l’accouplement de Weil. . . . . . . . . . . . .

Chapitre 6. Dénombrement des points. . . . . . . . . . . . . . . . . . . . . .
6.1. Restrictiond’une isogénie au groupe den−torsion .. . . . . . . . . .
6.2. Traceet théorème de Hasse. . . . . . . . . . . . . . . . . . . . . . . . .
6.3. Algorithmepour le dénombrement des points. . . . . . . . . . . . . .
6.4. Nombrede points sur une extension. . . . . . . . . . . . . . . . . . . .

Chapitre 7. Le problème du logarithme discret. . . . . . . . . . . . . . . . .
7.1. Laméthodeλde Pollard (1978). . . . . . . . . . . . . . . . . . . . . .
7.2. Pas-de-bébé-pas-de-géant(Shanks) .. . . . . . . . . . . . . . . . . . .
7.3. Méthodede Pohlig-Hellman. . . . . . . . . . . . . . . . . . . . . . . .
7.4. Groupegénérique .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5. Lecalcul d’indice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6. Complexitédu calcul d’indice. . . . . . . . . . . . . . . . . . . . . . .
7.7. L’améliorationde Waterloo. . . . . . . . . . . . . . . . . . . . . . . . .
7.8. Lelogarithme elliptique. . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 8. Loi de réciprocité de Weil. . . . . . . . . . . . . . . . . . . . . .
8.1. Corpset extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2. Normeet trace d’une extension .. . . . . . . . . . . . . . . . . . . . . .
8.3. Lethéorème des zéros de Hilbert .. . . . . . . . . . . . . . . . . . . . .
8.4. Valuation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.5. Topologieet complétion .. . . . . . . . . . . . . . . . . . . . . . . . . .
8.6. Polygonesde Newton et prolongement de valuation. . . . . . . . . . .
8.7. Preuvede la loi de réciprocité de Weil .. . . . . . . . . . . . . . . . . .

Chapitre 9. Isogénies. . . . . . . . . . . . . . . . . . . .
9.1. Imageinverse .. . . . . . . . . . . . . . . . . . . .
9.2. Complémentsde théorie de Galois. . . . . . . . .
9.3. Décompositiondes isogénies. . . . . . . . . . . .
9.4. Isogéniesinjectives .. . . . . . . . . . . . . . . .

. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .

84
91

97
97
99
104
107
110
110
117

119
120
121
124
127

129
130
131
133
135
139
141
151
153

157
158
165
168
172
176
181
193

205
205
207
212
216

9.5.
9.6.
9.7.
9.8.

Table des matières

Séparabilité et degré des isogénies. . . . . . . . . . . . . . . . . . . . .
Image directe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Isogénie duale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Duale de la somme de deux isogénies. . . . . . . . . . . . . . . . . . .

Exercices

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solutions des exercices

Bibliographie

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Index. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

218
218
221
224

229

245

263

265

Introduction

Les cubiques, courbes définies par une équation polynomiale de degré 3, ont été
étudiées et tracées parNewton à partir de 1666 qui les a classifiées selon leurs
asymptotes et leurs singularités.

Les courbes elliptiques, qui sont par définition des cubiques sans singularité,
conse
tituent un sujet d’étude qui remonte au 19siècle. Elles ont été introduites pour le
calcul des intégrales des fonctions elliptiques surCdans le cadre de l’analyse
complexe. L’étude des courbes elliptiques relève aujourd’hui de la géométrie algébrique.

e
Elles ont trouvé un regain d’intérêt considérable au 20siècle, en particulier pour
leurs applications en cryptographie. Cet intérêt réside principalement dans l’existence
d’une loi de groupe sur l’ensemble des points. Dans ce groupe, le logarithme discret
ne se calcule actuellement qu’en temps exponentiel, et cela en fait un candidat idéal
sur lequel s’appuyer pour définir des fonctions cryptographiques de signature et de
chiffrement à clé publique particulièrement sures et efficaces. Ainsi pour une sécurité
équivalente, l’utilisation des courbes elliptiques conduit à des tailles de clé bien
inférieures, de l’ordre de 256 bits au lieu de1024pour le RSA par exemple, et par voie de
conséquence, à des calculs plus rapides.

Les développements les plus récents de la cryptographie utilisent les courbes
elliptiques pour définir de nouvelles primitives, comme par exemple les systèmes à clé
publique choisie, qui permettent d’utiliser le nom du destinataire comme clé de
chiffrement, s’affranchissant ainsi du besoin de les authentifier. Ces nouvelles
fonctionnalités reposent sur la notion d’accouplement sur une courbe elliptique et certaines ne
sont pas aujourd’hui réalisables autrement.

La plupart des ouvrages sur les courbes elliptiques exigent un prérequis théorique
très élevé, et présentent les courbes elliptiques comme une application de l’étude des
variétés algébriques. D’autres sont incomplets, se réduisent à un formulaire applicatif,

10

Courbes elliptiques

sans donner les preuves des résultats pourtant essentiels et sur lesquels reposent les
fonctions cryptographiques, comme par exemple la loi de réciprocité de Weil.

Or, les cryptographes ont besoin d’une introduction assez précise et complète,
incluant les preuves, pour maîtriser le niveau de sécurité des systèmes qu’ils conçoivent
avec ce nouvel outil.

Cet ouvrage constitue une présentation qui se situe à un niveau assez élémentaire
pour être comprise et maîtrisée par les non-spécialistes, et cependant assez complète
pour aborder tout le développement de la théorie algébrique des courbes elliptiques.

Il ne suppose qu’un niveau d’algèbre assez élémentaire, acquis pour l’essentiel
en licence. De plus, il contient les preuves de tous les résultats qui sont présentés et
utilisés dans les applications. Ceci est indispensable à la fois au mathématicien qui
souhaite approfondir le sujet, mais aussi au cryptographe qui est en charge de définir
un système dont il peut être amené à prouver la sécurité.

Il introduit, en s’appuyant sur l’application très concrète que constitue la
cryptographie elliptique, des notions de théorie deGalois et de géométrie algébrique,
permettant au lecteur de poursuivre vers des développements plus abstraits.

Il est également orienté vers les applications, en présentant les algorithmes qui
permettent de réaliser le plus efficacement ces fonctions cryptographiques.

Cet ouvrage repose sur un cours de cryptographie avancée donnée dans le master
deMathématiques et Applications au Codage et à la Cryptographieà l’Université
Paris 8 depuis 2005. De nombreux exercices, rassemblés en fin d’ouvrage sont destinés
à familiariser le lecteur avec les notions introduites.

Mes remerciements vont à tous ceux sans qui cet ouvrage ne serait pas ce qu’il est,
en particulier les étudiants qui ont suivi le cours, mais également tous ceux qui par
leurs encouragements, leur conseils, leurs relectures, ont grandement contribué à sa
réalisation.

Chapitre 1

La cryptographie elliptique

Le terme raccourci decryptographie elliptiquedésigne l’ensemble des procédures
cryptographiques qui sont réalisables en utilisant la théorie des courbes elliptiques.
Avant d’entrer dans le détail de la théorie, ce chapitre donne les principales
applications, les principes généraux et les algorithmes de calcul.

1.1. Cryptographieavec un groupe

Les courbes elliptiques s’inscrivent dans la cryptographieà clé publique, notion
introduite en 1976 parDiffie etHellman pour répondre au problème posé par la la
distribution des clés dans les grands réseaux de télécommunications qui ont émergé à
cette époque.

Cette notion repose sur la notion defonction à sens unique, dont les valeurs sont
faciles à calculer, mais dont les antécédents sont en pratique impossibles à calculer.

La fonction exponentielle en est un exemple typique. Étant donné un groupe
cyn
cliqueGengendré parg, il est en général facile de calculergà partir den, et il existe
des algorithmes efficaces pour le faire, à partir d’une succession de multiplications et
d’élévations au carré. En revanche, l’opération inverse, appelé logarithme discret en
baseg, qui consiste à retrouver l’exposantnà partir de la donnée d’une certaine
puissance degest un problème en général difficile, pour lequel les algorithmes connus à
ce jour ont une complexité prohibitive lorsque les paramètres sont grands.

En guise
phiques qui

d’introduction, sont présentés dans ce
opèrent dans un groupe cyclique fini

paragraphe des services
cryptograquelconque. Nous verrons qu’une

12

Courbes elliptiques

réalisation effective de ces protocoles peut reposer avantageusement sur le groupe des
points d’une courbe elliptique.

REMARQUE.– Dans tout le paragraphe, on note(G,×)un groupe cyclique,
multiplicatif, d’ordreqetgun générateur de ce groupe, alors que le groupe des points d’une
courbe elliptique est noté additivement.

1.1.1.Echange de clé Diffie-Hellmann

Ce protocole d’échange de clé introduit en 1976 a ouvert la voie à la
cryptographie asymétrique. Sa description originale est définie dans le groupe multiplicatif des
entiers modulop, oùpest un grand nombre premier. Il a fallu attendre près de dix
ans, un délai étonnamment long, pour queMiller d’une part, etKoblitz d’autre part,
proposent en 1985 d’étendre ce protocole à d’autres groupes cycliques finis, et en
particulier au groupe des points d’une courbe elliptique.
✎☞ ✎☞
A B
✍✌ ✍✌
x
g
Choisitx∈Z/qZ✲Choisity∈Z/qZ

y xx y
y
Calcule(g)Calcule(g)
g
xy
AetBs’accordent sur le secretg

Z/qZ−→G
La fonction d’exponentiation en basegdansGest .Commeg
x
x→−7g
est un générateur deGet commeqest l’ordre deG, cette fonction est une bijection.

G
La fonction logarithme discret en basegestlog :
g
y

queg=y.

−→
7−→

Z/qZ
, oùℓest tel

Pour que le protocoleDiffie-Hellmann soit sûr, il est nécessaire que le calcul du
logarithme discret dansGsoit un problème difficile.

Le problèmeDiffie-Hellmann calculatoire est par définition le problème,a priori
xy xy
plus facile, qui consiste à calculergà partir de la connaissance deget deg. On
peut résoudre ce problème en calculant des logarithmes discrets, sans qu’on sache
actuellement s’il existe une méthode plus efficace pour le faire.

1.1.2.El GamalLe chiffrement

Ce mécanisme de chiffrement dérive directement du protocole d’échange de clé
Diffie-Hellmann. Il utilise un algorithme symétrique avec une clé de session que seul
le destinataire prévu peut retrouver.

✎☞
A
✍✌
Messagem
Aléar∈Z/qZ

r
(g ,γ)

La cryptographie elliptique
✎☞
B
✍✌
Clé privées∈Z/qZ
s
Clé publiqueg

s r
La clé de session est l’élément deGdonné park= (g).

13

La valeurγ=Ek(m)est le résultat du chiffrement demavec un algorithme
symétrique de chiffrementEquelconque, par exemple le DES, l’AES,etc. Le
cryptor
gramme transmis au destinataire est le couple(g ,γ).

Pour simplifier la présentation, on suppose que les clés de cet algorithme sont des
éléments du groupeG. Au besoin, une fonction de hachageh:G−→ Kprocède à la
mise en forme de cette donnée aléatoire.

r
La donnéegqui accompagneγdans le cryptogramme, est une indication pour
que le destinataire, titulaire de la clé privées, et lui seul, puisse calculer la clé de
r s
session park= (g).

−1
Il peut alors retrouver le message clair en calculantm=E(γ).
k

La sécurité de ce système de chiffrement repose également sur la difficulté du
problème Diffie-Hellmanncalculatoire.

1.1.3.SchnorrLe schéma de signature de

Soitmun message à signer qui appartient à l’ensemble des messagesM.

M ×G−→Z/qZ
SoitH:une fonction de hachage (hash function),
(m, y)→−7H(m, y) =h
qui réalise idéalement une fonction aléatoire donnée et accessible à tous, appelée
égalementoracle aléatoire.
✎☞ ✎☞
A B
✍✌ ✍✌
σ= (h, y)
Clé privéea∈Z/qZ

a
Clé publiqueg
y ah r
Aléar∈Z/qZCalculeg /(g) =z(=g)
r
h=H(m, g)Vérifie queh=H(m, z)
y=r+ha

La signature du messagemest constituée du coupleσ= (h, y).

14

Courbes elliptiques

Ce schéma comporte une preuve de sécurité. Si la fonctionHest aléatoire et si
un adversaire sait forger des fausses signatures pour tous les messages, alors il peut
calculer un logarithme discret avec à peu près le même effort. La production de fausses
signatures est donc un problème au moins aussi difficile que le problème du logarithme
discret.

La fonctionHétant aléatoire, s’il peut produire des signatures valides pour deux

messages différents, alors il peut produire deux signatures validesσ= (h, y)etσ=
′ ′
(yh ,), pour le même messagem, obtenues à partir du même aléaret deux fonctions

aléatoiresHetHdifférentes.

Ces signatures étant valides, on a :

y−ah r
H(m, g) =hH(m, g) =h
et
′ ′
′y−ah′ ′r′
H(m, g) =hH(m, g) =h
′ ′r
Avec une forte probabilité,y−ahety−ahsont tous deux égaux àg, donc
′ ′
égaux entre eux.y−ah=y−ah. La clé privéea, qui est le logarithme de la clé

y−y
a
publiquegse retrouve para=.

h−h

1.1.4.Le chiffrement à deux cadenas

Ce système de chiffrement deMassey-Omura permet de transférer en trois passes
un message chiffré, sans échange de clé préalable.
✎☞ ✎☞
A B
✍✌ ✍✌
x
m
Messagem∈G1)✲
x y
Choisitx∈Z/qZ
(m)
2)✛Choisity∈Z/qZ
1/x
x y
c= (m)1/y
3)✲Retrouvem=c

Les trois passes peuvent s’interpréter ainsi :
1) L’émetteur place son message dans une boîte qu’il ferme avec un cadenas et
l’envoie au destinataire.
2) Le destinataire ajoute son propre cadenas et renvoie la boîte à l’émetteur.
3) L’émetteur ôte son cadenas et renvoie la boîte au destinataire, qui peut ainsi
ouvrir la boîte et avoir accès au message.

1.1.5.Choix d’un groupe

Pour qu’un groupe soit utilisable pour ces applications de sécurité, il faut bien sûr
que l’opération de groupe soit calculable avec un algorithme efficace.

La cryptographie elliptique

15

Mais cela n’est pas suffisant. Il faut aussi que le problème du logarithme discret soit
difficile. Un groupe additif(Z/nZ,+)par exemple ne convient pas, car le logarithme
discret est la division et se calcule efficacement avec l’algorithme d’Euclide étendu.


Le groupe multiplicatif(Z/pZ,×)est utilisable. Les meilleurs algorithmes à ce
jour pour le calcul du logarithme discret sont sous-exponentiels, mais restent
surpolynomiaux, ce qui impose de choisir unpassez grand (1024à2048bits). Parmi
ces algorithmes, le calcul d’indice est présenté au paragraphe 7.5 page 139.

L’intérêt d’utiliser le groupe des points d’une courbe elliptique sur un corps fini
réside dans la complexité du calcul du logarithme discret dans ce groupe. Dans la plupart
des cas, le meilleur algorithme utilisable connu à ce jour a une complexité
exponentielle. Ceci autorise l’utilisation de paramètres de taille bien plus réduite (160 à 256
bits) pour une sécurité équivalente, voire supérieure. Les calculs cryptographiques,
bien que plus compliqués, sont plus rapides en raison de la taille plus réduite des
entiers manipulés, et l’attaque est plus difficile.

Pour que le problème du logarithme discret dans un groupe fini soit difficile, nous
verrons au chapitre 7, qu’il est nécessaire que son ordre comprenne dans sa
factorisation un nombre premier assez grand. Pour s’en assurer, il faut pouvoir calculer cet
ordre. L’utilisation du groupe des points d’une courbe elliptique sur un corps fini a été
rendu possible par la découverte par René Schoof en 1985 d’un algorithme efficace de
comptage des points, qui est présenté au chapitre 6.

1.2. Groupedes points d’une courbe elliptique

Cette section est consacrée aux définitions générales ainsi qu’à la présentation de
l’opération d’addition des points. Le fait que cette addition est une loi de groupe sera
démontré au chapitre 2.

1.2.1.Droite projective, plan projectif

SoitFun corps commutatif. Pour les applications cryptographiques, il s’agira en
pratique d’un corps finiFq, oùqest une puissance d’un nombre premier.

n
Pour un entiernsupérieur ou égal à 1, l’ensembleFest l’espace vectoriel de
n∗n
dimensionnsurF. La relationRsur(F) =F\ {0}identifie les éléments d’une
même droite vectorielle.
n∗n∗ ∗
∀(u, v)∈(F)×(F)uRv⇐⇒ ∃λ∈Fu=λv

n∗
Cette relation est une relation d’équivalence sur(F). L’espace projectifPn−1(F)
n∗
est par définition l’ensemble quotient(F)/R.

16

Courbes elliptiques

– Sin= 2, l’espace projectifP1(F)s’appelle la droite projective surF.
– Sin= 3, l’espace projectifP2(F)s’appelle le plan projectif surF.

Les coordonnées d’un point d’un espace projectif sont appeléescoordonnées
homogènes. Elles ne sont pas toutes nulles et sont définies à une constante multiplicative
près.

n
Soitu= (x1, . . . xn−1, xn)un vecteur non nul de l’espace vectorielF. La classe
deu, notée[u], est la droite vectorielle passant paru. Elle est constituée de tous les
n
vecteurs non nuls deFqui sont proportionnels àu.

x1xn−1
– Sixn6= 0il existe un représentant de[u]de la forme, . . . ,,1. Les
xnxn
points qui satisfont cette condition sont lespoints finisde l’espace projectif.
n
– Sixn= 0, alors les points deFde la forme(x1, . . . , xn−1,0)appartiennent
tous au même hyperplan d’équationxn= 0. Cet hyperplan est une réunion de classes
d’équivalence dans l’espace projectif. Les points qui satisfont cette condition sont les
points à l’infini. Ils constituent l’hyperplan projectif à l’infini.

L’espace projectifPn−1(F)peut ainsi être considéré comme étant la réunion de
l’espace affine de dimensionn−1surFet de l’hyperplan projectif à l’infini. Ainsi :

– La droite projectiveP1(F)est la réunion du corpsFet du point à l’infini∞:
P1(F) =F∪ {∞}.
– Le plan projectifP2(F)est la réunion de l’espace affine de dimension 2 et de la
droite projective à l’infiniD∞:
2
P2(F) =F∪D∞.

Concevoir ainsi l’espace projectifPn−1comme réunion d’un espace affine de
dimensionn−1et d’un élément singulier supplémentaire permet de réduire le nombre
de composantes, au prix d’un traitement particulier pour l’objet à l’infini.

1.2.2.Courbe elliptique, définitions

2
La forme la plus générale d’un sous-ensemble du plan affineFdéfini par une
équation polynomialef(x, y) = 0de degré 3 est :

3 22 3 22
ax+bx y+cxy+dy+ex+f xy+gy+hx+iy+j= 0

[1.1]

Pour s’assurer que le polynôme est effectivement de degré 3, il faut qu’au moins
l’un des coefficientsa,b,coudsoit non-nul.

La cryptographie elliptique

17

Il faut également que le polynômef(x, y)soit absolument irréductible,
c’est-àdire qu’il est irréductible dansF[x, y], oùFdésigne la clôture algébrique deF, afin de
ne pas se ramener à des racines multiples sur un polynôme de degré inférieur.

Dans le plan projectifP2, l’équation 1.1 se transpose en une équation homogène :

3 22 3 2
ax+bx y+cxy+dy+ex z+f xyz+
2 22 3
gy z+hxz+iyz+j z= 0

[1.2]

2
En considérantP2comme la réunion de l’espace affineFet de la droite projective
à l’infini, les points du plan projectif solutions de l’équation 1.2 sont exactement les
solutions de l’équation 1.1 qui sont solutions de 1.2 avecz6= 0, plus lespoints à
l’infinide la courbe, qui sont les solutions de l’équation 1.2 avecz= 0.

La courbe est ditelissesi elle admet une tangente en chaque point, c’est-à-dire
si en tout point(x, y, z)de la courbe, l’application linéaireDxyz: (dx, dy, dz)7→
′ ′ ′
f(x, y, z)dx+f(x, y, z)dy+f(x, y, z)dzn’est pas nulle.
x y z

Par un choix judicieux des coordonnées, on peut simplifier l’équation 1.2 et se
ramener à une forme dite deWeierstrass qui s’exprime en coordonnées affines sous
la forme suivante :

2 32
y+a1xy+a3y=x+a2x+a4x+a6

[1.3]

REMARQUE.– L’indexation des constantesa1,a3,a2,a4eta6ne doit rien au hasard.
Elle est le complément à 6 du degré du monôme, en comptant un degré 2 pourxet un
degré3poury, comme cela sera justifié au paragraphe 2.2.3 page 43.

Selon la caractéristique du corps, on peut encore simplifier cette équation.

2
En caractéristique différente de 2, on peut éliminer les monômesxyetypar le


x1
changement de variables(x, y)−→, y−a1x−a3et se ramener à une
2 2
équation de la forme :
2 32
y=x+ax+bx+c

En caractéristique différente de 2 et 3, on peut encore simplifier en éliminant le

x−3a y
2
monôme enxpar le changement de variables(x, y)−→,et se
rame36 108
ner finalement à une équation de la forme :

2 3
y=x+ax+b

18

Courbes elliptiques

Dans cet ouvrage, on se limitera à l’étude des courbes en caractéristique
de 2 et de 3. Notons seulement qu’en caractéristique 2, l’équation 1.3 peut se
pour aboutir à une équation de la forme suivante :

2 3
y+xy=x+ax+b

différente
simplifier

DÉFINITION1.1.– [définition projective]SoitFun corps de caractéristique différente
de 2 et de 3. On appelle courbe elliptique le sous-ensemble du plan projectifP2(F)
défini par :

3 23 23
E= (x, y, z)∈P2(F)|y z=x+axz+bz
3 2
avecΔ = 4a+ 27b6= 0.

3 23
La conditionΔ = 4a+ 27b6= 0signifie que le trinômex+ax+bn’a pas de
racine double. En effet, siaest non nul, alors le dernier reste lors du calcul du pgcd
3 2
4a+ 27b
3 2
des polynômesx+ax+bet3x+apar l’algorithme d’Euclide est.
2
4a
Sia= 0ce dernier reste estb. Cette condition exprime que la courbe est lisse (voir
exercice 3 page 230).

Lorsquez6= 0, tout point projectif(x, y, z)a un représentant avecz= 1et
l’équation de la courbe devient :

2 3
y=x+ax+b

Lorsquez= 0, c’est-à-dire sur la droite à l’infini, les points deEsatisfont
l’équa3
tionx= 0, c’est-à-direx= 0. Il existe donc un et un seul point de la courbeEsur la
droite projective à l’infini, notéP∞, et constitué des points proportionnels à(0,1,0).

Ces considérations conduisent à la définition affine des courbes elliptiques. Une
2
courbe elliptique est alors considérée comme un sous-ensemble du plan affineF,
auquel a été adjoint un point supplémentaire, appelé point à l’infini, et qui correspond
au point de la courbe situé sur la droite projective à l’infini du plan projectifP2.

DÉFINITION1.2.– [définition affine]SoitFun corps de caractéristique différente de
2 et de 3. On appelle courbe elliptique un ensemble :

2 23
E= (x, y)∈F|y=x+ax+b∪ {P∞},

3 2
avecΔ = 4a+ 27b6= 0, et oùP∞est un élément supplémentaire appelé point à
l’infini de la courbe.

Le point à l’infini est parfois
notation est choisie ici pour éviter
∞de la droite projective.

La cryptographie elliptique

19

notéOou encore∞dans certains ouvrages. La
la confusion avec l’origine(0,0)et avec l’élément

Les figures qui suivent montrent l’aspect de courbes elliptiques définies sur le plan
réel affine. Ces figures aident considérablement l’intuition pour comprendre les
phénomènes sur les courbes elliptiques, mais n’ont de sens que dans le plan réel. En
cryptographie, le corps de base est un corps fini, et les représentations graphiques,
outre qu’elles n’ont pas la même élégance, apportent peu à la compréhension.

R✥



Q✥



P✥
✥P+Q+R=P∞

2 3
y=x−x+ 1
Δ>0

1.2.3.Addition des points

P+Q=−R

2 3
y=x−x
Δ<0

Bien que cela soit abusif si le corps de base n’est pasR, le vocabulaire géométrique
usuel du plan affine réel sera utilisé. Il faudra le comprendre avec un sens purement
algébrique. Par exemple,
– la droite verticale passant par(xP, yP)est la droite d’équationx−xp= 0;

20

Courbes elliptiques

– la tangente en(xP, yP)à la courbe d’équationf(x, y) = 0est la droite passant

′ ′
par(x ,y)et normale au vecteurf(x ,y), f(xonc la droite
P Px P Py P, yP). C’est d
′ ′
ationf x−x) +f(yx ,)
d’équx(xP, yP)(P yP P(y−yP) = 0.

Une loi de composition des points, notée additivement, est définie sur l’ensemble
des points d’une courbe elliptique. Elle repose sur ce résultat :

LEMME1.3.–SoitFun corps algébriquement clos. Une courbe elliptique définie
surFet une droite se coupent en trois points projectifs, en tenant compte de leur
multiplicité.

PREUVE.– Les coordonnées d’un pointP= (x, y)qui appartient à la fois à la courbe
2 3
Ed’équationy=x+ax+bet à la droite(d)d’équationux+vy+w= 0satisfont
le système :


E
(d)

:
:

2 3
y=x+ax+b
ux+vy+w= 0

[1.4]

Siv6= 0, l’équation de la droite permet d’exprimeryen fonction dex. En
substituant dans l’équation de la courbe, on déduit quexest racine d’un polynôme de
degré 3. Le corps étant algébriquement clos, ce polynôme a trois racines qui sont
les abscisses de trois points. L’ordonnée est ensuite déterminée de façon unique par
l’équation de la droite.

Siv= 0, tous les points de la droite ont la même abscissex0. L’équation
homogène de la courbe estux+wz= 0et le point à l’infini de la courbe, dont les
coordonnées homogènes sont[0,1,0]appartient à la droite(d). En substituant cette
valeur dexdans l’équation de la courbe, on trouve queyest solution d’une équation
du second degré. Il existe donc deux autres points(x0, y1)et(x0, y2)qui satisfont le
système 1.4.

Ce résultat est faux dans l’espace affine. On a eu besoin du point à l’infini dans
le second cas. Dans un espace affine, on peut seulement dire que le nombre de points
d’intersection entre une courbe elliptique et une droite est inférieur ou égal à 3.

Ce lemme permet de définir la loi de composition, notée+, sur les points d’une
courbe elliptiqueE. Cette opération est définie par les règles suivantes :
1) L’élément neutre est le point à l’infiniP∞.
2) Si trois points de la courbeP,QetRdeEsont alignés, alors leur somme est
l’élément neutre :P+Q+R=P∞.

La cryptographie elliptique

21

Lorsque les deux pointsPetQdeEont la même abscissexP=xQ, le troisième
point de la courbe qui est sur la droite(P Q)est le point à l’infini. Il résulte de la règle 2
que dans ce cas, la somme de ces deux points est l’élément neutreP∞. Ces points sont
donc opposés. L’opposé du pointP= (xP, yP)est donc le point−P= (xP,−yP).

Si deux pointsPetQdeEn’ont
la courbe en un troisième pointRqui
La somme des pointsPetQdeEest
rapport à l’axe des abscisses.

pas la même abscisse, la droite(P Q)coupe
selon ces règles, est l’opposé de leur somme.
donc obtenue comme le symétrique deRpar

SiP=Q, le double du pointPest obtenu de façon similaire en considérant la
tangente enPà la courbeE.

REMARQUE.– Le choix du point à l’infini comme élément neutre est naturel, mais
arbitraire. Tout autre choix conviendrait autant.

L’ensembleEmuni de la loi ainsi définie est un groupe commutatif. Les axiomes
de la structure de groupe commutatif se vérifient plus ou moins facilement. La
vérification vraiment la plus fastidieuse, et la seule véritable difficulté, est celle de
l’associativité.

Le paragraphe qui suit donne des formules explicites pour la somme de deux
points, et sans préjuger de la confiance apportée par ce type de preuve, une solution
moderne pour établir l’associativité serait d’utiliser un ordinateur muni d’un logiciel
de calcul formel.

En attendant que cette propriété soit démontrée plus facilement au paragraphe 2.4,
page 53 par une étude théorique plus approfondie, signalons juste qu’elle résulte d’un
résultat plus général, théorème despoints alignésde Lamé.

THÉORÈMELamé]1.4.– [théorème des points alignés deSi une courbe elliptique
Eest coupée par trois droitesA1A2A3,B1B2B3etC1C2C3telles que les points
A1B1C1ainsi que les pointsA2B2C2sont alignés, alors les pointsA3B3C3sont
aussi alignés.

Ce résultat implique l’associativité de la loi d’addition des points, car en prenant
B2=P∞, on déduit des hypothèses d’alignement queB3=A1+C1et queC2=
A1+A3. De l’alignement deA3B3C3, on déduit que les sommesA3+ (A1+C1)et
(A3+A1) +C1sont égales, car elles ont le même opposé.

La figure qui suit illustre ce résultat.

22

Courbes elliptiques


B2=P∞
.
.
.
.
.
.
.
.
.
.B3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A1..
.
.
.
.
.
.
..A3
.
.
.
.A2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C3..
.
.
.

1.2.4.Formules d’addition

C1

C2

B1

Comme le point à l’infini est élément neutre, il suffit de ne traiter que le cas où les
deux points sont finis. SoientP= (xP, yP)etQ= (xQ, yQ)deux points distincts et
non opposés (c’est-à-direxP6=xQ) deE. Le coefficient directeur de la droite(P Q)
est :
yQ−yP
λ=
xQ−xP

La droite(P Q)a donc pour équationy=λx+µoùµ=−λxP+yP. Elle coupe la
courbeEen un troisième pointRdont les coordonnées(x, y)vérifient simultanément

y=λx+µcarRest sur la droite(P Q)
2 3
y=x+ax+bcarRappartient à la courbeE

En élevant au carré la première équation, on trouve l’équation enxsuivante qui
doit être satisfaite par l’abscissexSde la sommeS=P+Q:
3 2
x+ax+b−(λx+µ) =0

La cryptographie elliptique

23

Cette équation du troisième degré a déjà pour solutionsxPetxQ. Comme le
coefficient du terme de degré 2 est l’opposé de la somme des racines, la troisième solution
xSvaut :
2
xS=λ−xP−xQ

L’ordonnéeySest l’opposée de celle du pointRqui est donnée par l’équation de
la droite(P Q):
yS=−λ(xS−xP)−yP
3
=−λ+ 2λxP+λxQ−yP

1.2.5.Formule de doublement

LorsqueP=Q= (xP, yP), le raisonnement du paragraphe précédent s’applique
également, en considérant la tangente enPà la courbe. Celle-ci a pour direction la
droite vectorielle d’équation :
′ ′
f(yx ,(x
x P P)x+fy P, yP)y= 0

2 3
oùf(x, y) =y−x−ax−b. SiyP6= 0, le coefficient directeur est :
′2
f+a
x(xP, yP) 3xP
λ=−=

f(, y) 2y
yxPP P

LorsqueyP= 0, la tangente est parallèle à l’axe des ordonnées et2P=P∞.

1.2.6.Formules en coordonnées homogènes

Le calcul du coefficient directeurλnécessite une division dont l’exécution
lente devant les autres opérations. Avec les coordonnées homogènes(x, y, z)
plan projectif, il est possible de se passer de cette division. Le calcul est plus
tant pour le doublement que pour l’addition :

SoitP= (xP, yP, zP),Q= (xQ, yQ, zQ)etS=P+Q= (xS, yS, zS).

est très
dans le
rapide,

Addition.SiP6=Q(addition), le coefficient directeur de la droite(P Q)s’exprime

u u=yQzP−yPzQ
comme une fractionλ=avec .
v v=xQzP−xPzQ
2
u xPxQ
Les coordonnées affines(α, β)de la sommeP+Qsontα=− −
v zPzQ

u xPyP
etβ=−α− −.
v zPzP

24

Courbes elliptiques

Pour obtenir les coordonnées homogènes deP+Q, réduire les trois composantes
3
au même dénominateur qui estv zPzQet correspond à la valeur dezS, puis poser :
2
r=αv zPzQ
2 2
=u zPzQ−v(xPzQ+xQzP)


xS=vr
3 3
On obtientyS=−u(r−xPzQv)−yPzQv.
3
zS=v zPzQ

Ce calcul requiert 13 multiplications et 2 élévations au carré dans le corps de base.
u
Doublement.SiP=Q(doublement), le coefficientλestλ=avec :
v

2 2
u= 3x+az
P P
v= 2yPzP

Les coordonnées affines(α, β)de2Psont :

x ux
2P PyP
α=λ−2etβ=−α− −.
zPv zPzP

3
Le dénominateur commun aux deux composantes estv zPd’où, en posantr=

xS=vr
2 22 23
αv zP, on ar=u zP−2v xPet ensuite,yS=−u(r−v xP)−yPv
3
zS=zPv

Ce calcul requiert en général 9 multiplications et 4 élévations au carré. Si la valeur
du coefficientade l’équation de la courbe vaut 3, alors cela économise une
multiplication dans le calcul deu.

REMARQUE.– Le système de coordonnées jacobiennes, où par définition les
coordon2 3
nées(x, y, z)représentent le point affine(x/z ,y/z), permet de diminuer le nombre
d’opérations dans le corps de base pour le doublement. Ajouter et maintenir une
qua4
trième coordonnée égale àazconduit à un calcul encore plus efficace, on parle alors
de coordonnées jacobiennes modifiées.

1.3. Algorithmespour la multiplication

L’addition des points permet de définir pour tout entiernet tout pointPdeE, les
multiples du pointP:
n P=P+∙ ∙ ∙+P
| {z }
nfois

La cryptographie elliptique

25

Cette opération est définie par récurrence par0P=P∞et pour toutnentier
naturel(n+ 1)P=n P+P. Elle est similaire, en notation additive, à l’élévation à
la puissancenet les mêmes algorithmes peuvent s’appliquer, comme par exemple
l’algorithmesquare and multiply.

Ainsi, l’algorithme usuel pour calculer le multiple d’un point consiste en une
succession d’additions et de doublements en parcourant l’écriture binaire du
multiplicateurn. A chaque itération on effectue un doublement, et les additions correspondent
aux chiffres égaux à 1 dans la décomposition binaire den. Le temps de calcul dépend
du poids binaire den, c’est-à-dire du nombre de chiffres égaux à 1. Plus le poids est
faible, moins il y a d’additions, et plus l’exécution est rapide.

Une particularité de l’opération de groupe d’une courbe elliptique est que la
soustraction est similaire à l’addition, contrairement au groupe multiplicatif des entiers
modulop, où le calcul du quotient, qui utilise l’algorithme d’Euclide, est bien plus lent
que la multiplication. Une décomposition binaire du multiplicateur avec les chiffres
0,+1et−1, peut contenir davantage de zéros, et donc réduire le nombre
d’opérations. On présente dans ce paragraphe lesformes non adjacentesqui sont optimales et
comprennent en moyenne deux tiers de zéros.

Ce paragraphe présente égalementl’échelle de Montgomery. Cette méthode,
comme les suites de Lucas, calcule uniquement les abscisses de deux multiples consécutifs
n Pet(n+ 1)P, l’ordonnéeyétant reconstituée à la fin du calcul.

1.3.1.Forme non adjacente

Un entier peut se décomposer en base 2 avec les chiffres−1,0et1, mais alors la
décomposition n’est plus unique. Par exemple, en notant−1 = 1:

7

=
=

1 + 2 + 4 = 8−1
1112= 10012

DÉFINITION1.5.– [forme non adjacente]On dit qu’une décomposition en base 2 d’un
entier avec les chiffres dans{−1,0,1}est une forme non adjacente (F.N.A.) lorsqu’il
n’y a pas deux chiffres non nuls consécutifs.
EXEMPLE.– La décomposition1310= 1 + 4 + 8 = 11012n’est pas une F.N.A. ;
– La décomposition1310= 1−4 + 16 = 101012est une F.N.A.

La décomposition binaire d’un entiernen base 2 avec des chiffres égaux à0et±1,
que ce soit une forme non adjacente ou non, permet de définir un algorithme de
multiplication parn. Cet algorithme procède par succession d’additions ou de soustractions
et de doublements.