1 Cryptographie classique Cryptographie classique - 2 Cryptologie Stéganographi

1 Cryptographie classique Cryptographie classique - 2 Cryptologie Stéganographie (messages cachés) Cryptographie (Messages chiffrés) Substitution Transformation Transposition Chiffrement (changer l’ordre des lettres) Code (remplacer des mots) Chiffrement par substitution (remplacer des lettres) Cryptographie classique 3 Cryptographie classique Chiffrement monoalphabétique Dans les substitutions simples (qu'on appelle aussi monoalphabétiques), chaque lettre est remplacée par une autre lettre ou un autre symbole. Dans cette catégorie, on peut citer le chiffre de César, les alphabets désordonnés ou encore le chiffre affine. Le message que déchiffre Calvin sur la page suivante est aussi un exemple de substitution simple. Toutes les substitutions simples sont vulnérables à une analyse des fréquences d'apparition des lettres. Cryptographie classique - 4 Chiffrements par substitution Cryptographie classique - 5 Chiffrement de César „ Principe : décaler les lettres de l’alphabet. ‰ Chiffrement : C = E(p) = (p + k) mod 26 ‰ Déchiffrement : p = D(C) = (C - k) mod 26 „ Si algorithme connu →cryptanalyse par force brute très simple →25 clés possibles ! „ Pourquoi force brute ? ‰ Algorithme connu ‰ 25 clés à essayer ‰ Langage initial connu →c’est la longueur de la clé qui rend cette attaque inutilisable La plupart du temps, les algorithmes et la langue utilisés sont connu → c’est la longueur de la clé qui rend cette attaque inutilisable De plus, •une compression ou un langage inconnu rendent l’attaque plus difficile •une permutation des 26 caractères alphabétiques →26! clés (ou > 4*1026 clés). (voir plus loin) L’attaque par force brute est alors éliminée. Cryptographie classique - 6 Analyse de fréquence „ Si la langue de départ et la technique de chiffrement sont connus →exploiter les régularités du langage. „ Analyse de la fréquence d’une lettre „ Cette technique ne fonctionne bien que si le message chiffré est suffisamment long pour avoir des moyennes significatives. Cryptographie classique - 7 Analyse de fréquence „ QTJYCOQTQYVJYIOUOMPEGOJQIOYIUPQPFN S E S S E E E ES YOUOMGOBJOQSOYJGJQYEWAFOWOYYPHOSTUO SE E E E ES S E SS E E „ Fréquences : O = 14, Y = 9, Q = 7, J = 6… „ Fréquences en français : E , A, S, I, T, … „ Dans notre cas : O ?= E, Y ?= A ou Y ?= S, … „ NOUSVENONSJUSTEDEFAIREUNTESTDANALY SEDEFREQUENCESURUNSIMPLEMESSAGECODE Cryptographie classique - 8 Cryptographie classique - 9 Le chiffre affine „ L'idée est d'utiliser comme fonction de chiffrage une fonction affine du type y = (ax + b) mod 26, où a et b sont des constantes, et où x et y sont des nombres correspondant aux lettres de l'alphabet (A=0,B=1,…) „ On peut remarquer que si a=1, alors on retrouve le chiffre de César et b est le décalage. „ On remarquera aussi que si b=0, alors "a" est toujours chiffré "A". Cryptographie classique - 10 Le chiffre affine - fonctionnement „ Clé : Clé = (k1, k2) k1,k2 ∈[0,25] gcd(k1,26)=1 „ Transformation de chiffrement : ci = f(mi) = k1*mi + k2 mod 26 „ Transformation de déchiffrement : mi = f-1(ci) = k1 -1*(ci – k2) mod 26 „ Nombres de clés possibles : 12*26 = 312 Cryptographie classique - 11 Exemple d’utilisation „ Clé = (k1, k2) = (3, 11) „ Transformation de chiffrement : ci = f(mi) = 3 * mi + 11 mod 26 „ Transformation de déchiffrement : k1 -1 = 3-1 mod 26 = 9 car 3 * 9 mod 26 = 1 mi = f-1(ci) = 9 * (ci – 11) mod 26 „ Exemple : ‰ NSA →13 – 18 – 0 →24 – 13 – 11 →YNL Cryptographie classique - 12 Le chiffre affine - cryptanalyse 1. Établir la fréquence relative de chaque lettre du texte chiffré → analyse de fréquence GHUYI DEGRS YTGOR RYOVG EOHGA HKEIA AOTDG SBINN TGKGR HENNI RGSGH HGNYI ASI G : 10 H : 6 anglais ? Cryptographie classique - 13 Le chiffre affine – cryptanalyse(2) 2. Sur base de l’analyse de fréquence, dériver les équations correspondantes „ Hypothèse : E et T sont les lettres les plus fréquentes en anglais „ Equations correspondantes : E →G f(E) = G T →H f(T) = H 4 →6 f(4) = 6 19 →7 f(19) = 7 Cryptographie classique - 14 Le chiffre affine – cryptanalyse(3) 3. Résoudre les équations pour k1 et k2 inconnus f(4) = 6 f(19) = 7 4*k1 + k2 ≡6 (mod 26) 19*k1 + k2 ≡7 (mod 26) 15 k1 ≡1 mod 26 K1 = 7 Cryptographie classique - 15 Contre-mesures „ Utiliser des homophones ‰ remplacer une lettre non pas par un symbole unique, mais par un symbole choisi au hasard parmi plusieurs. ‰ Dans sa version la plus sophistiquée, on choisira un nombre des symboles proportionnel à la fréquence d'apparition de la lettre. →Renversement des fréquences. „ faire disparaître complètement les indications fournies par la fréquence „ Contrecarré par les digrammes et les trigrammes Cryptographie classique - 16 Digrammes et trigrammes 17 Cryptographie classique Chiffrements polygraphiques Polygrammique : Se dit d'un chiffre où un groupe de n lettres est codé par un groupe de n symboles. Dans les substitutions polygrammiques (aussi appelées polygraphiques), les lettres ne sont pas chiffrées séparément, mais par groupes de plusieurs lettres (deux ou trois généralement). Exemples: le chiffre de Playfair (avec n = 2), le chiffre de Hill et certains systèmes modernes comme le RSA Cryptographie classique - 18 Le chiffrement de Playfair (1854) „ Chiffrement à lettre multiples (digramme) „ On dispose les 25 lettres de l'alphabet (W exclu car inutile, on utilise V à la place) dans une grille 5x5, ce qui donne la clef. La variante anglaise consiste à garder le W et à fusionner I et J. „ 4 règles à appliquer „ Déchiffrement : appliquer les règles dans l’autre sens. Cryptographie classique - 19 Playfair - règles ‰ Si les 2 lettres sont : 1. sur des « coins » →lettres chiffrées = les 2 autres coins. 2. sont sur la même ligne →prendre les deux lettres qui les suivent immédiatement à leur droite 3. la même colonne →prendre les deux lettres qui les suivent immédiatement en dessous 4. Identiques →insérer une nulle (usuellement le X) entre les deux pour éliminer ce doublon. Pour former les grilles de chiffrement, on utilise un mot-clef secret pour créer un alphabet désordonné avec lequel on remplit la grille ligne par ligne. Les autres lettres de l’alphabet sont alors ajoutées dans l’ordre dans la grille pour la compléter Cryptographie classique - 20 Playfair – cryptanalyse et critique „ Si le cryptogramme est assez long →analyse de la fréquence des digrammes. Il faut ensuite essayer de reconstituer la grille de chiffrement. „ Avantages : ‰ 26 lettres →26*26 = 676 digrammes ‰ Analyse de fréquence difficile ‰ Utilisé pendant les 2 guerres mondiales par les alliés „ Inconvénient : ‰ Facile à casser car il conserve la structure du texte clair Cryptographie classique - 21 Chiffrement de Hill (1929) „ Chiffrement ‰ Les lettres sont d'abord remplacées par leur rang dans l'alphabet. Les lettres Pk et Pk+1 →Ck et Ck+1 ‰ Chaque digramme clair (P1 et P2) sera chiffré (C1 et C2) selon : Matrice de chiffrement On ne peut pas prendre n'importe quoi comme matrice de chiffrement. Ses composantes doivent tout d'abord être des nombres entiers positifs. Il faut aussi qu'elle ait une matrice inverse dans Z26. Le chiffre affine peut être vu comme la version unidimensionnelle du chiffrement de Hill. Cryptographie classique - 22 Exemple de chiffrement „ Alice prend comme clef de cryptage la matrice pour chiffrer le message « je vous aime » „ Après avoir remplacé les lettres par leur rang dans l'alphabet (a=1, b=2, etc.), elle obtiendra „ Elle fera de même avec les 3e et 4e lettres, 5e et 6e, etc. Elle obtiendra finalement Cryptographie classique - 23 Chiffre de Hill „ Déchiffrement ‰ Pour déchiffrer, le principe est le même que pour le chiffrement: on prend les lettres deux par deux, puis on les multiplie par une matrice ‰ Cette matrice doit être l'inverse de matrice de chiffrement (modulo 26). Ordinairement cet inverse est Cryptographie classique - 24 Exemple de déchiffrement „ Pour déchiffrer le message d'Alice, Bob doit calculer : „ Comme gcd(43,26) = 1, (43)-1 existe dans Z26 et (43 )-1 = 23 . Bob a la matrice de déchiffrement : Cryptographie classique - 25 Exemple de déchiffrement „ Bob prend donc cette matrice pour déchiffrer le message "FGXGE DSPGV". Après avoir remplacé les lettres par leur rang dans l'alphabet (A=1, B=2, etc.), il obtiendra: „ Il fera de même avec les 3e et 4e lettres, 5e et 6e, etc. Il obtiendra finalement: 26 Cryptographie classique Substitutions polyalphabétique Les substitutions polyalphabétiques (aussi appelées à double clef ou à alphabets multiples), utilisent plusieurs "alphabets", ce qui signifie qu'une même lettre peut être remplacée par plusieurs symboles. L'exemple le plus fameux de chiffre polyalphabétique est sans doute le chiffre de Vigenère, qui résista aux cryptanalystes pendant trois siècles. Cryptographie classique - 27 Chiffre de Vigenère (1568) „ uploads/Litterature/ 02-cryptographie-classique.pdf

  • 16
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager