Cryptographie: principes et mises en oeuvre (Collection informatique)

-

Livres
416 pages
Lire un extrait
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Quels sont les problèmes de la cryptographie moderne ? Quels sont ses objets, son langage ? Quelles sont les solutions actuelles aux problèmes de confidentialité et d'authentification ? Quel degré de confiance peut-on accorder à ces solutions ? L'ouvrage, sous forme d'un cours de cryptographie générale, expose l'état actuel des réponses à ces questions. Il comprend une présentation et une analyse des méthodes ainsi qu'une description précise des techniques mathématiques indispensables et des principales primitives cryptographiques. Les fonctionnalités de base, le chiffrement, la signature et l'authentification, sont étudiées dans le cadre de la cryptographie à clé publique et de la cryptographie à clé secrète. Ce livre analyse également l'interaction entre ces notions ainsi que leurs mises en œuvre dans des protocoles généraux et dans des applications concrètes. Il s'intéresse aux attaques contre les systèmes cryptographiques et aborde le domaine en plein essor des preuves de sécurité.
Introduction. Un tour d'horizon. Cryptographie à clé publique. Cryptographie à clé secrète. Mise en œuvre des outils cryptographiques. Cryptographie et codes correcteurs d'erreurs. La sécurité des systèmes cryptographiques. Annexes. Index.

Sujets

Informations

Publié par
Date de parution 22 juillet 2005
Nombre de visites sur la page 354
EAN13 9782746237698
Langue Français

Informations légales : prix de location à la page 0,069 €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème

