Arithmétique et cryptologie

Introduction
Table des matières
Première partie - Cryptologie à l'ancienne
Chapitre 1 - Historique
I. De l’Antiquité au Moyen Age
II. Le chiffrement de Vigenère
II.1. Description
II.2. Cryptanalyse
III. Le one-time pas ou masque jetable
IV. La machine Enigma
V. Et après...
VI. Exercices
Deuxième partie - Les nombres de la cryptologie
Chapitre 2 - Divisibilité et congruence
I. Divisibilité
I.1. Définitions et critères de divisibilité
I.2. Division euclidienne
II. Congruence
II.1. Relation d’équivalence
II.2. Relation de congruence
II.3. Preuve de critères de divisibilité
II.4. Opérations et congruences
II.5. Classes d’équivalence
III. Réponses aux questions
IV. Exercices
Chapitre 3 - Groupes - Anneaux - Corps
I. Groupes
I.1. Définitions, premières propriétés
I.2. Morphismes de groupes
I.3. Sous-groupes
I.4. Sous-groupes de (Z, +)
II. Anneaux et Idéaux
II.1. Généralités
II.2 Règles de calcul
II.3. Eléments inversibles - Corps
II.4. Morphismes d'anneaux
II.5. Sous anneaux et idéaux
II.6. Intersections et sommes d’idéaux
II.7 Anneaux principaux
II.8 Anneaux quotients
III. Réponses aux questions
IV. Exercices
Chapitre 4 - Arithmétique dans un anneau principal
I. Plus grand diviseur commun
I.1. Définitions - Exemples
1.2. Relation de Bézout
II. Eléments premiers entre eux
III. Plus petit multiple commun
IV. PGCD et PPCM de n éléments
V. Eléments irréductibles - Eléments premiers
V.1. Définitions
V.2. Comment trouver les nombres premiers ?
V.3. Eléments premiers
V.4. Décomposition en facteurs premiers
V.5. Polynomes irréductibles
V.6. Anneaux euclidiens et factoriels
VI. Réponses aux questions
VII. Exercices
Chapitre 5 - Anneau Z/nZ
I. Eléments inversibles et diviseurs de zéros
II. Et si n est un nombre premier ?
III. Equations et systèmes d’équations
III.1. Equations ax=b dans Z/nZ
III.2. Théorème des restes chinois
IV. Décomposition de Z/nZ
V. Réponses aux questions
VI. Exercices
Chapitre 6 - Le groupe (Z/nZ)x
I. Groupes cycliques
I.1. Sous-groupe monogène
I.2. Ordre d’un élément d’un groupe
I.3. Eléments primitifs
II. Structure de (Z/pZ)x
III. Structure de (Z/prZ)x)
IV. Structure de (Z/nZ)x
V. L’indicateur de Carmichael
VI. Réponses aux questions
VII. Exercices
Chapitre 7 - Rédidus quadratiques
I. Définitions - Exemples
II. Résidus quadratiques dans Z/pZ
III. Symbole de Legendre
IV. Calcul des racines carrées dans Z/pZ
IV.1. Cas où p est congru à 3 modulo 4
IV.2. Cas où p est congru à 1 modulo 4
V. Carrés modulo un entier quelconque
VI. Nombre de racinées carrées modulo n
VII. Entiers de Blum
VIII. Résidualité quadratique
IX. Réponses aux questions
X. Exercices
Troisième partie - Cryptologie contemporaine
Chapitre 8 - Schémas de Feistel - Standards de chiffrement par blocs
I. Schémas de Feistel
I.1. La construction
I.2. Le résultat essentiel
I.3. Avec une ou deux rondes seulement
II. Data Encryption Standard (DES)
II.1. Construction
II.2. La polémique
III. Advanced Encryption Standard (AES)
III.1. AddRoundKey
III.2.SubBytes
III.2.1. Corps finis
III.2.2. Description de la transformation
III.3. ShiftRows
III.4. Mix Columns
III.5. Fonctionnement
IV. Modes opératoires du chiffrement par bloc
IV.1. Le mode ECB (Electronic Codebook Mode)
IV.2. Le mode CBC (Cipher Block Chaining Mode)
IV.3. Le mode OFB (Output Feedback Mode)
IV.4. Le mode CFM (Cypher Feedback Mode)
V. Réponses aux questions
Chapitre 9 - Cryptographie à clé publique
I. Définitions et principes généraux
I.1. Quelques notions de complexité
I.2. Fonctions à sens unique
I.3. Application
II. RSA
II.1. Cryptage
II.2. Décryptage
II.3. Sécurité
III. Chiffrement de Rabin
III.1 Cryptage
III.2. Décryptage
III.3. Sécurité
IV. Ordinateurs quantiques
IV.1.Qubits
IV.2. Cryptographie post-quantique
V. Le cryptosystème ElGamal
V.1. Cryptage
V.2. Décryptage
V.3. Sécurité
VI. ElGamal généralisé
VII. Protocole d’échange de Clé de Diffie-Hellman
VII.1. Description
VII.2. Attaque
VIII. Cryptographie multivariable
IX. Tests de primalité
IX.1. Test de pseudo-primalité
IX.2. Test de Rabin-Miller
X. Exercices
Chapitre 10 - Signature - Identification - Blockchain
I. Procédés de signature
II. La signature RSA
III. Généralisation
IV. La signature ElGamal
IV.1. Description
IV.2. Sécurité
V. DSS
VI. Courbes elliptiques
VI.1. Coefficients réels
VI.2. Coefficients dans un corps fini
VII. ECDSA
VIII. Fonctions de hachage
VIII.1. Principes généraux
VIII.1.1. Vérifier l’intégrité d’un fichier
VIII.1.2. Stocker des mots de passe
V.III.1.3. Faire fonctionner une blockchain
VIII.1.4. Réduire la taille des signatures
VIII.2. Le paradixe des anniversaires
VIII.3. Une fonction résistante aux collisions
VIII.4. Petit historique
IX. Procédés d’identification « à clé privée »
X. Procédés d’identification « à clé publique"
XI. Procédé d’identification de Guillou-Quisquater
XII. Applications : sécurité des cartes bancaires
XII.1. Structure d’une carte bancaire
XII.2. Le role de la puce
XII.3. Paiement en ligne
XIII. Blockchain
XIII.1. Structure d’un bloc
XIII.2. Sécurité décentralisée
XIII.3. Perspectives
XIV. Réponses aux questions
XV. Exercices
Quatrième partie - Solution des exercices
Chapitre 1
Chapitre 2
Chapitre 3
Chapitre 4
Chapitre 5
Chapitre 6
Chapitre 7
Chapitre 9
Chapitre 10
Bibliographie
Index