Remerciez-le!

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

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Sup

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université Dr Moulay Tahar de Saida Faculté des sciences et de la technologie Département de Mathématique et Informatique Mémoire de fin d’étude pour l’obtention du diplôme Master en Informatique Spécialité : Sécurité des Systèmes d’Information et de la Communication Thème : UTILISATION DES TECHNIQUES EURISTIQUES (Algorithme Génétique) POUR LE PROBLEME DE CRYPTANALYSE DU CHIFFREMENT DE VEGENERE Présenté par : Mehdi FEZZA E En nc ca ad dr re eu ur r : : Ahmed Chaouki LOKBANI C Co o- -e en nc ca ad dr re eu ur r : : Reda Mohamed HAMOU Session : Juin 2013 promotion : 2012/2013 Dédicace Je dédie ce modeste travail A ma très chère mère A toi mon père A, mes sœurs, mes frères et mes chers amis. Mehdi FEZZA Remerciement Je remercie Allah pour la force et le courage qu’il m’a donné pour terminer mes études et élaborer ce modeste travail. Ce travail n’aurait certainement jamais vu le jour sans le soutien et le dévouement de certaines personnes que je remercie vivement. Aussi un grand merci à mes encadreurs Monsieur Ahmed Chaouki LOKBANI & Monsieur Reda Mohamed HAMOU pour leurs savoirs, leurs compétences scientifiques et leurs patiences durant ma recherche. Mes remerciments les plus vif s’adressent au comité de jury d’avoir accepté d’examiner et d’évaluer mon travail. Un grand remerciement à mes parents. Mes remerciements les plus sincères à toutes les personnes qui m’ont aidé dans l’élaboration de ce mémoire, même avec un simple sourire. Mehdi FEZZA Table des matières Introduction générale 1 Chapitre I 1/ Définition 4 2/ L’objectif de la sécurité :.............................................................................................................4 3/ Les attaques :...............................................................................................................................4 4/ Les principales attaques : ............................................................................................................5 4.1/ Les virus : .....................................................................................................................5 4.2/ Les vers : .....................................................................................................................6 4.3/ Les bombes logiques :.................................................................................................6 4.4/ Les chevaux de Troie : ................................................................................................6 4.5/ L’attaque par saturation (déni de service) :.................................................................7 4.6/ L’attaque de répudiation IP spoofing :.......................................................................7 5/ L’ espionage:...............................................................................................................................7 5.1/ Man in the middle: .......................................................................................................7 5.2/ Le Spyware :.................................................................................................................8 5.3/ Cookies :......................................................................................................................8 6/ La politique de sécurité :............................................................................................................8 7/ Les outils pour la protection :.....................................................................................................9 7.1/ L’Authentification :......................................................................................................9 7.2/ Le cryptage :.................................................................................................................9 7.3/ Les antivirus :.............................................................................................................10 7.4/ Les pare-feu :.............................................................................................................10 7.4.1/ Le filtrage : ..................................................................................................11 Table des matières 7.4.2/ La translation d'adresses :............................................................................11 8/ Conclusion.................................................................................................................................11 Chapitre II 12 Introduction ...................................................................................................................................13 1/ Définitions et terminologie .......................................................................................................13 1.1/ Domaine d’encryptage ..................................................................................................13 1.2/ Transformation d’encryptage et de décryptage .............................................................13 1.3/ Principe de KERCKHOFF ............................................................................................14 2/ Définitions ................................................................................................................................15 3/ Cryptographie symétrique ........................................................................................................16 4/ Cryptographie asymétrique ......................................................................................................17 5/ La cryptographie classique .......................................................................................................18 5.1/ Substitution ................................................................................................................18 5.1.1/ Chiffre monoalphabetique simple 19 5.1.1.1.1/ Analyse de fréquences ..............................................................19 5.1.1.1.2/ Chiffre de César ........................................................................19 5.1.1.2/ Chiffrement polygraphique.......................................................................20 5.1.1.2.1/ Chiffre Playfair .........................................................................20 5.1.1.2.2/ Chiffre Hill (1929).....................................................................20 5.1.1.3/ Chiffrement polyalphabetique ................................................................21 5.1.1.3.1/ Chiffre de Vigenère ..................................................................22 5.1.1.3.1.1/ Historique ...................................................................22 5.1.1.3.1.2/ Chiffre de Vigenère ....................................................22 5.1.1.3.1.3/ Principe du chiffrement ..............................................23 5.1.1.3.1.4/ La table de Vigenère ..................................................23 5.1.1.3.1.5/ Chiffrement ................................................................24 5.1.1.3.1.6/ Principe mathématique ...............................................25 Table des matières 5.1.1.3.1.7/ Cryptanalyse ...............................................................26 5.1.1.3.2/ Chiffre de Vernam (On Time Pad) ............................................26 5.1.2/ Permutation (transposition) .........................................................................28 5.1.3/ La machine à Rotors ...........................................................................28 5.2/ La cryptographie moderne .........................................................................................30 5.2.1/ Algorithmes de cryptographie symétrique .............................................................30 5.2.1.1/ Cryptosystème par blocs ..........................................................................30 5.2.1.1.1/ La structure de Fiestel ...............................................................31 5.2.1.1.2/ D.E.S .........................................................................................31 5.2.1.1.2.1/ Fonctionnement du DES ............................................32 5.2.1.1.2.2/ Algorithme de cadencement des clés .........................35 5.2.1.1.3/ A.E.S ........................................................................................36 5.2.1.1.3.1/ Fonctionnement du RIJENDEAL ..............................37 5.2.1.2/ Cryptosystème par flots ...........................................................................40 5.2.2/ Algorithmes de cryptographie asymétrique ...........................................................40 5.2.2.1/ RSA .........................................................................................................40 5.2.2.1.1/ Fonctionnement du RSA............................................................41 5.2.2.1.1.1/ Génération des clés .....................................................41 5.2.2.1.1.2/ Distribution des clés....................................................41 5.2.2.1.1.3/ Le chiffrement du message .........................................41 5.2.2.1.1.4/ Le déchiffrement du message .....................................41 Conclusion :...................................................................................................................................42 Chapitre III 43 Introduction ...................................................................................................................................44 1/ Terminologie ............................................................................................................................45 2/ Algorithme ...............................................................................................................................45 3/ Généralités ................................................................................................................................46 Table des matières 4/ Principales familles ..................................................................................................................47 5/ Programmation évolutionnaire .................................................................................................47 6/ Algorithmes génétiques ............................................................................................................47 6.1/ Définition et origine ..................................................................................................48 6.2/ Corps d’un algorithme génétique ..............................................................................49 6.2.1/ Codage ........................................................................................................50 6.2.2/ Construction de la population initiale .........................................................51 6.2.3/ Evaluation des individus .............................................................................51 6.2.4/ Sélection .....................................................................................................52 6.2.4.1/ Sélection de la roulette (Roulette Wheel Sélection) ....................52 6.2.4.2/ Sélection par rang de classement .................................................53 6.2.4.3/ Sélection par tournoi ....................................................................53 6.2.4.4/ Sélection par Elitisme ..................................................................53 6.2.5/ Operateurs génétiques .................................................................................54 6.2.5.1/ Opérateur de croisement ..............................................................54 6.2.5.2/ Opérateur de mutation .................................................................55 6.2.6/ Critère d’arrêt .............................................................................................55 6.2.7/ Convergence ...............................................................................................55 Conclusion 56 Chapitre IV : Implémentation et expérimentation…………………………………....……….…57 Introduction ...................................................................................................................................58 1. Langage utilisé : ........................................................................................................................58 1.1 Les avantages de JAVA : ............................................................................................58 1.2 Les caractéristiques de JAVA : .............................................................................. 59 2. Implémentation :....................................................................................................................59 2.1/ Création de la population initiale : C’est une population de base générée.................59 2.2/ Evaluation : C’est une étape de comparaison des individus, donc elle permettra......60 Table des matières 2.3/ Sélection ....................................................................................................................60 2.4/ Application des opérateurs génétiques:......................................................................60 2.5/ Critère d’arrêt : Peut être arbitraire par le nombre d’itération ou par la meilleure ....61 3. Description de l’application : ................................................................................................61 4. Expérimentation des résultats:...............................................................................................65 Conclusion.................................................................................................................................71 Listes des Figures FIG 1.1 : Le principe de pare-feu …………………………………………………………….10 FIG 2.2 : Cryptosystème Symétrique…………………………………………………………16 FIG 2.3 : Cryptosystème Asymétrique……………………………………………………….17 FIG 2.4 : Cryptosystème Hybride ……………………………………………………………18 FIG 2.5 : Technique du Scytale………………………………………………………………18 FIG 2.6: Table de Vigenère…………………………………………………………………...23 FIG 2.7 : La machine ENIGMA de Base…………………………………………………….29 FIG 2.8 : Exemple de Boite de Substitution et de Permutation……………………………...31 FIG 2.9 : Structure de Fiestel……………………………………………………………...…31 FIG 2. 10: Schéma du D.E.S…………………………………………………………………36 FIG 2.11 : Les états du message AES………………………………………………………...38 FIG 2.12 : Les états de la clé AES……………………………………………………………38 FIG 2.13: Shift Row de AES…………………………………………………………………39 FIG 2.14 : Mix Colum du AES………………………………………………………………39 Figure 3.1 : Un algorithme génétique………………………………………………………...49 Figure 3.2 : Croisement '1-point'……………………………………………………………...54 Figure 3.3 : Croisement ‘2-points’……………………………………………………………55 Fig 4.1: L’Onglet chiffrement « Chiffrement de Vignère »………………………………….62 Fig 4.2: L’Onglet Traitement avec AG « L’utilisation des AG pour le déchiffrement »…….63 Fig 4.3: L’Onglet Traitement avec AG « L’utilisation des AG pour le déchiffrement »……64 Listes des Figures Fig 4.4: L’Onglet Résultat optimals «Affichage des texte décrypter optimals au texte claire»…………………………………………………………………………………………65 Fig 4.5: Représentation graphique des résultats du tableau 4.1………………………………66 Fig 4.6: Représentation graphique des résultats du tableau 4.2………………………………67 Fig 4.7: Représentation graphique des résultats du tableau 4.3………………………………68 Fig 4.8: Représentation graphique des résultats du tableau 4.4………………………………70 Fig 4.9: Représentation graphique des résultats du tableau 4.5………………………………71 Liste des Tableaux TAB 2.1 : Tableau du chiffre Playfair.……………. ……………………………………….20 TAB 2.2 : Exemple du On Time Pad………………………………………………………..27 TAB 2.3 : Permutation des bits d’un bloc dans le D.E.S……………………………………32 TAB 2.4 : Bloc scindé dans D.E.S…………………………………………………………..32 TAB 2.5 : Fonction d’expansion……………………………………………………………..33 TAB 2.6 : Première boite de substitution du D.E.S…………………………………………..33 TAB 2.7: Table de permutation D.E.S………………………………………………………..34 TAB 2.8 : Table de transposition finale du D.E.S…………………………………………...34 TAB 2.9 : Matrice de réduction de la clé……………………………………………………35 TAB 2.10: Permutation pour l’algorithme de cadencement des clés dans le D.E.S…………35 TAB 2.11 : Rotation de l’algorithme de cadencement des clés du D.E.S……………………35 TAB 2.12 : Permutation compressive finale de Ki…………………………………………...36 TAB 2.13 : Tableau récapitulatif du nombre de rondes AES………………………………...40 TAB 4.1: Nombre de texte selectionés lorsque nombre d’itération égale à 100……………..66 TAB 4.2: Nombre de texte selectionés lorsque nombre d’itération égale à 200……………..67 TAB 4.3: Nombre de texte selectionés lorsque nombre d’itération égale à 300……………..68 TAB 4.4: Nombre de texte selectionés lorsque nombre d’itération égale à 400…………..…69 TAB 4.5: Nombre de texte selectionés lorsque nombre d’itération égale à 500………..……70 Introduction générale 1 La cryptologie, « science du secret » est l’une des sciences les plus antiques (plus de 3000 ans). Elle a été réservée pendant longtemps, aux milieux diplomatiques et militaires. Grace au développement de la société de l’information et l’évolution des réseaux de communications sa démocratisation s’est installée et elle s’est imposée dans tous les domaines. De nouvelles exigences se sont alors apparues : assurer la confidentialité des messages ne suffit plus, il faut également assurer leur intégrité et leur authenticité. Dans la cryptologie, on distingue la cryptographie et la cryptanalyse. La première définit et étudié les systèmes utilisés, alors que la seconde cherche à valider ou a casser ces systèmes. Depuis des siècles, de nombreux mécanismes ont été inventés. Nous ne remontons qu'à la fin du XVIe siècle pour étudier le chiffrement de Vigenère, qui est un système de chiffrement polyalphabétique sur les textes, c'est un chiffrement par substitution, mais une même lettre du texte clair peut, suivant sa position dans celui-ci, être remplacée par des lettres différentes, contrairement à un système de chiffrement monoalphabétique comme le chiffre de César (une extension du chiffrement de César). Cependant, bien que le système de chiffrement de Vigenère semble a priori robuste, une clé de 20 caractères présente 2x1026 = 294 possibilités, ce qui nécessiterait plus d'un million d'années pour toutes les essayer sur un parc d'un million de machines. Une première méthode d'attaque (ou cryptanalyse) a été proposée près de 3 siècles plus tard, indépendamment, par Babbage et Kasiski. Dans notre travail, pour casser ce système de chiffrement, nous avons opte pour l’utilisation des algorithmes évolutionnistes (AE). Pourquoi les algorithmes évolutionnistes ? Les AE ont connu un grand succès dans la résolution des problèmes d’optimisation et notamment les combinatoires qui sont en général NP-complets ou NP-difficiles. Introduction générale 2 Etant donné que nous avons pu ramener notre problème de uploads/Science et Technologie/ fezza-mehdi-master-ii.pdf