Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Exercices et problèmes de cryptographie Damien Vergnaud Préface de Jacques Ster

Exercices et problèmes de cryptographie Damien Vergnaud Préface de Jacques Stern Exercices et problèmes de cryptographie 2e édition Illustration de couverture : Energy of fractal realms © agsandrew-Fotolia.com © Dunod, 2012, 2015 5 rue Laromiguière, 75005 Paris www.dunod.com ISBN 978-2-10-072145-0 PRÉFACE « Pour devenir habile en quelque profession que ce soit, il faut le concours de la nature, de l’étude et de l’exercice ». Cette maxime d’Aristote semble bien mal s’ap- pliquer à la cryptologie tant l’exercice y est absent. Il existe de multiples ouvrages de référence de qualité mais, pour la plupart, ils sollicitent très peu l’initiative des étudiants. Et même ceux – rares – qui sont accompagnés d’un véritable choix de problèmes à résoudre, par exemple sous forme d’un livre compagnon, ne couvrent pas totalement une discipline qui connaît une évolution rapide. C’est donc un réel manque que vient combler le recueil que propose Damien Vergnaud. Le livre que j’ai le plaisir de présenter est issu d’un vrai travail de terrain puisqu’il est le résultat de plusieurs années d’enseignement de la cryptologie à l’École nor- male supérieure. À l’évidence, l’auteur a beaucoup de talent pour éveiller l’intérêt des étudiants et les conduire, pas à pas, à s’approprier les concepts et les méthodes de la science du secret. Beaucoup de culture également, puisque les sujets choisis sont extrêmement variés à l’image d’une science qui emprunte à l’algèbre, à la théorie des probabilités, à l’algorithmique, à la théorie de l’information. D’ailleurs, ils débordent largement le cadre strict de la cryptographie. Ce talent et cette culture conduisent à un choix d’exercices qui ne demandent pas simplement à l’étudiant de faire des gammes mais lui proposent de s’attaquer à de véritables compositions : ici un eﬀort raison- nable de programmation illustre des cryptanalyses célèbres comme celle de l’Enigma ou celle du programme Venona qui a permis l’interception de communications où les services russes mettaient incorrectement en œuvre le chiﬀrement jetable ; là une invi- tation à « mettre la main à la pâte » permet d’entrer de plain-pied dans les méthodes modernes de cryptanalyse – diﬀérentielle et linéaire – des algorithmes convention- nels tels que le DES ou l’AES ; là encore, une initiation progressive aux méthodes de factorisation d’entiers, intimement liées à la sécurité du RSA est proposée. Présenter un tel ouvrage comme un simple livre d’exercices est le reﬂet de la mo- destie de son auteur. Certes, il permet la pratique nécessaire à l’acquisition des élé- ments essentiels de la cryptologie. Mais il va au-delà de cet objectif : chaque chapitre inclut une présentation qui est un véritable cours d’introduction et l’ensemble consti- tue de fait une forme d’ouvrage d’enseignement avancé fondé sur la pratique. En d’autres termes, le lecteur qui va au terme de tous les exercices proposés est déjà un © Dunod. Toute reproduction non autorisée est un délit. V Exercices et problèmes de cryptographie véritable spécialiste, capable de se confronter aux multiples concepts que la cryptolo- gie moderne a développés ces trente dernières années. À un moment où la cryptologie est au cœur de la société de l’information, de l’internet aux moyens de paiement en passant par les téléphones portables, une telle expertise est indispensable et il faut souhaiter au livre de Damien Vergnaud des lecteurs à la fois nombreux et actifs. Jacques Stern Professeur à l’École normale supérieure VI TABLE DES MATIÈRES Préface V Avant-propos XIII Notations XV Chapitre 1. Cryptographie classique 1 1.1 Chiffrement par substitution mono-alphabétique 1 Exercice 1.1 (avec programmation). Chiffrement de César 3 Exercice 1.2 (avec programmation). Chiﬀrement aﬃne 4 Exercice 1.3 (avec programmation). Chiﬀrement par substitution mono-alphabétique 5 1.2 Chiffrement par substitution poly-alphabétique 8 Exercice 1.4 (avec programmation). Chiﬀrement de Vigenère – test de Kasiski 9 Exercice 1.5 (avec programmation). Chiﬀrement de Vigenère – indice de coïncidence 11 Exercice 1.6. Chiﬀrement de Hill – nombre de clés 12 Exercice 1.7. Chiﬀrement de Hill – attaque à clair connu 13 1.3 Chiffrement par transposition 14 Exercice 1.8 (avec programmation). Scytale 15 Exercice 1.9 (avec programmation). Chiﬀrement par transposition par colonnes 16 1.4 Chiffrement parfait 17 Exercice 1.10. Carré latin 18 Exercice 1.11 (avec programmation). Mauvaise utilisation du chiﬀrement jetable 20 Problème 1.12. Algorithme de Viterbi 20 1.5 La machine Enigma 22 Exercice 1.13. Enigma – Nombre de clés 24 Exercice 1.14 (avec programmation). Enigma – Tableau de connexions 25 Problème 1.15. Enigma – Indice de coïncidence 27 Chapitre 2. Chiffrement par bloc 31 2.1 Modes opératoires 32 Exercice 2.1. Modes opératoires et propriétés de sécurité 34 Exercice 2.2. Mode opératoire CBC * 36 Problème 2.3. Attaque sur le mode CBC avec le processus de bourrage RFC2040 38 2.2 Schémas de Feistel 39 Exercice 2.4. Schéma de FEISTEL à un ou deux tours 40 Exercice 2.5. Sécurité du schéma de FEISTEL à trois tours 42 Exercice 2.6. Distingueur pour le schéma de FEISTEL à trois tours∗ 43 © Dunod. Toute reproduction non autorisée est un délit. VII Exercices et problèmes de cryptographie 2.3 Chiffrement DES 45 Exercice 2.7. Clés faibles et semi-faibles du chiﬀrement DES 46 Exercice 2.8. Propriété de complémentation du chiﬀrement DES 48 Exercice 2.9. Chiﬀrement DES avec blanchiment 49 Exercice 2.10. Construction de Even-Mansour 50 Exercice 2.11. Double chiﬀrement 51 Exercice 2.12. Chiﬀrement Triple-DES avec deux clés indépendantes 52 Exercice 2.13. Mode opératoire CBC-CBC-ECB 53 2.4 Chiffrement AES 55 Exercice 2.14 (avec programmation). S-Boîte de l’AES 57 Exercice 2.15 (avec programmation). Opération MixColumns 59 Exercice 2.16. Propriétés de l’opération MixColumns 61 Exercice 2.17 (avec programmation). Diversiﬁcation de clé de l’AES 63 Chapitre 3. Fonctions de hachage – Techniques avancées de cryptanalyse 65 3.1 Généralités sur les fonctions de hachage 66 Exercice 3.1. Résistance à la pré-image et aux collisions 66 Exercice 3.2. Construction de Merkle-Damgaård 67 Exercice 3.3 (avec programmation). Collisions sur la fonction MD5 tronquée 71 3.2 Chiffrement par bloc et fonction de compression 72 Exercice 3.4. Chiﬀrement par bloc et fonction de compression 72 Exercice 3.5. Sécurité de la construction de Matyas-Meyer-Oseas avec le DES 73 Exercice 3.6. Attaque en pré-image pour la construction de M. O. RABIN 74 3.3 Attaques génériques sur les fonctions de hachage itérées 76 Exercice 3.7. Multi-collisions pour les fonctions de hachage itérées 76 Exercice 3.8. Attaque en collision contre fonctions de hachage concaténées 78 Problème 3.9. Attaque de Kelsey-Schneier 79 3.4 Cryptanalyse différentielle 82 Exercice 3.10 (avec programmation). Table des diﬀérences du DES 83 Problème 3.11. Cryptanalyse diﬀérentielle de FEAL-4 85 3.5 Cryptanalyse différentielle impossible 89 Exercice 3.12. Attaque par diﬀérentielle impossible contre DEAL 89 Problème 3.13. Attaque par diﬀérentielle impossible contre l’AES 92 3.6 Cryptanalyse linéaire 96 Exercice 3.14 (avec programmation). Table d’approximation linéaire du DES 96 Exercice 3.15. Approximation linéaire de l’addition 98 Problème 3.16. Cryptanalyse linéaire de SAFER 100 Exercice 3.17. Biais de la parité d’une permutation 102 3.7 Attaques par saturation 104 Problème 3.18. Attaque par saturation contre l’AES 104 Exercice 3.19. Attaque par distingueur sur Ladder-DES 108 VIII Table des matières Chapitre 4. Chiffrement par ot 111 4.1 Registres à décalage à rétroaction linéaire 111 Exercice 4.1. LFSR et polynômes de rétroaction 113 Exercice 4.2. Propriétés statistiques d’une suite produite par un LFSR 115 Exercice 4.3. Reconstruction du polynôme de rétroaction minimal 115 4.2 Chiffrement par ﬂot par registres à décalage irrégulier 116 Exercice 4.4 (avec programmation). Distingueur sur le générateur à signal d’arrêt 117 Problème 4.5. Propriétés du générateur par auto-rétrécissement 119 4.3 Chiffrement par ﬂot par registre ﬁltré 120 Exercice 4.6. Attaque « deviner et déterminer » sur Toyocrypt 121 Exercice 4.7. Attaque algébrique sur Toyocrypt* 122 4.4 Chiffrement par ﬂot par registres combinés 124 Exercice 4.8. Attaque par corrélation sur le générateur de Geﬀe 125 Exercice 4.9. Attaque « deviner et déterminer » sur le générateur de Geﬀe 127 Exercice 4.10. Attaque algébrique sur le générateur de Geﬀe 127 4.5 Le chiffrement par ﬂot A5/1 128 Exercice 4.11. États internes de A5/1 129 Exercice 4.12. Attaque par compromis temps-mémoire sur A5/1 131 Problème 4.13. Attaque « deviner et déterminer » sur A5/1 132 4.6 Le chiffrement par ﬂot RC4 135 Exercice 4.14. Cryptanalyse de RC4 sans opération d’échange * 136 Exercice 4.15. Biais de la suite chiﬀrante produite par RC4 137 Problème 4.16. Attaque par recouvrement de clé sur RC4 139 Chapitre 5. Problème du logarithme discret 143 5.1 Logarithme discret dans un groupe générique 143 Exercice 5.1. Multi-exponentiation 145 Exercice 5.2. Algorithme de Shanks 146 Exercice 5.3. Algorithme ρ de Pollard 148 Exercice 5.4. Algorithme de Pohlig-Hellman 151 Exercice 5.5 (avec programmation). Application de l’algorithme de Pohlig-Hellman 153 5.2 Problème du logarithme discret dans (Z/pZ)∗ 154 Exercice 5.6. Entiers friables 155 Problème 5.7. Méthode de Kraitchik – Calcul d’indice * 157 5.3 Problèmes algorithmiques liés au logarithme discret 161 Exercice 5.8. Auto-réductibilité du problème du logarithme discret 161 Exercice 5.9. Algorithme λ de Pollard 163 Problème 5.10. Logarithme discret de petit poids de Hamming 166 5.4 Interpolation polynomiale de logarithme discret 169 Exercice 5.11. Polynôme d’interpolation du logarithme discret 169 Exercice 5.12. Interpolation polynomiale de logarithme discret – Borne inférieure 170 © Dunod. Toute reproduction non autorisée est un délit. IX Exercices et uploads/Litterature/ feuilletage-2.pdf