Cryptographie© LAVOISIER, 2005
LAVOISIER
11, rue Lavoisier
75008 Paris
www.hermes-science.com
ISBN 2-7462-1150-5
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.
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.Cryptographie
principes et mises en oeuvre
Pierre Barthélemy
Robert Rolland
Pascal VéronCOLLECTION DIRIGÉE PAR
JEAN-CHARLES POMEROLTable des matières
Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Préface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapitre 1. Introduction - Un tour d'horizon . . . . . . . . . . . . . . . . . . 19
1.1. Ce qu’est la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.1.1. Transmission de l’information . . . . . . . . . . . . . . . . . . . . 20
1.1.1.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.1.1.2. Outils mathématiques . . . . . . . . . . . . . . . . . . . . . . 20
1.1.2. Sécurité de l’information . . . . . . . . . . . . . . . . . . . . . . . 21
1.1.2.1. Buts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1.2.2. Problèmes de base . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2. Techniques cryptographiques . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.1. Chiffrement à clé secrète . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.1.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2.1.2. Chiffrement à flot . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.1.3. Chif par bloc . . . . . . . . . . . . . . . . . . . . . . 25
1.2.2. Chiffrement à clé publique . . . . . . . . . . . . . . . . . . . . . . 27
1.2.2.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.2.2. Systèmes de chiffrement à clé publique . . . . . . . . . . . . 28
1.2.3. Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.3.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.3.2. Systèmes de signature numérique . . . . . . . . . . . . . . . 29
1.2.3.3. Fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . 30
1.2.4. Authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.2.4.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.2.4.2. Systèmes d’authentification . . . . . . . . . . . . . . . . . . . 31
1.3. Techniques mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . 316 Cryptographie
1.3.1. Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.1.1. Fonctions à sens unique . . . . . . . . . . . . . . . . . . . . . 31
1.3.1.2. F à sens avec trappe . . . . . . . . . . . . . . 32
1.3.1.3. Fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . 32
1.3.2. Arithmétique et algèbre . . . . . . . . . . . . . . . . . . . . . . . . 32
1.3.2.1. Problème de la factorisation . . . . . . . . . . . . . . . . . . 32
1.3.2.2. Racines carrées . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.3.2.3. Problème du logarithme discret . . . . . . . . . . . . . . . . 33
1.3.3. Générateurs pseudo-aléatoires . . . . . . . . . . . . . . . . . . . . 34
1.3.3.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.3.3.2. Générateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.3.4. Théorie de la complexité des algorithmes . . . . . . . . . . . . . . 35
1.3.4.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.4.2. Classes de complexité . . . . . . . . . . . . . . . . . . . . . . 35
1.4. Protocoles, systèmesxes . . . . . . . . . . . . . . . . . . . . . . 35
1.5. Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.5.1.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.5.1.2. À propos de la sécurité . . . . . . . . . . . . . . . . . . . . . 37
1.5.1.3. Classification des attaques . . . . . . . . . . . . . . . . . . . 37
1.5.2. Quelques attaques concrètes . . . . . . . . . . . . . . . . . . . . . 38
1.5.2.1. Cryptographie à clé publique . . . . . . . . . . . . . . . . . . 38
1.5.2.2. à clé secrète . . . . . . . . . . . . . . . . . . . 38
1.6. La normalisation et la standardisation . . . . . . . . . . . . . . . . . . . 38
1.7. Évolution de la taille des clés pour les systèmes cryptographiques . . . 39
Chapitre 2. Cryptographie à clé publique . . . . . . . . . . . . . . . . . . . . 41
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2. Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.1. Le chiffrement RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.1.1. La fonction RSA . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.1.2. Schéma de chiffrement et de déchiffrement RSA . . . . . . 51
2.2.1.3. Attaques de RSA . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2.2. Le chiffrement d’ElGamal . . . . . . . . . . . . . . . . . . . . . . 58
2.2.2.1. La fonction exponentielle et la fonction logarithme . . . . . 58
2.2.2.2. Le problème de Diffie-Hellman . . . . . . . . . . . . . . . . 58
2.2.2.3. La fonction d’ElGamal . . . . . . . . . . . . . . . . . . . . . 59
2.2.2.4. Le chiffrement . . . . . . . . . . . . . . . . . . . 60
2.2.2.5. Amélioration théorique : le chiffrement de Cramer-Shoup . 63
2.2.3. Le chiffrement de Rabin . . . . . . . . . . . . . . . . . . . . . . . 63
2.2.3.1. La fonction carrée . . . . . . . . . . . . . . . . . . . . . . . . 63
2.2.3.2. Application de la fonction carrée au chiffrement de Rabin . 65
2.3. Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Table des matières 7
2.3.1. La signature d’ElGamal . . . . . . . . . . . . . . . . . . . . . . . . 67
2.3.2. Le standard DSS de signature . . . . . . . . . . . . . . . . . . . . 69
2.3.2.1. La signature DSA . . . . . . . . . . . . . . . . . . . . . . . . 69
2.3.2.2. La RSA . . . . . . . . . . . . . . . . . . . . . . . . 72
2.3.2.3. La signature ECDSA . . . . . . . . . . . . . . . . . . . . . . 74
2.4. Gestion des clés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.5. Échange de clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.6. Authentification : preuve à divulgation nulle . . . . . . . . . . . . . . . 83
2.6.1. Preuves interactives à di nulle . . . . . . . . . . . . . . . 83
2.6.2. Principes généraux d’une preuve interactive à divulgation nulle . 84
2.6.3. Schéma d’identification de Feige-Fiat-Shamir . . . . . . . . . . . 84
2.6.4. Identification de Schnorr . . . . . . . . . . . . . . . . . . . . . . . 85
2.7. Cryptographie à faible coût . . . . . . . . . . . . . . . . . . . . . . . . . 86
2.7.1. Le système GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.7.2. Le GQ2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Chapitre 3. Cryptogaphie à clé secrète . . . . . . . . . . . . . . . . . . . . . . 91
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.2. Généralités sur le chiffrement par bloc . . . . . . . . . . . . . . . . . . 92
3.2.1. Les principes généraux . . . . . . . . . . . . . . . . . . . . . . . . 92
3.2.1.1. Remarque préalable . . . . . . . . . . . . . . . . . . . . . . . 92
3.2.1.2. Description d’un chiffrement par bloc . . . . . . . . . . . . . 92
3.2.1.3. La diffusion et la confusion . . . . . . . . . . . . . . . . . . . 93
3.2.1.4. Itération d’une fonction de tour . . . . . . . . . . . . . . . . 93
3.2.1.5. Le schéma de production des sous-clés . . . . . . . . . . . . 94
3.2.1.6. Le modèle de Feistel . . . . . . . . . . . . . . . . . . . . . . 94
3.2.2. Les modes principaux d’utilisation . . . . . . . . . . . . . . . . . . 95
3.3. Le système DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.3.1. La permutationIP . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3.2. La fonctionf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3.2.1. L’expansionE . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.3.2.2. Le ou exclusif (XOR) . . . . . . . . . . . . . . . . . . . . . . 104
3.3.2.3. Les S-boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.3.2.4. La permutationP . . . . . . . . . . . . . . . . . . . . . . . . 106
3.3.2.5. Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.3.3. La génération des clés de tour . . . . . . . . . . . . . . . . . . . . 106
3.3.3.1. La sélectionPC-1 . . . . . . . . . . . . . . . . . . . . . . . . 107
3.3.3.2. Les rotations à gauche . . . . . . . . . . . . . . . . . . . . . . 107
3.3.3.3. La sélectionPC-2 . . . . . . . . . . . . . . . . . . . . . . . . 108
3.3.4. Le déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.3.5. Utilisation du DES . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.4. Le système AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.4.1. La structure générale . . . . . . . . . . . . . . . . . . . . . . . . . 1108 Cryptographie
3.4.1.1. Le nombre de tours . . . . . . . . . . . . . . . . . . . . . . . 111
3.4.1.2. La clé de tour . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.4.1.3. Vue globale du fonctionnement . . . . . . . . . . . . . . . . 111
3.4.2. La procédure SubBytes . . . . . . . . . . . . . . . . . . . . . . . . 113
3.4.2.1. Le corps fini à 256 éléments . . . . . . . . . . . . . . . . . . 113
3.4.2.2. La fonction affinef . . . . . . . . . . . . . . . . . . . . . . . 114
3.4.2.3. La procédure SubBytes . . . . . . . . . . . . . . . . . . . . . 114
3.4.3. La procédure ShiftRows . . . . . . . . . . . . . . . . . . . . . . . . 114
3.4.4. La MixColumns . . . . . . . . . . . . . . . . . . . . . . 115
3.4.5. La procédure AddRoundKey . . . . . . . . . . . . . . . . . . . . . 117
3.4.6. La KeyExpansion . . . . . . . . . . . . . . . . . . . . . 117
3.5. La cryptanalyse de ces systèmes . . . . . . . . . . . . . . . . . . . . . . 119
3.5.1. L’attaque brutale ou recherche exhaustive . . . . . . . . . . . . . . 119
3.5.2. Notion de détecteur et application au dernier tour . . . . . . . . . 120
3.5.3. Cryptanalyse différentielle . . . . . . . . . . . . . . . . . . . . . . 121
3.5.3.1. Différentielle surn 1 tours. . . . . . . . . . . . . . . . . . 121r
3.5.3.2. Le dernier tour . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5.3.3. Description globale de l’attaque . . . . . . . . . . . . . . . . 124
3.5.4. Cryptanalyse linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.5.4.1. Principe de l’attaque . . . . . . . . . . . . . . . . . . . . . . . 125
3.5.4.2. Comment obtenir les conditions requises . . . . . . . . . . . 126
3.5.5. Cryptanalyse interpolatoire . . . . . . . . . . . . . . . . . . . . . . 126
3.6. Le chiffrement en continu ou par flot . . . . . . . . . . . . . . . . . . . 128
3.6.1. Les principes généraux . . . . . . . . . . . . . . . . . . . . . . . . 128
3.6.2. Réutilisation de circuits existants . . . . . . . . . . . . . . . . . . . 130
3.6.2.1. Utilisation de circuits de chiffrement par bloc . . . . . . . . 130
3.6.2.2. L’utilisation de fonctions de hachage . . . . . . . . . . . . . 130
3.6.3. Les constructions spécifiques . . . . . . . . . . . . . . . . . . . . . 130
3.6.3.1. Le générateur pseudo-aléatoire Blum-Blum-Shub . . . . . . 130
3.6.3.2. Les registres à décalage . . . . . . . . . . . . . . . . . . . . . 131
3.7. Les fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.7.1. Fonctions de MDC . . . . . . . . . . . . . . . . . . . . . 135
3.7.1.1. Fonctions de hachage à sens unique . . . . . . . . . . . . . . 135
3.7.1.2. F de résistantes aux collisions . . . . . . . 135
3.7.2. La construction de Merkle-Damgård . . . . . . . . . . . . . . . . 136
3.7.3. Fonctions de hachage à deux entrées . . . . . . . . . . . . . . . . . 137
3.7.3.1. Familles universelles de fonctions de hachage à sens unique 137
3.7.3.2. Code d’authentification de message (MAC) . . . . . . . . . 137
3.7.4. Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.7.4.1. SHA-256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.7.4.2. La famille NH . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.7.5. Les codes d’authentification de message (MAC) . . . . . . . . . . 142
3.7.5.1. CBC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142Table des matières 9
3.7.5.2. HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
3.7.5.3. UMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Chapitre 4. Mise en œuvre des outils cryptographiques. . . . . . . . . . . . . 145
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.2. Notions de base sur les réseaux informatiques . . . . . . . . . . . . . . 146
4.2.1. L’internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.2.2. Le modèle OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.3. Notion de protocole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.3.1. Protocoles cryptographiques . . . . . . . . . . . . . . . . . . . . . 147
4.3.2. d’échange d’information . . . . . . . . . . . . . . . . . 148
4.3.3. Protocoles sécurisés . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4. Cryptographie et sécurité informatique . . . . . . . . . . . . . . . . . . 149
4.4.1. L’insécurité informatique . . . . . . . . . . . . . . . . . . . . . . . 149
4.4.2. Les attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.4.2.1. Typologie des attaques . . . . . . . . . . . . . . . . . . . . . 150
4.4.2.2. Exemples d’attaques . . . . . . . . . . . . . . . . . . . . . . . 151
4.4.3. Cryptographie embarquée . . . . . . . . . . . . . . . . . . . . . . . 152
4.4.3.1. Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.4.3.2. Cryptographie et téléphonie mobile . . . . . . . . . . . . . . 153
4.4.3.3. et puces RFID . . . . . . . . . . . . . . . . . 155
4.5. Certificats électroniques et infrastructures de gestion de clés . . . . . . 158
4.5.1. Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.5.2. Notion de certificat . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.5.3. Autorité de certification et opérateur de certification . . . . . . . . 159
4.5.4. Politique de et déclaration des pratiques de certification 160
4.5.4.1. Politique de certification . . . . . . . . . . . . . . . . . . . . 160
4.5.4.2. Déclaration des pratiques de certification . . . . . . . . . . . 161
4.5.5. Structure d’un certificat . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5.6. Infrastructure de gestion de clés . . . . . . . . . . . . . . . . . . . 162
4.5.6.1. Rôle et définition . . . . . . . . . . . . . . . . . . . . . . . . 162
4.5.6.2. Enregistrement et génération . . . . . . . . . . . . . . . . . . 163
4.5.6.3. Publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.5.6.4. Révocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.5.6.5. Recouvrement des clés . . . . . . . . . . . . . . . . . . . . . 165
4.5.7. Confiance et niveaux de sécurité . . . . . . . . . . . . . . . . . . . 165
4.5.8. Les tiers de confiance . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.5.8.1. Les tiers certificateurs . . . . . . . . . . . . . . . . . . . . . . 167
4.5.8.2. Les tiers archiveurs . . . . . . . . . . . . . . . . . . . . . . . 167
4.5.8.3. Les tiers horodateurs . . . . . . . . . . . . . . . . . . . . . . 168
4.5.9. La manipulation des certificats . . . . . . . . . . . . . . . . . . . . 170
4.6. Protocoles sécurisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.6.1. La messagerie électronique . . . . . . . . . . . . . . . . . . . . . . 17010 Cryptographie
4.6.1.1. Brefs rappels techniques . . . . . . . . . . . . . . . . . . . . 170
4.6.1.2. L’emploi de PGP . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.6.1.3. L de S/MIME . . . . . . . . . . . . . . . . . . . . . . 171
4.6.2. Le protocole SSH . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.6.2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.6.2.2. La couche transport . . . . . . . . . . . . . . . . . . . . . . . 173
4.6.2.3. La authentification . . . . . . . . . . . . . . . . . . . 180
4.6.2.4. Les attaques possibles . . . . . . . . . . . . . . . . . . . . . . 182
4.6.3. Le protocole SSL . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
4.6.4. Kerberos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.6.5. Protocole « station to station » . . . . . . . . . . . . . . . . . . . . 191
4.7. Du bon usage de la cryptographie . . . . . . . . . . . . . . . . . . . . . 191
4.7.1. La YesCard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.7.1.1. Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.7.1.2. Contenu d’une carte bancaire . . . . . . . . . . . . . . . . . . 192
4.7.1.3. Le déroulement d’une transaction . . . . . . . . . . . . . . . 193
4.7.1.4. L’affaire Humpich . . . . . . . . . . . . . . . . . . . . . . . . 194
4.7.1.5. La carte bancaire de nos jours . . . . . . . . . . . . . . . . . 195
4.7.2. Sécurité des réseaux sans-fil . . . . . . . . . . . . . . . . . . . . . 196
4.7.2.1. WEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.7.2.2. Mécanisme de chiffrement et de déchiffrement . . . . . . . . 197
4.7.2.3. La confidentialité des données . . . . . . . . . . . . . . . . . 198
4.7.2.4. Le contrôle d’accès . . . . . . . . . . . . . . . . . . . . . . . 201
4.7.2.5. Intégrité des données . . . . . . . . . . . . . . . . . . . . . . 202
4.7.2.6. Authentification des postes clients . . . . . . . . . . . . . . . 202
4.7.2.7. Clés faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.7.2.8. L’attaque de l’oracle TCP . . . . . . . . . . . . . . . . . . . . 203
4.7.2.9. Remarques importantes et inquiétantes . . . . . . . . . . . . 204
4.7.2.10.WPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
4.7.2.11.WPA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Chapitre 5. Cryptographie et codes correcteurs d'erreurs . . . . . . . . . . . 207
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.2. Le problème SD et ses variantes . . . . . . . . . . . . . . . . . . . . . . 208
5.2.1. Les codes correcteurs d’erreurs . . . . . . . . . . . . . . . . . . . . 210
5.2.2. Le problème du décodage . . . . . . . . . . . . . . . . . . . . . . . 213
5.2.3. Variantes du problème SD . . . . . . . . . . . . . . . . . . . . . . 215
5.3. Algorithmes pour la résolution du problème SD . . . . . . . . . . . . . 216
5.3.1. L’algorithme de Lee et Brickell . . . . . . . . . . . . . . . . . . . 217
5.3.2. L de Leon . . . . . . . . . . . . . . . . . . . . . . . . . 219
5.3.3. L’algorithme de J. Stern . . . . . . . . . . . . . . . . . . . . . . . 221
5.3.4. L de Canteaut-Chabaud . . . . . . . . . . . . . . . . . 221
5.3.5. Efficacité de ces algorithmes . . . . . . . . . . . . . . . . . . . . . 221Table des matières 11
5.3.6. L’algorithme de Johansson et Jönsson . . . . . . . . . . . . . . . 222
5.4. Le schéma d’identification G-SD . . . . . . . . . . . . . . . . . . . . . 224
5.4.1. Les codes correcteurs et la problématique de l’identification . . . 224
5.4.2. Notion de mises en gage . . . . . . . . . . . . . . . . . . . . . . . 225
5.4.3. Description du schéma . . . . . . . . . . . . . . . . . . . . . . . . 226
5.4.4. Sécurité et performances du schéma . . . . . . . . . . . . . . . . 227
5.5. Un générateur pseudo-aléatoire . . . . . . . . . . . . . . . . . . . . . . 229
5.5.1. Introduction et définitions . . . . . . . . . . . . . . . . . . . . . . . 229
5.5.2. Une famille de fonctions à sens unique dépendantes
du problème SD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
5.5.3. Description du générateur . . . . . . . . . . . . . . . . . . . . . . . 231
5.5.4. Sécurité et performances du générateur . . . . . . . . . . . . . . . 231
5.6. Le système de chiffrement de Mc Eliece . . . . . . . . . . . . . . . . . 233
5.6.1. Le cryptosystème et ses contraintes . . . . . . . . . . . . . . . . . 233
5.6.2. Les codes de Goppa classiques et leur décodage . . . . . . . . . . 234
5.6.2.1. Définitions, propriétés . . . . . . . . . . . . . . . . . . . . . . 234
5.6.2.2. Le décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
5.6.3. Sécurité du système . . . . . . . . . . . . . . . . . . . . . . . . . . 237
5.6.3.1. L’attaque générique . . . . . . . . . . . . . . . . . . . . . . . 237
5.6.3.2. L structurelle . . . . . . . . . . . . . . . . . . . . . . 238
5.6.3.3. Une autre attaque . . . . . . . . . . . . . . . . . . . . . . . . 239
5.6.4. La sécurité prouvée . . . . . . . . . . . . . . . . . . . . . . . . . . 241
5.6.5. Performances du système . . . . . . . . . . . . . . . . . . . . . . . 241
5.6.6. Le cryptosystème en pratique . . . . . . . . . . . . . . . . . . . . . 244
5.6.7. Variantes de Mc Eliece . . . . . . . . . . . . . . . . . . . . . . . . 246
5.6.7.1. Le cryptosystème de Niederreiter . . . . . . . . . . . . . . . 246
5.6.7.2. Utilisation de codes de Goppa particuliers . . . . . . . . . . 249
5.6.7.3. Le GPT . . . . . . . . . . . . . . . . . . . . . 252
5.7. Un schéma de signature . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
5.7.1. Le schémaCFS . . . . . . . . . . . . . . . . . . . . . . . . . . . 2561
5.7.2. Performances et sécurité . . . . . . . . . . . . . . . . . . . . . . . 257
5.8. Une fonction de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . 262
5.8.1. Les mots réguliers . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.8.2. Sécurité et performances . . . . . . . . . . . . . . . . . . . . . . . 263
5.9. Le partage de secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Chapitre 6. La sécurité des systèmes cryptographiques . . . . . . . . . . . . 269
6.1. Introduction, notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
6.2. Sécurité au sens de Shannon . . . . . . . . . . . . . . . . . . . . . . . . 269
6.2.1. Systèmes cryptographiquement sûrs . . . . . . . . . . . . . . . . . 270
6.2.2. Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
6.2.3. Le paradoxe de la cryptographie à clé publique . . . . . . . . . . . 272
6.3. Autres notions de sécurité pour les systèmes à clé publique . . . . . . . 27312 Cryptographie
6.3.1. Généralités sur la sécurité prouvée . . . . . . . . . . . . . . . . . . 273
6.3.1.1. Calcul en temps raisonnable . . . . . . . . . . . . . . . . . . 274
6.3.1.2. Le modèle de l’oracle aléatoire . . . . . . . . . . . . . . . . . 275
6.3.1.3. Les diverses exigences . . . . . . . . . . . . . . . . . . . . . 276
6.3.1.4. Chiffrement probabiliste . . . . . . . . . . . . . . . . . . . . 276
6.3.1.5. Les modèles d’adversaires . . . . . . . . . . . . . . . . . . . 277
6.3.1.6. Les notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
6.3.2. Formalisation des notions de sécurité . . . . . . . . . . . . . . . . 278
6.3.2.1. Notion de paramètre de . . . . . . . . . . . . . . . . 278
6.3.2.2. Mise en place du cryptosystème . . . . . . . . . . . . . . . . 279
6.3.2.3. L’attaquant (polynomial) . . . . . . . . . . . . . . . . . . . . 280
6.3.2.4. Indistinguabilité . . . . . . . . . . . . . . . . . . . . . . . . . 281
6.3.2.5. Non-malléabilité . . . . . . . . . . . . . . . . . . . . . . . . . 283
6.3.3. Les relations entre les diverses notions . . . . . . . . . . . . . . . 284
6.3.3.1. L’indistinguabilité, la sécurité sémantique, et l’indivisibilité 284
6.3.3.2. La non-malléabilité basée sur la simulation et la non-malléabilité
basée sur la comparaison (SNM et CNM) . . . . . . . . . . . 286
6.3.3.3. Énoncés des résultats . . . . . . . . . . . . . . . . . . . . . . 288
6.3.4. Preuve du théorème 6.8 . . . . . . . . . . . . . . . . . . . . . . . . 290
6.3.5. Preuve du 6.17 . . . . . . . . . . . . . . . . . . . . . . . 290
6.3.5.1. ND-ATK) SS-ATK . . . . . . . . . . . . . . . . . . . . . . 290
6.3.5.2. SS-ATK) IND-ATK . . . . . . . . . . . . . . . . . . . . . . 291
6.3.5.3. IND-ATK) ND-ATK . . . . . . . . . . . . . . . . . . . . . 291
6.3.6. Preuve du théorème 6.18 . . . . . . . . . . . . . . . . . . . . . . . 293
6.3.6.1. CNM-ATK) SNM-ATK . . . . . . . . . . . . . . . . . . . 293
6.3.6.2. SNM-ATK) IND-PXX . . . . . . . . . . . . . . . . . . . . 295
6.3.6.3. IND-PXX) CNM-ATK . . . . . . . . . . . . . . . . . . . . 297
6.3.7. Preuve du théorème 6.19 . . . . . . . . . . . . . . . . . . . . . . . 298
6.3.7.1. NM-CCA2) NM-CCA1 . . . . . . . . . . . . . . . . . . . 298
6.3.7.2. NM-CCA1 ; NM-CCA2 . . . . . . . . . . . . . . . . . . . 298
6.3.7.3.) NM-CPA . . . . . . . . . . . . . . . . . . . . 302
6.3.7.4. IND-CCA2) IND-CCA1 . . . . . . . . . . . . . . . . . . . 302
6.3.7.5. IND-CCA1) IND-CPA . . . . . . . . . . . . . . . . . . . . 302
6.3.7.6. NM-CCA2, IND-CCA2 . . . . . . . . . . . . . . . . . . . 302
6.3.7.7. NM-ATK) IND-ATK . . . . . . . . . . . . . . . . . . . . . 302
6.3.7.8. NM-CPA ; IND-CCA1 . . . . . . . . . . . . . . . . . . . . 303
6.3.7.9. IND-CCA1 ; NM-CPA . . . . . . . . . . . . . . . . . . . . 303
6.4. Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
6.4.1. Le problème décisionnel de Diffie-Hellman (DDH) . . . . . . . . 304
6.4.2. Autour du chiffrement d’ElGamal . . . . . . . . . . . . . . . . . . 311
6.4.2.1. Chiffrement de base . . . . . . . . . . . . . . . . . . . . . . . 311
6.4.2.2. Chif d’ElGamal modifié . . . . . . . . . . . . . . . . 312
6.4.2.3. Méthode de transformation de Fujisaki-Okamoto . . . . . . 313Table des matières 13
6.4.2.4. Le chiffrement de Cramer-Shoup . . . . . . . . . . . . . . . 315
6.4.3. Les systèmes OAEP et OAEP+ . . . . . . . . . . . . . . . . . . . . 321
Annexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
A. Complexité des algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . 323
A.1. Introduction - Notations . . . . . . . . . . . . . . . . . . . . . . . . 323
A.2. Rappels sur les machines de Turing . . . . . . . . . . . . . . . . . . 323
A.2.1. Description intuitive . . . . . . . . . . . . . . . . . . . . . . . 323
A.2.2. Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
A.2.3. Machines de Turing non déterministes . . . . . . . . . . . . . 325
A.2.4. Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
A.3. Temps d’exécution, complexité . . . . . . . . . . . . . . . . . . . . 327
A.3.1. Les échelles de croissance . . . . . . . . . . . . . . . . . . . . 328
A.3.2. Remarque sur les temps d’exécution . . . . . . . . . . . . . . 328
A.3.3. Analyse des algorithmes et notations asymptotiques . . . . . 328
A.3.4. Quelques coûts classiques . . . . . . . . . . . . . . . . . . . . 333
A.3.5. La classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
A.3.6. La classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
A.3.7. Réduction d’un problème à un autre . . . . . . . . . . . . . . 334
A.4. Probabilisation des algorithmes non déterministes. Classes ZPP,
RP, BPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
A.4.1. La classe ZPP . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
A.4.2. La classe RP . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
A.4.3. La classe BPP . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
A.4.4. Relations entre ces classes . . . . . . . . . . . . . . . . . . . . 336
A.4.5. Modèle uniforme, modèle non uniforme . . . . . . . . . . . . 336
A.5. Fonctions à sens unique . . . . . . . . . . . . . . . . . . . . . . . . 337
B. Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
B.1. Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . 340
B.1.1. Algorithme de division euclidienne par soustraction . . . . . 340
B.1.2. Version binaire de l’algorithme de division euclidienne . . . 341
B.1.3. Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . 343
B.1.4. étendu . . . . . . . . . . . . . . . . . . 343
B.1.5. Complexité de l’algorithme d’Euclide et de l’algorithme
d’Euclide étendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
B.2. Les classes résiduelles . . . . . . . . . . . . . . . . . . . . . . . . . 350
B.2.1. Les éléments inversibles de Z=nZ . . . . . . . . . . . . . . . 350
B.2.2. Le petit théorème de Fermat . . . . . . . . . . . . . . . . . . . 352
B.2.3. La fonction indicatrice d’Euler . . . . . . . . . . . . . . . . . 354
B.2.4. Calcul d’une puissance . . . . . . . . . . . . . . . . . . . . . . 356
B.2.5. Générateurs de (Z=pZ) (p premier) - Logarithme discret . . 357
B.2.6. Quelques résultats sur les logarithmes discrets . . . . . . . . . 361
B.3. Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 36114 Cryptographie
B.3.1. Déterminer si un nombre est premier ou non . . . . . . . . . . 361
B.3.2. La factorisation des entiers . . . . . . . . . . . . . . . . . . . . 365
B.4. Algorithmes de construction de nombres premiers . . . . . . . . . 365
B.4.1. Construire un grand nombre premier au hasard . . . . . . . . 365
B.4.2. un couple (p;q) de nombres premiers tels queq
divisep 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
B.4.3. Construire un couple (p;q) de nombres premiers tels que
p = 2q + 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
B.5. Résidus quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . 367
B.5.1. Cas d’un module premier impair de la forme 4k 1 : cas
simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
B.5.2. Cas d’un module premier impair de la forme 4k + 1 :
algorithme de Shanks . . . . . . . . . . . . . . . . . . . . . . . . . 367
B.5.3. Cas d’un module produit de deux grands nombres premiers
distincts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
B.5.4. Symbole de Legendre et symbole de Jacobi . . . . . . . . . . 370
C. Développement en fraction continue . . . . . . . . . . . . . . . . . . . . . 375
C.1. Remarques préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 375
C.2. Le cas des nombres rationnels . . . . . . . . . . . . . . . . . . . . . 375
C.3. Cas des irrationnels . . . . . . . . . . . . . . . . . . . . . 376
C.3.1. Généralisation des fractions continues simples . . . . . . . . 377
C.3.2. Application aux réduites d’un nombre irrationnel . . . . . . . 380
C.4. Cas des nombres irrationnels quadratiques . . . . . . . . . . . . . . 381
C.5. Comparaison des réduites à d’autres approximations rationnelles . 385
D. Paradoxe des anniversaires . . . . . . . . . . . . . . . . . . . . . . . . . . 389
D.1. Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . 389
D.2. Formalisation et résultats . . . . . . . . . . . . . . . . . . . . . . . . 389
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405Avant-propos
Cet ouvrage est basé sur divers cours de cryptographie que nous avons donnés ces
dernières années à l’Université de la Méditerranée et à l’Université du
Sud-ToulonVar, dans des cursus d’informatique et de mathématiques. Il s’appuie aussi sur nos
propres activités de recherche au sein du groupe « Arithmétique et Théorie de
l’Information » de l’IML - Institut de Mathématiques de Luminy (CNRS et Université de
la Méditerranée) et du GRIM - « Groupe de Recherche en Informatique et
Mathématiques de Toulon » (Université du Sud-Toulon-Var). Il s’agit d’un ouvrage de
cryptologie générale qui, nous l’espérons, pourra être utile au lecteur désireux d’avoir une
vue d’ensemble de la cryptologie contemporaine, tant du point de vue des principes
de base que du point de vue des mises en œuvre des outils fondamentaux de la
cryptographie. Le niveau correspond à peu près à la licence et au master, ou aux formations
d’ingénieurs. Pour une grande partie de l’ouvrage, les prérequis sont relativement
minimes dans la mesure où nous partons des notions de base de la cryptographie. Les
outils mathématiques et informatiques principaux sont repris dans des annexes et
développés de manière détaillée. Si la cryptologie est maintenant intégrée dans un bon
nombre de formations scientifiques, il faut bien constater qu’elle est rarement
considérée comme la partie centrale de ces formations. L’étudiant désireux de s’orienter
professionnellement vers cette voie doit alors combler le fossé qui sépare l’enseignement
général suivi et les exigences de la recherche et du développement dans le domaine.
Nous espérons que cet ouvrage pourra aider à cette transition et permettra d’aborder
des questions plus spécialisées avec le recul nécessaire.
La cryptologie est devenue un domaine autonome, à la frontière des
mathématiques, de l’informatique et de l’électronique, qui a ses problématiques propres et ses
méthodes. C’est une discipline qui, portée par le développement technologique, est en
pleine expansion. Nous avons essayé de couvrir une large partie de ses bases tout en
sachant qu’il était quasi impossible de rendre compte de toutes les directions nouvelles.
Certaines théories, comme la sécurité prouvable par exemple, ne sont pas encore
complètement stabilisées, ce qui rend difficile leur exposé. Ainsi plutôt que de chercher à16 Cryptographie
faire un inventaire plus ou moins exhaustif et forcément éphémère des systèmes
existants, nous avons préféré illustrer par des exemples significatifs les méthodes qui nous
semblent les plus importantes. De ce fait, pour chaque chapitre, nous avons dû faire
des choix, tant sur les exemples traités que sur le niveau d’approfondissement. En ce
qui concerne la sécurité prouvable par exemple, nous avons décidé de développer et
d’approfondir le cas des systèmes de chiffrement à clé publique.
Jacques Stern, Professeur à l’École Normale Supérieure, Directeur du
Département d’Informatique et du Laboratoire d’Informatique de l’ENS, nous a soutenus dans
notre projet. Nous le remercions d’avoir accepté de préfacer ce livre.
Nous sommes reconnaissants à David Pointcheval, Phong Nguyen et Matthieu
Finiasz pour les documents qu’ils nous ont communiqués et les remarques scientifiques
qu’ils nous ont faites.
Nous remercions aussi Yves Aubry, Alain Barichard, Valérie Gillot, Philippe
Langevin, Pierre-Yvan Liardet, Patrice Rabizzoni, Patrick Soubeyrand, Christian
Tavernier, Yannick Teglia, Jacques Wolfmann, qui ont relu et commenté des parties du
manuscrit.
Les auteursPréface
En une trentaine d’années, la cryptographie est passée d’une activité régalienne
limitée aux univers de la défense et de la diplomatie, à une discipline scientifique à
part entière structurée autour de concepts précis et de méthodes rigoureuses et servie
par une nombreuse communauté de recherche.
Depuis l’invention de la cryptographie à clé publique par Diffie et Hellman en
1976, des résultats nombreux et significatifs ont été obtenus : algorithme RSA de
Rivest, Shamir et Adleman, preuves à divulgation nulle, systèmes cryptographiques
mettant en œuvre les courbes elliptiques, cryptanalyse différentielle et linéaire,
sécurité prouvée, cryptographie fondée sur l’identité, etc.
Parallèlement, la cryptographie s’est largement déployée : des millions de clés
RSA ont été créées pour sécuriser par le protocole SSL les transactions menées sur
le Web ; des infrastructures de gestion de clés se mettent en place ; on fait appel à
des algorithmes de chiffrement élaborés pour protéger les communications du GSM
ou de l’UMTS ; on imagine des méthodes où les contenus multimédia sont en
permanence chiffrés pour protéger les droits d’auteur. Si bien qu’on peut véritablement
parler d’ubiquité de la cryptologie. Qu’on en juge : chacun d’entre nous a sur lui deux
processeurs cryptographiques, l’un dans son téléphone mobile et l’autre dans sa carte
de crédit.
Cette considérable expansion de la cryptologie, en termes de recherche et de
développement, ne s’est pas accompagnée d’un effort pédagogique suffisant. Peu
d’ouvrages présentent de façon cohérente, synthétique et globale, les éléments essentiels
du savoir cryptographique contemporain. Les uns sont plutôt des cours de
mathématiques, d’autres des ouvrages d’ingénierie, certains sont simplistes, d’autres trop
avancés. De plus, la quasi-totalité sont écrits en langue anglaise par des auteurs
anglosaxons. Ce n’est, certes pas un défaut, mais, même traduits avec soin, ces livres ne
tiennent pas compte de la spécificité de nos étudiants.18 Cryptographie
Ecrire un ouvrage d’introduction à la cryptographie est donc un défi et la difficulté
principale tient à ce que cette science n’est ni une branche des mathématiques, ni de
l’informatique, ni de l’ingénierie mais emprunte, dans un subtil mélange, aux
méthodologies de ces trois disciplines. Je suis heureux de constater que les trois auteurs,
Pierre Barthélemy, Robert Rolland et Pascal Véron, ont relevé le défi avec succès.
Sans doute parce que leurs compétences englobent précisément le spectre des
connaissances que je viens d’évoquer. De fait, on trouve dans l’ouvrage, à la fois les bases
mathématiques nécessaires, les développements maintenant classiques de la
cryptographie conventionnelle et à clé publique, les applications aux protocoles SSH, SSL
ou à la sécurité des cartes bancaires et une sélection de résultats récents, notamment
sur la prouvée. L’écriture est précise et réussit à ne pas sacrifier la clarté à la
correction des énoncés, des explications et des preuves. À l’évidence, les auteurs sont
parvenus à écrire un livre qui sera largement utilisé par les étudiants des universités et
des grandes écoles. Je forme le vœu qu’il contribue ainsi à attirer plus d’étudiants vers
la cryptographie.
Dans la civilisation de l’information, les enjeux de sécurité sont essentiels et le
recours à la cryptographie s’impose dès qu’une opération symbolique peut être
détournée de son objet. Le nombre des étudiants, ingénieurs et chercheurs formés à la
cryptographie, doit être à la mesure des enjeux.
Jacques STERN
Professeur à l’École normale supérieure
Directeur du département d’informatiqueChapitre 1
Introduction - Un tour d’horizon
1.1. Ce qu’est la cryptographie
Il est difficile de réduire tout un large secteur d’activité scientifique à une formule,
et de ce fait une bonne définition de la cryptographie ne pourra s’acquérir qu’au fur
et à mesure de son étude et de sa pratique. Mais puisqu’il faut bien commencer, on
peut dire dans un premier temps : la est l’étude des systèmes
mathématiques propres à résoudre les problèmes de confidentialité et d’authentification.
Bien entendu cette définition est un peu réductrice dans la mesure où actuellement la
cryptographie s’occupe de problèmes allant au-delà de ce qui vient d’être dit. De plus
il faudrait rajouter la notion d’ adversaire sans laquelle la cryptographie n’a guère de
sens. On peut donc aussi dire que la cryptographie s’occupe de communication en
présence d’adversaires. En outre, il faut tenir grand compte de l’environnement matériel
et technologique de la cryptographie, comme les ordinateurs, les réseaux
d’ordinateurs, les moyens modernes de télécommunication, les cartes à puce. Le besoin
croissant de sécurité au sein de cet environnement a motivé un développement rapide de
la cryptographie, développement impliquant outre les mathématiques, l’informatique
ainsi que la physique. À côté du terme ancien de cryptographie, limité à l’origine au
chiffrement des messages, on a introduit récemment, de manière à préciser la
terminologie et rendre compte de l’évolution récente du domaine, la dénomination générale
de cryptologie pour désigner la partie de la sécurité des systèmes d’information qui
s’occupe d’assurer, ou au contraire de compromettre, les grandes fonctions de sécurité
(en particulier la confidentialité et l’intégrité des données, l’authentification, la
nonrépudiation). Ainsi la cryptologie a un double aspect : d’une part la cryptographie
qui consiste à construire des outils propres à assurer des fonctionnalités de sécurité,
d’autre part la cryptanalyse qui consiste à s’attaquer aux outils en question pour en
trouver les faiblesses.20 Cryptographie
Sans doute faut-il, pour comprendre plus profondément le domaine, se replonger
dans l’histoire et dans la réflexion sur l’évolution de la notion de secret. Nous
renvoyons pour cela aux excellents ouvrages de J. Stern [Ste98], et de D. Kahn [Kah80].
Nous traiterons essentiellement de la cryptographie récente, qui correspond à ce que
J. Stern appelle l’âge paradoxal. Nous allons faire un premier tour d’horizon et en
particulier replacer la cryptologie dans le contexte de la transmission de l’information.
1.1.1. Transmission de l’information
1.1.1.1. Description
La transmission de l’information soulève au moins les trois grands problèmes
suivants :
– la représentation de l’information, son codage, sa compression ;
– l’intégrité des données, la détection et la correction des erreurs ;
– la sécurité de l’information, sa confidentialité.
Le premier problème consiste à étudier comment utiliser les mots écrits avec les
lettres d’un alphabet pour représenter chaque type d’information (texte, image, etc.).
Comme problème sous-jacent, on veut éventuellement représenter les données en
utilisant une place minimale. C’est le problème de la compression des données.
Le deuxième problème s’attache à l’étude des erreurs qui peuvent survenir en
raison du bruit dans le canal de transmission. Ce problème est traité dans le cadre de la
théorie des codes correcteurs d’erreurs. Il est à remarquer ici, que les erreurs dont on
parle sont des erreurs de transmission et non pas des erreurs volontaires, dues à une
attaque malveillante, qui elles relèvent du problème suivant.
Le troisième problème concerne les questions de sécurité, en particulier la
confidentialité des données transmises, l’authentification des messages et des personnes.
C’est l’objet principal de ce livre.
Remarquons que si nous voulons traiter efficacement les données, nous avons
intérêt à choisir un alphabet permettant des calculs mathématiques, c’est-à-dire un
alphabet ayant une structure mathématique riche. Les corps finis sont pour ce faire de
bons candidats.
1.1.1.2. Outils mathématiques
Ces différentes parties de la théorie de l’information utilisent toute une panoplie
d’outils mathématiques similaires dont voici une liste non exhaustive :
– théorie de la complexité des algorithmes ;
– probabilités, statistiques, entropie, suites pseudo-aléatoires ;Introduction 21
– arithmétique ;
– algèbres de Boole ;
– corps finis, géométrie affine et projective, géométrie combinatoire ;
– algèbre commutative ;
– géométrie algébrique.
Insistons sur le fait qu’en cryptographie, le point de vue algorithmique est
extrêmement important.
1.1.2. Sécurité de l’information
Venons-en à la partie qui nous intéresse ici, c’est-à-dire tout ce qui est lié à la
sécurité de l’information et à sa confidentialité.
1.1.2.1. Buts
Voici quelques buts principaux à atteindre, dont la description nous aidera à cerner
les problèmes principaux de la cryptographie, ainsi que quelques définitions
importantes et la terminologie associée :
– secret, confidentialité, chiffrement. Les données doivent rester inintelligibles à
toute personne non autorisée. Plus précisément : la confidentialité est la propriété
qu’une information n’est ni disponible ni divulguée aux personnes, entités ou
processus non autorisés (selon la norme ISO 7498-2). La confidentialité se définit également
comme le caractère réservé d’une information dont l’accès est limité aux personnes
admises à la connaître pour les besoins du service. En particulier, lors d’une
communication, il s’agit d’empêcher un tiers de prendre connaissance de l’information
contenue dans un message transmis sur un canal non sécurisé, c’est-à-dire sur lequel
l’intrusion non détectée d’un tiers est possible.
– intégrité des données. On doit éviter que les données transmises soient modifiées
ou forgées par un adversaire. Plus précisément : l’intégrité est la prévention d’une
modification non autorisée de l’information. L’intégrité du système et de l’information
garantit que ceux-ci ne sont modifiés que par une action volontaire et légitime. Les
attaques contre l’intégrité sont appelées substitutions.
– authentification. L’authentification consiste à vérifier l’identité des différents
éléments impliqués dans un dialogue. Il peut s’agir d’authentifier une personne : on
parle aussi dans ce cas d’ identification. On parlera par exemple d’authentification
ou d’identification de l’expéditeur, du destinataire. Il peut s’agir aussi d’authentifier
une machine, notamment dans le cadre d’une relation d’un client avec un serveur à
travers un réseau ouvert (exemple : le web) ou un réseau fermé (exemple : Distributeurs
Automatiques de Billets, appelés aussi DAB). On peut vouloir également authentifier
un document, son auteur, le serveur sur lequel on l’a récupéré, etc. Ainsi la notion22 Cryptographie
d’authentification recouvre différentes variantes plus ou moins similaires. Dans le cas
d’un message, c’est-à-dire d’une information échangée, il s’agit de prouver son
origine. Les attaques contre l’authentification sont appelées mascarades.
– non-répudiation. C’est un mécanisme qui empêche de nier un contrat. La
nonrépudiation consiste à prouver par exemple qu’un message a bien été émis par son
expéditeur ou a bien été reçu par son destinataire. L’auteur d’un message ne peut nier
l’avoir écrit ou transmis.
– signature. C’est un mécanisme qui garantit l’authentification de l’expéditeur,
l’intégrité des données et la non-répudiation.
– certification. Une entité connue, digne de confiance, valide une certaine
information.
– contrôle d’accès. L’accès à certaines ressources est limité aux personnes
autorisées.
– gestion des clés. En général les systèmes cryptographiques utilisent des clés (clés
secrètes, clés privées, clés publiques). La gestion de ces clés (distribution, intégrité,
recouvrement, etc.) est un problème difficile.
– preuve. Plus généralement, une entité appelée prouveur souhaite démontrer à
une autre entité appelée vérificateur qu’elle détient un certain secret (mot de passe
par exemple ou clé secrète, etc.). Dans certaines circonstances on peut de plus exiger
que ceci se fasse sans que le prouveur dévoile au vérificateur une information qui
pourrait permettre à celui-ci de reconstituer en pratique tout ou partie du secret. On
parle alors de preuve à divulgation nulle.
Ceci n’est pas, bien entendu, une liste exhaustive. Remarquons aussi que toutes ces
fonctionnalités ne sont pas indépendantes les unes des autres. Plusieurs d’entre elles
font appel à des mécanismes semblables.
1.1.2.2. Problèmes de base
Les objectifs peuvent être atteints par l’usage de techniques cryptographiques de
base qui sont en quelque sorte les briques permettant de construire des systèmes plus
complexes mettant en jeux des protocoles. Nous allons décrire les techniques de base
les plus importantes :
– le chiffrement ;
– la signature ;
– l’authentification ;
– l’échange de clé.Introduction 23
1.2. Techniques cryptographiques
1.2.1. Chiffrement à clé secrète
1.2.1.1. Description
Le chiffrement à clé secrète a des origines lointaines, et a toujours été associé
à des applications militaires. Donnons tout d’abord la terminologie en usage dans
ce domaine. Le chiffrement consiste à transformer un texte clair en texte chiffré ou
cryptogramme. Le déchiffrement est l’opération qui consiste à retrouver le texte clair
à partir du texte chiffré lorsqu’on dispose de la clé. Le décryptage consiste à retrouver
le texte clair à partir du chiffré lorsqu’on ne connaît pas la clé. Ainsi un expéditeur
chiffre un texte clair et envoie le chiffré à un destinataire. Celui-ci le déchiffre et
récupère ainsi le texte clair. Un attaquant (ou ennemi) passif écoute la communication
et tente à partir du chiffré une cryptanalyse afin de le décrypter.
Dans un système à clé secrète ou symétrique un expéditeur et un destinataire
partagent une même clé secrète. Cette clé est utilisée à la fois pour le chiffrement
et pour le déchiffrement et doit rester secrète de tout observateur ennemi. À chaque
cléK sont associées une fonction de chiffrementC et une fonction de déchiffrementK
D . L’expéditeur chiffre le texte clairm pour obtenir le texte chiffréc =C (m) etK K
envoiec au destinataire. Le destinataire rétablit le texte clair en calculantm =D (c)K
(voir la figure 1.1). Autrement ditD C = Identité.K K
D (c)Km c = E (m) cKAlice E Bob D m
KGénérateur
de clés
Figure 1.1. Schéma classique d’un système de chiffrement à clé secrète
Dans son article intitulé « La cryptographie militaire » (Journal des sciences
militaires, vol. IX, pp. 5-38, janvier 1883 et pp. 161-191, février 1883), Auguste
Kerckhoffs donne des principes de base de la cryptographie à clé secrète : « Il faut bien
distinguer entre un système d’écriture chiffrée, imaginé pour un échange momentané
de lettres entre quelques personnes isolées, et une méthode de cryptographie destinée
à régler pour un temps illimité la correspondance des différents chefs d’armée entre
eux. Ceux-ci, en effet, ne peuvent à leur gré et à un moment donné, modifier leurs
conventions ; de plus, ils ne doivent jamais garder sur eux aucun objet ou écrit qui
soit de nature à éclairer l’ennemi sur le sens des dépêches secrètes qui pourraient
tomber entre ses mains.24 Cryptographie
Un grand nombre de combinaisons ingénieuses peuvent répondre au but qu’on
veut atteindre dans le premier cas ; dans le second, il faut un système remplissant
certaines conditions exceptionnelles, conditions que je résumerai sous les six chefs
suivants :
1˚ Le système doit être matériellement, sinon mathématiquement, indéchiffrable ;
2˚ Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre
les mains de l’ennemi ;
3˚ La clef doit pouvoir être communiquée et retenue sans le secours de notes
écrites, et être changée ou modifiée au gré des correspondants ;
4˚ Il faut qu’il soit applicable à la correspondance télégraphique ;
5˚ Il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige
pas le concours de plusieurs personnes ;
6˚ Enfin il est nécessaire, vu les circonstances qui en commandent l’application,
que le système soit d’un usage facile, ne demandant ni tension d’esprit, ni la
connaissance d’une longue série de règles à observer. »
Un peu plus loin dans le texte, il conclut : « Eh bien ! si l’Administration veut
mettre à profit tous les services que peut rendre un système de correspondance
cryptographique bien combiné, elle doit absolument renoncer aux méthodes secrètes, et
établir en principe qu’elle n’acceptera qu’un procédé qui puisse être enseigné au
grand jour dans nos écoles militaires, que nos élèves seront libres de communiquer
à qui leur plaira, et que nos voisins pourront même copier et adopter si cela leur
convient. »
La leçon principale de ces extraits est que la sécurité du système doit reposer sur
la robustesse de la clé et non pas sur le fait que le système de chiffrement est inconnu
de l’ennemi.
Les problèmes difficiles principaux liés à un tel système sont : engendrer et
échanger la clé secrète, la stocker, éviter de l’exposer lors de son utilisation pour chiffrer
ou déchiffrer. L’élaboration d’une clé secrète nécessite généralement l’utilisation d’un
générateur aléatoire dont le comportement ne doit pas être prévisible afin qu’un intrus
ne puisse pas deviner quelle clé va être utilisée. Le problème d’échange de la clé est
spécifique de la cryptographie à clé secrète. La clé doit être communiquée par un
canal sûr. L’utilisation d’une clé secrète entraîne la notion de sphère de confiance pour
le partage de la clé. Le partage de clés qui est acceptable en réseau fermé (exemple :
réseau de type militaire avec préchargement des clés en usine) n’est plus envisageable
en réseau ouvert (exemple : l’internet).Introduction 25
Nous verrons que les cryptosystèmes symétriques se répartissent en deux familles :
le chiffrement à flot et le chiffrement par bloc.
1.2.1.2. Chiffrement à flot
Une méthode de chiffrement à flot opère individuellement sur chaque bit de texte
clair en utilisant une transformation qui varie en fonction de la place du bit d’entrée.
Le cryptosystème de Vernam appelé aussi one-time-pad ou encore masque jetable
est le prototype de ces systèmes. Il utilise une clé secrète très longue qui devrait de
manière idéale représenter une suite aléatoire de bits. Si on a un messagem den bits
à chiffrer, on considère les n premiers bits de la clé qui constituent un motK et on
calcule le « ou exclusif bit à bit » entre le message et cette partie de la clé, c’est-à-dire
que le texte chiffré s’écrit sous la formec = mK. Ainsi la partieK de la clé sert
de masque. Le destinataire qui partage la même clé extrait de la même façon la partie
K et récupère alors le texte clairm en calculantm =cK. Les deux interlocuteurs
jettent la partieK utilisée et peuvent effectuer une nouvelle transaction en procédant
de même avec le reste de la clé.
partie utilisée K nouvelle clé
. . . . . . . . . . . . . .0 1 1 0 1 0 1 1 1 1 0 clé
1 1 1 0 0 1 0 texte clair m
1 0 0 0 1 1 1 texte chiffré c=m XOR K
Figure 1.2. Le masque jetable
Construire une clé aussi longue et qui de plus soit une suite aléatoire de bits n’est
pas chose facile. Il est possible de réaliser approximativement un tel système à partir
d’un générateur pseudo-aléatoire et d’un germe.
1.2.1.3. Chiffrement par bloc
Un système de chiffrement par bloc opère avec une transformation fixe qui
s’applique sur des blocs de texte clair, de taille fixe.
Il existe de nombreux systèmes de chiffrement par bloc. Citons quelques systèmes,
dont certains seront détaillés par la suite.
– DES (Data Encryption Standard). C’est le standard ANSI X3.92, proposé en
1974, publié dans le Federal Register en 1975, adopté comme standard en 1977
(FIPS46). C’est un système symétrique qui utilise une clé de 56 bits (complétée par 8 bits de26 Cryptographie
Block
SORTIEENTREE Cipher
CLE
Figure 1.3. Chiffrement par bloc
parité), des entrées de texte clair de 64 bits et des sorties de texte chiffré de 64 bits. Ce
système est maintenant considéré comme trop faible en raison de la taille trop petite
des clés. Il est encore utilisé principalement dans le 3-DES.
– 3-DES. Appelé encore Triple DES, c’est le standard ANSI X9.71 et ISO 9732
(1985). On compose trois circuits précédents de la façon suivante : on utilise deux
clés DESk etk . On chiffre le texte clair aveck on déchiffre la sortie aveck et1 2 1 2
on chiffre cette deuxième sortie aveck . On a donc 112 bits de clé, une entrée de 641
bits et une sortie de 64 bits. Il existe une version utilisant trois clésk ,k etk . On1 2 3
chiffre aveck , la sortie obtenue est déchiffrée aveck et le résultat produit est chiffré1 2
aveck . L’étape de déchiffrement permet en utilisantk =k dans le système à deux3 1 2
clés etk =k ouk =k dans le système à trois clés de transformer le 3-DES en un1 2 2 3
simple DES.
– MISTY1. Il utilise une clé de 128 bits et chiffre des blocs de données de 64 bits.
La sortie est aussi un bloc de 64 bits.
– IDEA (International Data Encryption Algorithm). Proposé en 1992 par Lai et
Massey. Il utilise une clé de 128 bits, des entrées de texte clair de 64 bits et des sorties
de texte chiffré de 64 bits.
– AES (Advanced Encryption Standard). Nouveau standard américain de
chiffrement par bloc qui remplace le DES. Il a été proposé en 1998 par J. Daemen et V.
Rijmen sous le nom de Rijndael, retenu en partie par le NIST en 2000. Il est devenu
le standard FIPS-197 en 2001. On a un choix pour la taille des clés : 128, 192 ou
256 bits. Bien que Rijndael propose aussi un choix pour la taille des textes clairs et
chiffrés : 128, 192, ou 256 bits, le standard AES n’a retenu que la taille 128 bits.
– Camellia. Ce système offre aussi un choix pour la taille des clés : 128, 192 ou
256 bits. La taille des textes clairs et chiffrés est fixée à 128 bits.
– SHACAL-2. Il utilise une clé secrète de 512 bits et travaille sur des blocs de 256
bits.Introduction 27
MISTY1, AES (version 128 bits de données), Camellia, SHACAL-2 ont été
retenus par le projet européen NESSIE ( New European Schemes for Signatures,
Integrity, and Encryption).
1.2.2. Chiffrement à clé publique
1.2.2.1. Description
En 1976, Diffie et Hellman introduisent la notion de couple de clés : l’une servant
au chiffrement et l’autre au déchiffrement. C’est le début de l’ère de la cryptographie
à clé publique et du règne du système RSA développé en 1977 par Rivest, Shamir et
Adleman. Aujourd’hui, il existe divers systèmes à clé publique.
Dans un cryptosystème à clé publique, chaque utilisateur A dispose d’une paire
de clés : une clé privéed et une clé publiquee . La clé privée deA n’est connueA A
que de A. La clé publique est publiée et connue de tous. Il doit, bien entendu, être
impossible en pratique de calculerd à partir dee . On dispose en outre d’une fonc-A A
tion publique de chiffrementE qui à une clée et un texte clairx fait correspondreA
y =E(e ;x), le chiffré dex à destination deA. On dispose également d’une fonctionA
publique de déchiffrementD qui à la clé privée d de A et à un chiffré y à desti-A
nation deA fait correspondrex =D(d ;y), le texte clair associé ày. RemarquonsA
que seule la clé privée est secrète ; les fonctionsE etD sont publiques. On notera
E la fonction de chiffrement à destination deA, c’est-à-dire la fonction définie parA
E (x) =E(e ;x) ; de même on désignera parD la fonction de déchiffrement deA A A
A, c’est-à-dire la fonction définie parD (y) =D(d ;y). Pour tout utilisateurA duA A
système on a donc :
D E = Identité:A A
Pour résumer la situation disons que si l’expéditeurB veut communiquer le texte
clairm àA, il calcule le texte chiffréc = E (m) en utilisant la clé publique deA,A
et il envoiec àA. Le destinataireA retrouve le texte clair en calculantm = D (c)A
grâce à sa clé privée (voir la figure 1.4).
D(d ;c)c =E(e ;m) Bm B Bob c
Alice E D m
dB
Zone Publique
eB
Figure 1.4. Schéma classique d’un système de chiffrement à clé publique
L’existence d’un tel cryptosystème est basée sur la possibilité de construire des
paires de fonctions réciproques l’une de l’autre,E etD , qui sont faciles à calculerA A28 Cryptographie
et oùE est très dure à inverser. Les systèmes à clé publique reposent sur la difficultéA
d’effectuer en pratique certains calculs.
Dans un tel système il n’y a pas de clé secrète à échanger : la clé privée ne sort
pas de chezA et la clé publique est connue de tous. Toutefois il reste les problèmes de
gestion de clé :
– comment éviter que la clé publique ne soit corrompue par une attaque
malveillante du serveur de clés ou même forgée ?
– comment éviter que la clé privée ne soit exposée, soit lorsqu’elle est stockée
(faiblesse du moyen de stockage), soit lors de son utilisation (inspection de la mémoire
de la machine utilisant la clé, virus malveillants, etc.) ?
1.2.2.2. Systèmes de chiffrement à clé publique
Citons quelques systèmes à clé publique dont certains seront décrits plus en détail
dans la suite de cet ouvrage.
– RSA (Rivest-Shamir-Adleman). Ce système est basé sur la difficulté de
factoriser un produit de deux nombres premiers. Associé à l’encodage KEM ( Key
Encapsulation Mechanism) il a été retenu par le projet NESSIE.
– ElGamal. Ce système est basé sur la difficulté du problème du logarithme discret
dans certains groupes.
– PSEC ( Provable Secure Elliptic Curve Encryption). Ce chiffrement utilise
le calcul sur le groupe des points d’une courbe elliptique. Associé à KEM, il a été
également retenu par le projet NESSIE.
– Rabin. Ce système est basé sur la difficulté d’extraire une racine carrée modulo
un produitn de deux grands nombres premiers (la décomposition den étant secrète).
– McEliece. Ce système est basé sur la difficulté du décodage d’un code correcteur
linéaire binaire quelconque et sur l’indistinguabilité des codes de Goppa.
– Diffie-Hellman. Ce système qui permet d’échanger des clés a été le premier
protocole utilisant le principe de la cryptographie à clé publique.
1.2.3. Signature
1.2.3.1. Description
Un algorithme de signature numérique a plusieurs volets. Tout d’abord un
condensé du message est calculé avec une fonction de hachage. Ainsi, le messageM est
transformé en un messagem =h(M) en général plus court, de longueur fixée, grâce à
une fonction publique de hachageh. Pour la partie signature proprement dite, chaque
utilisateurA dispose d’une clé publiquee et d’une clé privéed . Le système définitA A
une fonction de signatureS qui à une clé privéed et à un message condensém faitA
correspondres =S(d ;m), appelé appendice de la signature deM par l’utilisateurAIntroduction 29
A. La démarche est donc la suivante : l’utilisateur A, qui veut signer un message
M, commence par en faire un condensém = h(M) (la fonctionh est publique et
utilisable par tous), puis il calcule, grâce à sa clé privée, l’appendices =S(d ;m).A
Il peut alors transmettre son message signé (M;s). Le système définit également une
fonction de vérificationV qui à une clé publiquee , et à un message signé (M;s)A
fait correspondreV(e ;M;s), valant « vrai » si (M;s) correspond bien à un messageA
signé par A et « faux » sinon (voir la figure 1.5). Nous noteronsS , la fonction deA
signature parA, c’est-à-dire la fonction définie parS (M) = (M;S (d ;h(M))).A A
(M,s) V(e ;M;s)Alice AM Bob V {vrai, faux}S
dA s =S(d ;m)A
M
Zone Publique
eAm=h(M)
h
Figure 1.5. Schéma classique d’un système de signature avec appendice
Remarquons que le processus de signature implique la non-répudiation. En effet,
puisque tout le monde connaît la clé publique deA, tout le monde peut s’assurer que
la signature est bien conforme. CommeA est le seul à avoir accès à la fonctionS ,A
tout le monde peut s’assurer que c’est bienA qui a signé le messageM. Il existe aussi
des algorithmes de signature appelés algorithmes à recouvrement de message dans
lesquels on ne condense pas le message et où le message est récupéré à partir de la
signature.
1.2.3.2. Systèmes de signature numérique
Voici quelques systèmes de signature numérique avec appendice.
– RSA (Rivest-Shamir-Adleman). C’est l’algorithme RSA utilisé « à l’envers » :
celui qui signe, chiffre avec sa clé privée. Tout le monde peut vérifier avec la clé
publique de celui qui a signé. La signature RSA associée à l’encodage PSS (
Probabilistic Signature Scheme) a été retenue par le projet NESSIE.
– DSS (Digital Signature Standard). Utilise DSA (Digital Signature Algorithm)
basé sur la difficulté du problème du logarithme discret sur le groupe multiplicatif
Z=pZ (p étant un grand nombre premier). D’autres alternatives sont possibles dans
le standard DSS : on peut utiliser aussi ECDSA (Elliptic Curve Digital Signature
Algorithm) basé sur la difficulté du problème du logarithme discret sur le groupe des
points d’une courbe elliptique, ou encore RSA. Le standard ECDSA a été retenu par
le projet NESSIE.30 Cryptographie
1.2.3.3. Fonctions de hachage
Une fonction de hachage transforme un long message en un résumé court, de
taille fixe. L’image d’un message par une fonction de hachage s’appelle le condensé
du message, l’ empreinte du message, le résumé du message ou encore le message
haché. Une fonction de hachage doit posséder deux qualités indispensables :
– résistance à la détermination d’une préimage, ce qui signifie qu’il doit être
impossible en pratique, à partir d’un résumém, de retrouver un messageM ayant ce
résumé, c’est-à-dire tel que m = h(M) ; l’« impossibilité en pratique » dont nous
parlons ici, fait référence à la difficulté calculatoire de l’opération en question. Un
peu plus précisément, les algorithmes connus qui peuvent mener à bien l’opération
« impossible » s’exécutent en un temps bien trop long pour être en pratique menés
à leur terme. Tout ceci fait référence à la complexité des algorithmes présentée dans
l’annexe A.
– résistance aux collisions, ce qui signifie qu’il est impossible en pratique de
construire deux messagesM etM ayant le même résumé :h(M ) =h(M ).1 2 1 2
Bien entendu, comme une fonction de hachageh transforme un long message en
un message court, la fonctionh n’est certainement pas injective. Donc les deux
propriétés demandées aux fonctions de hachage ne peuvent être réalisées qu’à cause de
l’inextricabilité des calculs qui permettraient de revenir aux préimages, ou de
provoquer des collisions. Cependant l’inextricabilité des calculs n’est assurée que si la
taille fixe des images de la fonctionh est suffisamment grande. Le paradoxe des
anniversaires (qui fait apparaître que, lors d’une réunion, la probabilité pour que deux
personnes aient le même jour d’anniversaire, est relativement grande) nous impose
une taille minimale de l’image afin d’éviter précisément l’attaque des anniversaires
(décrite en détail dans l’annexe D). Une taille de 128 bits est maintenant considérée
comme trop courte et il est conseillé de prendre au moins 160 bits. Il existe de
nombreuses fonctions de hachage.
– SHA1 (Secure Hash Algorithm), qui fournit en sortie un bloc de 160 bits.
– MD5 (Message Digest), qui donne une empreinte sur 128 bits.
– SHA-224, SHA-256, SHA-384, SHA-512 . Ce sont des améliorations de SHA1.
Les trois dernières fonctions fournissent une résistance aux attaques brutales
comparable à la résistance des diverses versions de AES (SHA-256 à mettre en rapport avec
AES-128, SHA-384 à mettre en rapport avec AES-192, SHA-512 à mettre en rapport
avec AES-256). Elles ont été retenues par le projet NESSIE.
– Whirlpool. Cette fonction a une sortie de 512 bits. Whirlpool a été retenue par le
projet NESSIE.
– utilisation de systèmes de chiffrement par bloc (par exemple AES).Introduction 31
1.2.4. Authentification
1.2.4.1. Description
L’authentification (voir le paragraphe 1.1.2.1) est un mécanisme qui couvre
plusieurs fonctionnalités voisines. Par exemple, il garantit que l’expéditeur d’un message
est bien celui qu’il prétend être et que le message n’est pas corrompu ou forgé
(identification et intégrité des données). On peut penser à utiliser un processus de signature
pour obtenir l’authentification. C’est une possibilité, mais il faut remarquer toutefois
que la signature demande des fonctionnalités différentes de celles de
l’authentification. Par exemple, l’authentification ne requiert pas la non-répudiation. De plus dans
un processus de signature, tout le monde peut vérifier la conformité de la signature.
Ceci peut éventuellement être indésirable dans un processus d’authentification. En
revanche l’authentification peut éventuellement requérir un empêchement de rejeu,
c’est-à-dire empêcher la réutilisation des données échangées lors d’une précédente
authentification. Par exemple on voudra éviter qu’un chèque numérique soit présenté
plusieurs fois. Ceci peut se faire par un système de datation ou horodatage.
1.2.4.2. Systèmes d’authentification
Citons quelques systèmes d’authentification ou d’identification parmi les plus
connus :
– il est possible de construire des MAC (Message Authentication Code) en
utilisant des systèmes de chiffrement par bloc à clé secrète (DES, AES).
– le système d’authentification de Feige-Fiat-Shamir qui fournit un processus
d’identification basé sur la difficulté de l’extraction d’une racine carrée modulo n,
lorsquen est un nombre composé et que sa factorisation n’est pas connue.
– UMAC (retenu par le projet NESSIE). La conception de ce système utilise une
famille très intéressante de fonctions de hachage.
– certains protocoles d’échanges de signatures permettent d’assurer l’identification
mutuelle des protagonistes.
1.3. Techniques mathématiques
1.3.1. Fonctions
1.3.1.1. Fonctions à sens unique
Une fonction à sens unique est une fonction qui est facile à calculer et difficile
1à inverser (c’est-à-dire que f (y) est difficile à calculer pour « presque tout » y).
Les significations exactes de « facile » et « difficile » dans la définition précédente
demandent quelques notions de théorie de la complexité des algorithmes. Ceci est
développé dans l’annexe A.6
32 Cryptographie
De manière intuitive nous pouvons dire que quelque chose est facile à calculer si
nous pouvons faire le calcul en temps polynomial. D’un autre côté, nous pouvons dire
que quelque chose est dur à calculer si nous ne pouvons pas le calculer en temps
polynomial. Il semble donc que les bons candidats pour des problèmes durs soient les
problèmes de la classeNP . Mais ceci est inexact, car un problèmeNP peut être dur
dans les plus mauvais cas, mais être facile pour de nombreuses instances. De plus nous
ne savons pas siP = NP . La question est donc compliquée. Nous introduirons par
la suite (voir l’annexe A) plusieurs autres classes de complexité (ZPP ,RP ,BPP ).
En fait nous ne savons pas s’il existe des fonctions à sens unique, mais certaines
fonctions semblent en pratique jouer ce rôle. Remarquons enfin, que les algorithmes non
polynomiaux peuvent aussi avoir des degrés de difficulté différents : on distingue par
exemple les algorithmes exponentiels des algorithmes sous-exponentiels (voir le
paragraphe A.3.1). Cette distinction n’est pas anodine, elle a des conséquences directes
sur la taille des clés des systèmes qui s’appuient sur la difficulté du problème en
question. On prendra par exemple une taille de clé de 160 bits pour un système qui s’appuie
sur un problème dont on ne connaît que des attaques exponentielles et de 1024 bits
pour un système qui s’appuie sur un problème dont on connaît des attaques
sousexponentielles.
1.3.1.2. Fonctions à sens unique avec trappe
Une fonction à sens unique avec trappe ou brèche secrète est une fonction à sens
unique qui devient facile à inverser si on connaît une valeur secrète.
1.3.1.3. Fonctions de hachage
Une fonction de hachage (voir le paragraphe 1.2.3.3) transforme un long message
en un bloc court de taille fixe (le résumé, le condensé, l’ empreinte, le haché). Si
bien que de nombreux messages ont le même résumé. Mais en pratique personne ne
doit être capable de construire un message ayant un résumé donné ( résistance à la
détermination d’une préimage), c’est-à-dire qu’une fonction de hachage doit être à
sens unique. De plus, personne ne doit être capable en pratique de construire deux
messages distincts ayant le même résumé ( résistance aux collisions). On pourra se
reporter à l’annexe D pour voir une étude mathématique de cette résistance (paradoxe
des anniversaires) .
1.3.2. Arithmétique et algèbre
1.3.2.1. Problème de la factorisation
Étant donné un entier n qui est le produit de deux grands nombres premiers,
n = pq, déterminerp etq. La difficulté de ce problème est utilisée dans le système
de chiffrement RSA, ainsi que dans la signature RSA et aussi dans la méthode
d’identification de Feige-Fiat-Shamir (en conjonction avec le problème de l’extraction de
racines carrées modulon).Introduction 33
On dispose de plusieurs algorithmes (non polynomiaux bien entendu) de
factorisation des entiers. Par exemple :
– méthode de Pollard ;
–p 1 de Pollard ;
– méthode des fractions continues ;
– des courbes elliptiques ;
– multiple polynomial quadratic sieve ;
– number field sieve.
La méthodep 1 de Pollard s’exécute en général en temps exponentiel (voir le
paragraphe A.3.1), mais est très efficace dans les cas particuliers où p 1 n’a que
des petits facteurs premiers (on dit alors quep 1 est friable). Les quatre derniers
algorithmes cités s’exécutent en temps sous-exponentiel (voir le paragraphe A.3.1).
1.3.2.2. Racines carrées
Soitp un nombre premier> 2 etx un carré dans Z=pZ. Il est possible de calculer
p+1
4en pratique les racines carrées dex. Sip 3 mod 4,x est une solution. Sip 1
mod 4, on utilise l’algorithme de Shanks (voir le paragraphe B.5.2).
Soitn = pq le produit de deux grands nombres premiers distincts. Sip etq sont
connus, en utilisant le théorème des restes chinois, on peut calculer une racine carrée
dans Z=nZ. Mais si la factorisation de n n’est pas connue, le problème de trouver
une racine carrée den est difficile. Ce problème est d’ailleurs en un certain sens aussi
difficile que de factorisern (voir le paragraphe 2.2.3.1).
Ceci est par exemple utilisé dans la méthode d’identification de Feige-Fiat-Shamir.
1.3.2.3. Problème du logarithme discret
SoitG un groupe commutatif fini ayant beaucoup d’éléments etH un sous-groupe
ncyclique de G engendré par un élément a. Étant donné un a , retrouver n est
appelé le problème du logarithme discret en base a (par similitude avec R, où on a
nn = log a ). Pour certains groupes ce problème est difficile (c’est-à-dire que lesa
meilleurs algorithmes connus ne sont pas polynomiaux). Par exemple dans le groupe
multiplicatif d’un corps fini F (pourq bien choisi) et en particulier dans Z=pZ pourq
certains nombres premiersp.
On connaît des algorithmes (non polynomiaux) pour résoudre le problème du
logarithme discret dans les groupes multiplicatifs (Z=pZ) (où p est premier). Par
exemple :
– méthode rho de Pollard ;34 Cryptographie
– méthode giant steps, baby steps (Shanks) ;
– de Pohlig et Hellman ;
– méthodes de l’index : algorithme d’Adleman, algorithme de Coppersmith,
Function Field Sieve.
Les méthodes de l’index donnent des algorithmes sous-exponentiels.
Pour les corps finis, on connaît également des algorithmes sous-exponentiels pour
calculer les logarithmes discrets. On peut alors penser, afin de réduire les tailles des
clés, à utiliser des groupes plus compliqués. Le groupe d’une courbe elliptique et,
plus généralement, la Jacobienne de certaines courbes algébriques procurent de tels
groupes, au prix d’une complication de la représentation des éléments et d’une
augmentation du coût de l’opération du groupe. Actuellement l’utilisation de courbes
elliptiques bien choisies semble intéressante et de nombreux systèmes exploitent
effectivement cette possibilité.
La difficulté du problème du logarithme discret est utilisée en particulier dans les
méthodes suivantes :
– échange de clé de Diffie et Hellman ;
– les cryptosystèmes d’ ElGamal ;
– la signature DSA (et des généralisations comme ECDSA).
1.3.3. Générateurs pseudo-aléatoires
1.3.3.1. Description
Un générateur pseudo-aléatoire produit à partir d’un nombre initial appelé germe
une suite de nombres ayant de bonnes propriétés statistiques de répartition. Pour un
usage cryptographique un tel générateur doit posséder également de bonnes propriétés
d’imprévisibilité. Les générateurs pseudo-aléatoires sont en général construits à l’aide
de suites récurrentes. Le germe fournit le premier terme de la suite. Le qualificatif
« pseudo » fait référence au fait qu’un tel générateur, ayant une structure
mathématique, procure une « simulation » de l’aléa tout en étant déterministe.
1.3.3.2. Générateurs
De nombreux générateurs classiques de suites pseudo-aléatoires utilisés pour la
simulation de problèmes statistiques ne sont pas « imprévisibles » et par conséquent
ne sont pas utilisables pour la cryptographie. C’est le cas, par exemple, des suites
récurrentes linéaires. On présentera par la suite le générateur BBS (Blum, Blum,
Shub) qui est très sûr, mais certainement pas assez rapide. On peut aussi utiliser une
fonction de hachage (par exemple SHA256) dont on concatène les itérées.Introduction 35
Avec un bon générateur pseudo-aléatoire, on peut émuler un système à masque
jetable.
1.3.4. Théorie de la complexité des algorithmes
1.3.4.1. Description
Shannon a donné une définition de la sécurité parfaite (voir la section 6.2). Mais
dans un cryptosystème répondant aux critères de la sécurité parfaite, il est nécessaire
de disposer d’une clé aussi longue que la somme des longueurs de tous les textes
clairs à chiffrer, cette clé étant à tirer au hasard dans un ensemble de clés équiréparti.
Pendant les années de guerre froide entre le bloc de l’Est et le bloc de l’Ouest, ce
système a fonctionné pour la liaison téléphonique (appelée alors téléphone rouge)
entre la Maison Blanche et le Kremlin. Cependant, ces contraintes sont vraiment trop
fortes à réaliser dans les systèmes civils concrets. On dispose alors de notions plus
faibles de sécurité basées sur l’impossibilité de réaliser en pratique certains calculs.
La théorie de la complexité nous permet d’évaluer le temps d’exécution de certains
algorithmes et la résistance de certaines fonctions cryptographiques.
Certaines notions cryptographiques importantes, comme par exemple la notion de
fonction à sens unique, sont définies à l’aide des classes de complexité.
1.3.4.2. Classes de complexité
Les classes de complexité sont définies à partir des machines de Turing, des
machines de Turing non déterministes et des machines de Turing probabilistes.
L’exécution d’une machine de Turing non déterministe dépend d’une suite de choix. Si on met
une probabilité sur ces choix, on obtient alors une machine de Turing probabiliste.
Voici quelques classes de complexité détaillées dans l’annexe A :
– P : complexité polynomiale ;
– NP : complexité non déterministe polynomiale ;
– ZPP : complexité « Zero-sided probabilistic polynomial » ;
– RP : complexité « Random polynomial » ;
– BPP : complexité « Bounded probabilistic polynomial ».
1.4. Protocoles, systèmes complexes
Voici une liste non exhaustive de quelques applications concrètes des outils
cryptographiques.
– PGP (Pretty Good Privacy) : un système cryptographique fournissant
chiffrement et signature. Il peut être utilisé pour le courrier électronique ou pour les
transactions commerciales.36 Cryptographie
– Kerberos : un système complet dans lequel des clients obtiennent d’un centre de
distribution de clés une clé de session afin de pouvoir communiquer avec un serveur.
– Station to station protocol : ce système qui utilise à la fois de la cryptographie
à clé publique, de la cryptographie à clé secrète et de l’authentification mutuelle des
correspondants, est décrit au chapitre 4.
– SSH : protocole réseau permettant l’accès sécurisé aux ressources d’une machine
distante. Ce est détaillé dans le chapitre 4.
1.5. Cryptanalyse
1.5.1. Introduction
1.5.1.1. Description
La cryptanalyse est la partie de la cryptologie qui s’occupe de l’attaque des
cryptosystèmes et bien entendu de manière interactive de leur sécurité. Le but principal
de la est de casser les cryptosystèmes, c’est-à-dire de déterminer des
informations (par exemple de récupérer le texte clair, la clé secrète) ou d’interagir avec
le système (par ex de forger une signature ou de modifier un message sans être
découvert) sans bien entendu aucun droit de le faire et notamment sans connaître la
clé secrète. Il est nécessaire d’étudier les deux faces du problème : le point de vue de
la protection et de la sécurité et le point de vue de l’attaquant qui cherche à casser ou
à détourner le système.
Pour développer une théorie de la sécurité (ou de la cryptanalyse) on doit définir la
puissance de l’adversaire : quelle est la puissance de ses moyens de calcul ? Est-il un
adversaire passif ( observateur) ou actif (capable de modifier ou même de forger des
messages) ? De quelles informations dispose-t-il pour mener à bien son attaque ? Nous
devons aussi préciser le type de sécurité que nous voulons assurer. Par exemple quelle
information voulons-nous protéger : le texte clair lui-même ? Toute information sur le
texte clair ? V prouver quelque chose sur la sécurité du cryptosystème ?
Les attaques peuvent être dirigées contre les fonctions de base qui forment le cœur
du système ou contre le protocole et ceci aussi bien contre la conception que contre
l’implémentation.
Dans la suite nous ferons d’une part dans le chapitre 6 une étude théorique de la
sécurité prouvable, d’autre part pour certains systèmes particuliers nous dirons quelques
mots des attaques connues contre eux.Introduction 37
1.5.1.2. À propos de la sécurité
Comme cela a été mentionné précédemment, Shannon a défini une notion de
sécurité parfaite qui n’est guère réalisable en pratique. La sécurité des systèmes
commerciaux repose donc sur une notion plus faible découlant de la sécurité
calculatoire.C’està-dire que la sécurité est basée sur la difficulté de mener à terme certains calculs.
Nous nous demandons s’il est possible de retrouver non pas toute l’information,
mais une partie de cette information. Si le chiffré ne permet pas de retrouver en
pratique quelque information sur le texte clair nous dirons que le système est
sémantiquement sûr.
Il n’existe pas de preuve absolue de la sécurité d’un système, mais nous pourrons
parfois prouver que, sous certaines conditions d’attaque, cryptanalyser de façon
efficace un système reviendrait à résoudre un problème connu pour être difficile. Ce
raisonnement est à la base de la sécurité prouvable.
1.5.1.3. Classification des attaques
Le principe de Kerckhoffs (voir le paragraphe 1.2.1.1) définit l’hypothèse de base :
le cryptanalyste connaît tout sur le fonctionnement du système sauf la clé secrète (ou
privée).
Il existe diverses attaques suivant les informations dont peut disposer le
cryptanalyste, en voici quelques-unes :
– attaque à chiffré seul. Le cryptanalyste ne connaît que le chiffré.
– attaque à textes clairs connus. Le cryptanalyste connaît des paires de textes clairs
et leurs chiffrés.
– attaque à textes clairs choisis. L’attaquant peut obtenir le chiffrement des textes
clairs de son choix et ceci seulement avant la donnée du chiffré à attaquer (appelé dans
la suite le challenge).
– attaque adaptative à textes clairs choisis. L’attaquant peut obtenir le chiffrement
des textes clairs de son choix avant et après la donnée du challenge. Le qualificatif
adaptatif provient du fait que l’attaquant peut adapter sa façon d’engendrer les textes
clairs dont il souhaite obtenir le chiffrement, une fois qu’il connaît le challenge.
– attaque à textes chiffrés choisis (attaque CCA1). L’attaquant peut obtenir le
déchiffrement des textes chiffrés de son choix et ceci seulement avant la donnée du
challenge.
– attaque adaptative à textes chiffrés choisis (attaque CCA2). L’attaquant peut
obtenir le déchiffrement des textes chiffrés de son choix et ceci avant et après la donnée
du challenge (à l’exception de celui-ci).38 Cryptographie
Remarquons que dans un système à clé publique, l’adversaire dispose de la clé de
chiffrement qui est publique. Il peut donc toujours porter au moins une attaque à textes
clairs choisis (et même adaptative).
1.5.2. Quelques attaques concrètes
1.5.2.1. Cryptographie à clé publique
Voici quelques attaques classiques contre la fonction RSA (voir le chapitre 2) :
– module commun ;
– petit exposant privé ;
– petit e public, attaque par « broadcast » ;
– attaque par analyse de temps, par analyse de courant.
1.5.2.2. Cryptographie à clé secrète
Voici quelques attaques classiques contre les systèmes de chiffrement par bloc
(voir le chapitre 3) :
– cryptanalyse différentielle ;
– linéaire ;
– attaque par interpolation.
1.6. La normalisation et la standardisation
Les questions de normalisation et de standardisation sont centrales dans tout
problème d’informatique, d’informatique communicante et donc de cryptographie.
Rappelons que les standards se définissent de facto et que les normes sont définies de jure
par un organisme normalisateur comme :
– l’ ISO ( International Standards Organization);
– l’ ITU ( Telecommunication Union) ;
– l’ ANSI ( American National Standards Institute) ;
– l’ ECMA ( European Computer Manufacturers Association) ;
– l’ IEEE ( Institute of Electrical and Electronics Ingineers) ;
– le NIST ( National Institute of Standards and Technology);
– ou l’ AFNOR ( Association Française pour la NORmalisation).
Dans le cas de l’internet, les standards sont appelés des RFC ( Request For
Comments). Il peut s’agir de définitions de protocoles, de projets, de comptes-rendus de
réunions, de spécifications de standards, etc. Les RFC sont des documents publics,