Cours d'algèbre et d'algorithmique : applications à la cryptologie du RSA et logarithme discret

Auteur(s) :

Meunier, Pierre (1944-....) Découvrir l'auteur

Résumé

La cryptologie moderne, aidée par l'ordinateur, a acquis une grande importance dans les mathématiques, elle nécessite une grande connaissance de l'algèbre.

Éditeur(s)
- Cépaduès-éd.
Date
- impr. 2012
Notes
- Index
Langues
- Français
Description matérielle
- 1 vol. (336 p.) : couv. ill. en coul. ; 21 cm
Sujet(s)
- Cryptographie
- Algorithmes
ISBN
- 978-2-36493-014-8
Indice
- 512 Algèbre
Quatrième de couverture
- Comment savoir si un nombre entier est composé ou premier, et dans le cas où il est composé, comment obtenir sa factorisation primaire ?
  Ces questions essentielles de la théorie des nombres sont au centre des préoccupations de tous ceux qui étudient une discipline frontière entre les mathématiques et l'informatique : la cryptologie.
  Science des écritures secrètes, elle utilise des protocoles mathématiques nécessitant une connaissance approfondie en algèbre : groupes, anneaux, corps finis, fractions continues, courbes elliptiques, mais aussi en algorithmique : tests de primalité, algorithmes de factorisation.
  Puissamment aidés par l'ordinateur et la très grande qualité de leurs travaux, les mathématiciens ont permis à la cryptologie moderne, « moteur de la théorie des nombres », d'acquérir des lettres de noblesse incontestables que cet ouvrage souhaite faire partager au public scientifique le plus large possible : étudiants en Classes Préparatoires, étudiants, candidats au CAPES ou à l'Agrégation, ingénieurs, enseignants.
Tables des matières
- - Cours d'algèbre et d'algorithmique
  - Applications à la cryptologie du RSA et du logarithme discret
  - Pierre Meunier
  - Cépaduès
  - Introduction
  - Chapitre 1 Les groupes1
  - 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 (...)ⁿ ; application à la structure des groupes abéliens, cas particuliers des groupes abéliens finis14
  - 1.4.1 Sous-groupes additifs de (...)ⁿ14
  - 1.4.2 Les diviseurs élémentaires d'une matrice à coefficients entiers16
  - 1.4.3 Retour aux sous-groupes de ((...)ⁿ, +)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 finis29
  - 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 (...) - Racines primitives de l'unité dans un corps32
  - 2.2.1 Le groupe multiplicatif d'un corps (...)32
  - 2.2.2 Caractéristiques d'un corps33
  - 2.2.3 Les polynômes cyclotomiques sur un corps (...)35
  - 2.3 Les corps finis ; le corps à p^m éléments40
  - 2.3.1 Un lemme fondamental et ses conséquences40
  - 2.3.2 Le corps à p^m é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 (...)48
  - 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 (...) et (...) [ X ] - Résiduosité quadratique55
  - 3.1 Anneaux quotients de (...)55
  - 3.1.1 Généralités55
  - 3.1.2 Condition nécessaire et suffisante pour que (G_n, (...)) soit cyclique57
  - 3.2 Anneaux quotients dans (...) [ X ]60
  - 3.3 Le théorème chinois dans (...) ou dans (...) [ X ]61
  - 3.4 Algorithmes d'Euclide dans (...) ou dans (...)[X]; applications64
  - 3.5 Résidus quadratiques modulo p premiers - Symbole de Legendre67
  - 3.6 Application à la décomposition de (...)(X) en facteurs premiers sur un corps premier de Frobénius (...) dans un cas particulier utile en cryptologie69
  - 3.6.1 Les polynômes g₁ et g₂ de (...)[X]69
  - 3.6.2 Détermination des polynômes g₁ et g₂70
  - 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és77
  - 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 (...)104
  - 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 : (...), 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ômes 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 (Ademan-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-Gamal143
  - 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 RSA157
  - 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 ((...), *) où * est la loi de convolution, (...) étant un corps fini ayant q éléments et n un entier, n (...) 2179
  - 7.1 La loi de convolution * dans (...)179
  - 7.2 Le groupe (G, *)181
  - 7.3 Etude du cardinal du groupe (G, *) quand q (...) 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 (...) 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 (...) 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 (...) 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 elliptiques213
  - 8.1 Introduction213
  - 8.1.1 Quelques préliminaires213
  - 8.1.2 Le discriminant d'un polynôme de la forme (...) + (...) + q214
  - 8.2 Les courbes elliptiques sur un corps fini ou non de caractéristiques distincte de 2 et de 3215
  - 8.2.1 Définitions et premieres conséquences215
  - 8.2.2 Cas où le corps (...) est fini218
  - 8.2.3 Loi de groupe (additif) sur une courbe elliptique226
  - 8.2.4 La n-addition dans (E((...)), +) : polynômes de division229
  - 8.2.5 Utilisation d'une clôture algébrique (...) du corps (...) : 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 conclusion319
  - 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 (...)324
  - 9.5 En conclusion325
  - Postface327
  - Index329
Origine de la notice:
- FR-751131015