Remerciez-le!

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

Sécurité informatique Université Kasdi Merbah Ouargla Département Mathématique

Sécurité informatique Université Kasdi Merbah Ouargla Département Mathématique et informatique Crypto I : Cryptosystèmes et science de la cryptologie Master 1 ASR Février 2016 M1-ASR 1 Sec 1 Cryptosystèmes et science de la cryptologie 1. Définitions et terminologie – Historique – Cryptosystème – Principe de la cryptographie, cryptanalyse 2. Cryptographie classique – Chiffrements mono-alphabétiques – Chiffrements poly-alphabétiques 3. cryptanalyse de la cryptographie classique – Confusion et diffusion – Méthode de cryptanalyse de base – Cryptanalyse et analyse des fréquences – Sûreté d'un chiffrement 4. Résumé : cryptographie classique – Algorithme de chiffrement – Concepts généraux – Algorithmes "classiques" mono-alphabétiques – Algorithme de Vigenère et OTP (poly-alphabétique) – Enigma (En TP si possible) M1-ASR 2 Sec 1 1- Définitions et terminologie I M1-ASR 3 Sec 1 Un peu de grec classique… Kryptos = "caché", "secret" Graphos = écriture => Cryptographie => Cryptanalyse Logos = "savoir" => Cryptologie Stéganos = "couvert", "étanche" => Stéganographie Un peu d'américain… Alice Bob Eve (Charlie) Encrypt and Decrypt Un peu de français !!! Chiffrer et déchiffrer Coder et décoder Crypter et décrypter (!) Irène !!! (l'ingénieure) Un peu de math… 1- Définitions et terminologie II M1-ASR 4 Sec 1 Vocabulaire : Cryptosystème : Un système de chiffrement/déchiffrement Cryptographie : Art de concevoir des cryptosystèmes Cryptanalyse : Art de casser les cryptosystèmes Cryptologie : Science qui étudie les deux arts précédents Cryptologie : science du secret Historique Les trois ères de la cryptographie « Classique » • Jusqu’au masque jetable (One Time Pad) « Moderne » • Crypto électro-mécanique (voir applet Enigma) • Guerre froide … • Crypto électronique et informatique - DES « Âge d’or » • Chiffrement à clé publique et gestion de certificats • Cryptologie et autres tâches cryptographiques • Internet et enjeux commerciaux M1-ASR 5 Sec 1 Cryptosystème I M1-ASR 6 Sec 1 Eve Cryptosystème II M1-ASR 7 Sec 1ique Cryptosystème III M1-ASR 8 Sec 1e Principe de la cryptographie, cryptanalyse M1-ASR 9 Sec 1 • Considérations pratiques les fonctions ek et dk doivent pouvoir se calculer efficacement un opposant observant les messages chiffrés y ne peut déterminer k ou x cryptanalyse : rechercher k à partir de y. Donnera aussi x • Algorithme public, clé cachée : principe de Kerckhoffs (1883) la sécurité d'un cryptosystème ne repose que sur le secret de la clé. autres paramètres connus (e et d) exprimé aussi par Shannon : l'adversaire connaît le système chiffres civils suivent le principe de Kerckhoffs. Militaires utilisent des systèmes secrets. NB : l’algorithme de cryptage A5/1 des mobiles GSM non divulgué au début (1987), divulgué en 1994. • Le nombre de clés possibles doit être grand. • Pourquoi de tels principes pour la sécurité informatique ? Résumé des outils I M1-ASR 10 Sec 1 • arithmétique modulo (ex : caractères modulo 26, bits modulo 2) • chiffrement eK, déchiffrement dK à clé secrète K • chiffrement public eKpub , déchiffrement privé dKpriv • signature privée sigKpriv, vérification publique verKpub • fonction de hachage h publique, empreinte privée sigKpriv(h(x)) (signature numérique) 2- Cryptographie classique : Chiffrements mono- alphabétiques I • Quelques grands noms : Al-Kindi (801-873), Alberti (1404-1472), Vigenère (1523-1596), Porta (1535- 1615), Babbage (1792-1872), Kerckhoffs (1835- 1903), Turing (1912-1954) • Chiffre de substitution : remplacer les lettres ou les mots par d'autres symboles • On appelle chiffrement mono-alphabétique ou substitution simple, un chiffre où chaque lettre est remplacée par une autre lettre ou symbole. M1-ASR 11 Sec 1ue Chiffrements mono-alphabétiques II • Chiffre de César : Si on code A − Z dans , alors y = x + 3 mod 26 et x = y − 3 mod 26. M1-ASR 12 Sec 1 Vérifier (1) ? Chiffrements mono-alphabétiques III M1-ASR 13 Sec 1 Exercices : 1. Quelle est l'espace des clés du chiffre par décalage ? 2. Quel est le texte clair de TMKBM CZXIQ AQJTM MBJCK WTQYCM? Chiffrements mono-alphabétiques III • Chiffrement par substitution M1-ASR 14 Sec 1 Algorithme de substitution On prend un texte en clair et, pour chacune des lettres du texte, on utilise la lettre comme index dans une table de substitution () pour trouver l’équivalent chiffré La table de substitution représente la clé Chiffrements mono-alphabétiques IV • Exemple : – « HELLOWORLD » devient : M1-ASR 15 Sec 1 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z h e v a m t s i c f n u o r b g q w j y d l x k z p « imuubxbwua » Exercice Quelle est l'espace des clés de ce chiffrement ? Est-ce qu'une recherche exhaustive est envisageable ?  Chiffrements mono-alphabétiques V • Un autre exemple est le chiffrement affine eK(x) = ax + b mod 26, pour des clés k = (a, b) avec pgcd(a, 26) = 1. • Montrez que résoudre ax + b= y(mod 26) est équivalent à résoudre ax= y(mod 26) • Supposez pgcd(a, 26) = d > 1 et montrez que ax= 0(mod 26) a au moins deux solutions. eK peut-il être alors injectif ? • Supposez pgcd(a, 26) = 1 et supposez x1, x2 tq ax1= ax2(mod 26). • En déduire 26 divise (x1 − x2), ce qui montre que x1= x2(mod 26). ek est-il alors injectif ? • En déduire que l'équation ax= y(mod 26) admet une solution unique. • Le chiffrement affine est bien un cryptosystème. • Si a−1 est l'inverse de a, en déduire que dK(y)= a−1(y − b)(mod 26) Exercices : • Montrer que K = (7, 3) induit un chiffrement affine dans Z26. Quelle est sa fonction de déchiffrement ? Combien y a-t-il de clés possibles ? M1-ASR 16 Sec 1 Chiffrements mono-alphabétiques VI Algorithme de substitution Un exemple de texte chiffré en utilisant : Il est difficile de faire la correspondance entre le texte original et le texte chiffré sans connaître la table de substitution (la clé) Sans le texte en clair, il serait aussi difficile d’inférer à partir du texte chiffré, il faut avoir un « grand » (au moins une occurrence de 25 lettres sur 26) nombre de texte en clair pour reconstruire la clé L’algorithme classique de substitution possède donc des propriétés raisonnables de confusion M1-ASR 17 Sec 1 I L E T A I T U N E F O I S L H I S T O I R E D U N P E T I T C H A P E R O N R O U G E c u m y h c y d r m t b c j u i c j y b c wm a d r g m y c y v i h g m w b r w b d s m Chiffrements poly-alphabétiques I Un chiffrement polyalphabétique peut remplacer une lettre par une autre lettre qui n'est pas toujours la même. Cryptanalyse plus difficile. M1-ASR 18 Sec 1 Le message clair est découpé en bloc de m lettres. Les clés comme les messages sont traduits de l'alphabet a-z vers les nombres 0-25. Vérifier (1) ? Chiffrements poly-alphabétiques II • chiffrement par permutation (mélange de m lettres consécutives par une permutation/clé) : Transposition • chiffrement de Hill (multiplication par une matrice m × m inversible dans ) (voir exercice dans TD) • Masque jetable (One Time Pad) M1-ASR 19 Sec 1 Chiffrements poly-alphabétiques III : Algorithme de transposition (bit shifting) M1-ASR 20 Sec 1 • On prend un texte en clair et on permute la position des lettres (ou des bits dans le cas moderne) entre elles en fonction d’une « clé » • Dans l’antiquité on utilisait un bâton autour duquel on enroulait une lanière de cuir (déguisée en ceinture) où était écrit le texte • Exemple : – Avec un « bâton » qui a une épaisseur de deux lettres, « HELLOWORLD » devient « hloolelwrd » h l o o l e l w r d Chiffrements poly-alphabétiques IV : Algorithme de transposition (bit shifting) M1-ASR 21 Sec 1ue Chiffrons ce texte avec un « bâton » de taille 6 Ici, il est « facile » d’inférer le texte original à partir du texte chiffré On peut « facilement » retrouver la clé à partir du texte chiffré La confusion est donc mauvaise Par contre, la disparition d’une lettre entraîne la modification de tout le texte chiffré qui suit I L E T A I T U N E F O I S L H I S T O I R E D U N P E T I T C H A P E R O N R O U G E e n l i p h n i t e h r e a r l a f i e t p o i o s d i e u t i t u t r g u s o n c o e e n l i p h n i t e h r e uploads/Management/ crypto-1.pdf