Courbes elliptiques

Philippe Guillot

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

• Algèbre
• Arithmétique
• Mathématiques

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 08 février 2010
• Nombre de lectures: 56
• EAN13: 9782746240551
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

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