Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur, traité Sciences fondamentales AF 172 − 1 Cryptographie Mathématiques par Guy CHASSÉ Maître-Assistant de mathématiques École des Mines de Nantes n peut grossièrement définir la cryptographie comme un ensemble de techniques visant à assurer la sécurité des communications. Un examen rapide de cette sécurité révèle qu’elle peut se présenter sous deux formes assez distinctes suivant les menaces dont on cherche à se prémunir. I Si une entité A envoie un message à une entité B et cherche à rendre inutile l’interception du message à quiconque n’est pas B, le service recherché est celui de la confidentialité : il s’agit de rendre inopérante une attaque passive (écoute téléphonique, ouverture de courrier). La réponse à ce besoin repose sur l’utilisation d’un algorithme de chiffrement. I Reprenons la même configuration. A envoie un message à B, mais on ne se préoccupe plus maintenant de confidentialité ; on veut que B puisse avoir l’assu- rance de la provenance de l’information qu’il reçoit, de son authenticité. On veut 1. Évolution de la cryptographie et vocabulaire.................................. AF 172 – 2 1.1 Cryptographie avant l’informatique........................................................... — 2 1.1.1 Algorithme de César........................................................................... — 2 1.1.2 Substitutions et transpositions.......................................................... — 4 1.1.3 De Vigenère à Kasiski. Statistiques des lettres de l’alphabet ......... — 4 1.1.4 Hasard.................................................................................................. — 4 1.2 Cryptographie moderne.............................................................................. — 5 1.2.1 Un peu de formalisme mathématique.............................................. — 5 1.2.2 Sécurité des algorithmes ................................................................... — 5 2. Mathématiques élémentaires de la cryptographie......................... — 6 2.1 Arithmétique ................................................................................................ — 6 2.1.1 Quelques propriétés de l’anneau des entiers relatifs...................... — 6 2.1.2 Quotients de .................................................................................. — 9 2.2 Polynômes et corps finis............................................................................. — 11 2.2.1 Polynômes en une indéterminée sur un anneau............................. — 11 2.2.2 Polynômes en une indéterminée sur un corps ................................ — 12 2.2.3 Factorisation des polynômes de K [T ] en produits de polynômes irréductibles........................................... — 13 2.2.4 Quotients d’anneaux de polynômes................................................. — 14 2.2.5 Polynômes à plusieurs indéterminées sur un corps K.................... — 14 2.2.6 Théorème chinois............................................................................... — 15 2.2.7 Corps finis ........................................................................................... — 15 2.3 Suites récurrentes linéaires sur un corps fini............................................ — 16 2.3.1 Généralités .......................................................................................... — 16 2.3.2 Suites récurrentes linéaires sur un corps fini. Suites périodiques.............................................................................. — 17 2.3.3 Suite récurrente linéaire et racines du polynôme minimal............. — 17 2.3.4 Séries formelles et suites récurrentes linéaires............................... — 18 2.3.5 Algorithme de Massey-Berlekamp et complexité linéaire d’une suite ..................................................... — 18 2.4 Fonctions booléennes ................................................................................. — 19 Pour en savoir plus........................................................................................... Doc. AF 174 � O