Cours d'algèbre et d'algorithmique
Applications à la cryptologie du RSA et du logarithme discret
Pierre Meunier
Cépaduès-Éditions
Introduction
Chapitre 1 Les groupes
1
1.1 Monoïdes et groupes1
1.1.1 Définitions1
1.1.2 Sous-groupes et groupes quotients2
1.2 Groupes monogènes et groupes cycliques3
1.2.1 Introduction3
1.2.2 Générateurs d'un groupe cyclique4
1.2.3 Sous-groupes d'un groupe cyclique5
1.2.4 Produit de groupes cycliques6
1.2.5 Exposant d'un groupe fini ; cas où ce groupe est
abélien8
1.3 Le problème du logarithme discret dans un groupe cyclique10
1.3.1 Instance du problème10
1.3.2 Algorithme de Shanks (algorithme de collision)11
1.3.3 Algorithme de Pohlig-Hellman11
1.4 Sous-groupes additifs de Zn ; application à la structure
des groupes abéliens ; cas particuliers des groupes
abéliens finis14
1.4.1 Sous-groupes additifs de Zn14
1.4.2 Les diviseurs élémentaires d'une matrice à coefficients
entiers16
1.4.3 Retour aux sous-groupes de (Zn, +)20
1.4.4 Structure des groupes abéliens finis21
1.5 Indicatrice d'Euler24
1.6 Couplages de groupes25
1.6.1 Définition25
1.6.2 Exemples de couplages26
1.6.3 Intérêt de la notion de couplage27
Chapitre 2 Anneaux et corps ; Corps finis
29
2.1 Définitions29
2.1.1 Les anneaux29
2.1.2 Anneaux quotients30
2.1.3 Idéaux maximaux d'un anneau commutatif31
2.2 Les corps - Caractéristique d'un corps - Polynômes cyclotomiques
sur un corps K - Racines primitives de
l'unité dans un corps32
2.2.1 Le groupe multiplicatif d'un corps K32
2.2.2 Caractéristique d'un corps33
2.2.3 Les polynômes cyclotomiques sur un corps K35
2.3 Les corps finis ; le corps à pm éléments40
2.3.1 Un lemme fondamental et ses conséquences40
2.3.2 Le corps à pm éléments42
2.3.3 Les sous-corps d'un corps fini46
2.4 Clôture algébrique d'un corps48
2.4.1 Elements algébriques ; extension algébrique d'un
corps K48
2.4.2 Généralisation49
2.4.3 Clôture algébrique d'un corps50
2.4.4 Etude d'un exemple51
2.4.5 Un résultat utile pour les courbes elliptiques51
2.4.6 Des remarques pour finir52
Chapitre 3 Anneaux Z et K[X] - Résiduosité quadratique
55
3.1 Anneaux quotients de Z55
3.1.1 Généralités55
3.1.2 Condition nécessaire et suffisante pour que (Gn,)
soit cyclique57
3.2 Anneaux quotients dans K[X]60
3.3 Le théorème chinois dans Z ou dans K[X]61
3.4 Algorithmes d'Euclide dans Z ou dans K[X] ; applications64
3.5 Résidus quadratiques modulo p premiers - Symbole de
Legendre67
3.6 Application à la décomposition de Phin(X) en facteurs
premiers sur un corps premier de Frobénius Fp dans
un cas particulier utile en cryptologie69
3.6.1 Les polynômes g1 et g2 de Fp[X]70
3.6.2 Détermination des polynômes g1 et g270
3.6.3 Etude du cas particulier où n>7 et p = 3
(mod 4)71
3.7 Généralisation : le symbole de Jacobi75
3.7.1 Définition75
3.7.2 La réciprocité relative au symbole de Jacobi75
Chapitre 4 Algorithmes - Complexités
77
4.1 Définitions77
4.2 Coût (ie complexité) d'un algorithme - Exemples80
4.2.1 Définitions80
4.2.2 Quelques exemples (de base)81
4.2.3 L'exponentiation rapide dans un monoïde (E, *)82
4.2.4 Cas des algorithmes probabilistes de type (i),
c'est-à-dire fournissant toujours une réponse82
4.3 Algorithmes (ou tests) de primalité de Miller et de
Solovay-Strassen84
4.3.1 Test de primalité de Miller-Rabin84
4.3.2 Test de primalité de Solovay-Strassen89
4.4 Coût des algorithmes génériques de
Shanks et de Pohlig-Hellman91
4.5 Algorithmes de type "index calculus"92
4.6 Compléments mathématiques indispensables pour l'étude
des algorithmes de calcul d'index94
4.6.1 Les fonctions de type sous-exponentiel94
4.6.2 Les entiers B-friables95
4.6.3 Les polynômes à coefficients entiers96
4.6.4 Le résultant de deux polynômes100
4.7 L'algorithme de type index calculus de Kraitchik dans
Fp104
4.7.1 Fonctionnalité et description de cet
algorithme104
4.7.2 Complexité en temps de cet algorithme probabiliste106
4.7.3 Des schémas mesurant les performances109
4.7.4 Etude d'un exemple110
4.8 L'algorithme de type index-calculus de Schirokauer112
4.8.1 Fonctionnalité et schéma du mécanisme112
4.8.2 Calcul de a modulo q113
4.8.3 Détermination d'un couple (s, t)113
4.9 Généralisation : algorithmes de calcul des log-discrets
dans les corps non premiers : Fpn, avec n>2116
4.9.1 Instance du problème116
4.9.2 Quelques records de calcul de logarithme discret
dans un corps non premier119
4.10 Algorithme de factorisation du crible algébrique général
(GNFS=General Number Field Sieve)119
4.10.1 L'idée119
4.10.2 Concrétisation de l'idée120
4.10.3 Mise en forme pratique de l'idée : le corps de
nombres et le polynôme P120
4.10.4 Le crible131
4.10.5 L'algèbre linéaire132
4.10.6 Exemple d'un cas particulier : les nombres de
Cunningham133
4.10.7 Résumé et bilan134
4.11 Des algorithmes déterministes de primalité : les tests
APR-CL et AKS135
4.11.1 Le test APR-CL (Adleman-Pomerance-Rumely-Cohen-Lenstra)135
4.11.2 Le test AKS (Agrawal-Kayal-Saxena)136
Chapitre 5 Les deux grands cryptosystèmes à clé
publique : le RSA et le cryptosystème
El-Gamal
143
5.1 Définitions143
5.1.1 Définition d'un cryptosystème à clé publique143
5.1.2 Définition de la cryptologie144
5.1.3 Les deux principales fonctions "à sens unique"144
5.2 Le cryptosystème RSA146
5.2.1 La clé K du cryptosystème146
5.2.2 Le chiffrement et le déchiffrement146
5.2.3 Des considérations pratiques147
5.3 Le cryptosystème El-Gamal (logarithme discret)149
5.3.1 Création de la clé du cryptosystème149
5.3.2 Le chiffrement et le déchiffrement149
5.3.3 Le logarithme discret et le standard de signature
numérique : le DSS151
5.4 Remarques pour finir153
5.4.1 Cryptographie symétrique et cryptographie asymétrique153
5.4.2 Dis-moi ce que tu veux chiffrer, je te proposerai
alors un protocole adapté156
Chapitre 6 Cryptanalyse du RSA
157
6.1 Quelques compléments mathématiques indispensables157
6.1.1 Proposition157
6.1.2 Les réduites d'un rationnel157
6.2 L'attaque de Wiener du protocole RSA162
6.3 Une autre attaque du RSA168
6.4 Le théorème de Coppersmith169
6.4.1 Instance du problème169
6.4.2 Une première application170
6.4.3 Une variante de la proposition précédente170
6.5 Autres attaques du RSA - Attaque de Håstad172
6.5.1 Cas de deux RSA du type172
6.5.2 Attaque de Håstad172
6.6 Des recommandations et quelques résultats concernant
le RSA173
6.6.1 Des recommandations173
6.6.2 Des résultats174
6.6.3 Des records175
Chapitre 7 Cryptosystème El-Gamal dans (Kn, *)
où * est la loi de convolution, K étant
un corps fini ayant
q
éléments et
n
un
entier, n>2
179
7.1 La loi de convolution * dans Kn179
7.2 Le groupe (G, *)181
7.3 Etude du cardinal du groupe (G, *)
quand q Delta n = 1. Applications ; c.n.s. pour que (G, *)
soit cyclique185
7.3.1 Cardinal de G185
7.3.2 Application : cas où (G, *) est cyclique186
7.3.3 Exposant du groupe (G, *)187
7.4 Cryptosystème El-Gamal dans Kn relativement à un
sous-groupe cyclique H de (G, *)188
7.4.1 Définition188
7.4.2 Sécurité selon le choix de H188
7.5 Cryptosystème El-Gamal dans Kn associé au groupe
(G, *) lorsque celui-ci est cyclique ; cryptosystèmes induits
associés189
7.5.1 Observations générales189
7.5.2 Mise en forme pratique du cryptosystème190
7.5.3 Coût du chiffrement et du déchiffrement192
7.5.4 Amélioration du coût du déchiffrement193
7.5.5 Cryptosystèmes induits associés195
7.6 Exemple de cryptosystème proposé196
7.7 Un cryptosystème dans Fnp lorsque
(G, *) n'est pas cyclique197
7.7.1 Fabrication d'un tel groupe (G, *) et d'un sous-groupe
cyclique H permettant d'élaborer le cryptosystème198
7.7.2 Autre procédé de fabrication d'un sous-groupe
cyclique H d'ordre maximum dans le
cas où le groupe (G, *) n'est pas cyclique200
7.8 Quelques observations algébriques pour finir206
7.9 Annexes numériques et justifications éditoriales207
7.9.1 Une estimation207
7.9.2 Des factorisations (utiles pour un cryptosystème
de ce chapitre)208
7.9.3 Des générateurs (utiles pour un cryptosystème
de ce chapitre)210
7.9.4 Des "explications" concernant la première de
couverture de cet ouvrage211
Chapitre 8 Les courbes elliptiques
213
8.1 Introduction213
8.1.1 Quelques préliminaires213
8.1.2 Le discriminant d'un polynôme de la forme X3 +
pX + q214
8.2 Les courbes elliptiques sur un corps fini ou non de caractéristique
distincte de 2 et de 3215
8.2.1 Définitions et premières conséquences215
8.2.2 Cas où le corps K est fini218
8.2.3 Loi de groupe (additif) sur une courbe elliptique226
8.2.4 La n-addition dans (E(K), +) : polynômes de
division229
8.2.5 Utilisation d'une clôture algébrique (...) du corps
K : le morphisme de Frobénius241
8.2.6 Les couplages de Weil250
8.2.7 L'algorithme de Schoof262
8.2.8 Utilisations cryptographiques des courbes elliptiques276
8.2.9 Algorithme de factorisation de Lenstra à l'aide
des courbes elliptiques281
8.2.10 Des perspectives et une ébauche de généralisation314
Chapitre 9 Chapitre de conclusion
319
9.1 Introduction319
9.2 Les deux modes de chiffrement319
9.2.1 Cryptographie symétrique320
9.2.2 Cryptographie asymétrique320
9.3 Quelques règles et recommandations321
9.4 Des justifications et des perspectives322
9.4.1 Clés symétriques322
9.4.2 Clés du RSA ou d'un cryptosystème El-Gamal
sur un Fp324
9.5 En conclusion325
Annexe : Philosophie du cryptosystème du chapitre 7
327
Postface
335
Index
337