Remerciez-le!

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

1 M&K Hdhili Cryptographie: théorie et pratique Mohamed Houcine HDHILI med_elhd

1 M&K Hdhili Cryptographie: théorie et pratique Mohamed Houcine HDHILI med_elhdhili@yahoo.es 2 M&K Hdhili Introduction à la cryptographie …... ... 3 M&K Hdhili Cryptographie: objectifs Objectif principal: Assurer la sécurité des communications sur un canal non sécurisé Sécurité des communications? Confidentialité, Integrité, authenticité, non repudiation Canal non sécurisé? Attaques passives: écouter des communications Attaques actives: contrôler la communication (Man in the middle) Injection, Suppression, modification 4 M&K Hdhili Terminologie Cryptologie= cryptographie+cryptanalyse Science (branche des mathématiques) des communications secrètes. Composée de deux domaines d'études complémentaires : Cryptographie : conception d'algorithmes/protocoles Cryptanalyse : casser des algorithmes/protocoles 5 M&K Hdhili Terminologie Cryptographie (cryptography) = Chiffrement=Encryptage Ensemble des méthodes et techniques qui permettent de transformer un message afin de le rendre incompréhensible pour quiconque qui n'est pas doté du moyen de le déchiffrer. On parle d'encrypter (chiffrer) un message, Le code résultant s'appelle cryptogramme. L'action inverse s'appelle décryptage (déchiffrement). Texte clair Texte chiffré ou Texte crypté ou Cryptogramme Cryptographie Encryptage ou Chiffrement Texte clair Décryptage ou Déchiffrement 6 M&K Hdhili Terminologie Cryptanalyse (cryptanalysis) Art de révéler les messages qui ont fait l'objet d'un encryptage. Lorsqu'on réussie, au moins une fois, à déchiffrer un cryptogramme, on dit que l'algorithme qui a servi à l’encrypter a été cassé. Texte clair Texte chiffré ou Texte crypté ou Cryptogramme Cryptographie Encryptage ou Chiffrement Texte clair Décryptage ou Déchiffrement en disposant seulement du cryptogramme Cryptanalyse 7 M&K Hdhili Terminologie Clé : Information qui sera utilisée pour encrypter et / ou décrypter un message. On peut cependant concevoir un algorithme qui n'utilise pas de clé, dans ce cas c'est lui-même qui constitue le secret et son principe représente la clé Crypto système: Ensemble composé d'un algorithme, de tous les textes en clair (espace des textes clairs), de tous textes chiffrés (espace des textes chiffrés) de toutes les clés possibles (espace des clés). 8 M&K Hdhili Chiffrement Chiffrement symétrique C=EncK (M) Canal non sécurisé C Canal sécurisé et authentifié Clé = K M=Dec K(C) A B xxx xxx xx Message original ----- ------ ------ Message chiffré Cryptage  Clé secrète xxx xxx xx Message chiffré Décryptage  Clé secrète Message original ----- ------ ------ Réseau Message M 9 M&K Hdhili Chiffrement par décalage (shift cipher) Exemple: espace des clés [0..25] Chiffrement en utilisant K Chaque lettre du message clair est remplacé par la kieme lettre en partant de la lettre à remplacer (shift right) Déchiffrement: shift left Cryptanalyse: Il est facile de déterminer K (brute force attack: tester les 26 possibilités) Exemple: chiffrement de cesar (K=3) 10 M&K Hdhili Chiffrement mono alphabétique par substitution Espace des clés: Exemple: toutes les permutations de Σ={A,B,.....Z} Chiffrement en utilisant une clé K Chaque lettre X du message clair est remplacé par la lettre K(X) Déchifrement en utilisant la clé K Chaque lettre Y du message chiffré est remplacé par K-1(Y) Exemple: ESSALAMO ALEIKOM ==> WNNSYSPF SYEVQFP 11 M&K Hdhili Chiffrement mono alphabétique par substitution: Cryptanalyse La recherche exhaustive est difficille: Espace des clés= 26! Cryptanalyse par analyse fréquentielle: facile Découverte par les arabes (Al KINDI): Idée: Chaque langage possède certaines caractéristiques: fréquences des lettres, de groupes de 2 lettres.... ==> insécurité du chiffrement par substitution Exemple: fréquences des lettres en Français 12 M&K Hdhili Défense contre l'analyse fréquentielle Utiliser des blocs plus long (64 ou 128 bits) pour la substitution au lieu de faire la substitution lettre par lettre ==> exemple de chiffrement par bloc: DES, AES... Utiliser différents substitution Faire correspondre à chaque caractère du texte en clair un ensemble d'équivalents possibles appelé homophones (généralement des chiffres) ==> analyse fréquentielle difficille mais possible Chiffrement par substitution polyalphabétique ... 13 M&K Hdhili Evolution de la cryptographie classique ... 14 M&K Hdhili Chiffrement par substitution polyalphabétique Faiblesse du chiffrement monoalhabétique Chaque lettre du message chiffré correpond à une seule lettre du message clair ==> possibilité de l'analyse fréquentielle Solution: substitution polyalphabétique Utiliser plusieurs alphabets de chiffrement et les utiliser lors du chiffrement de différentes lettres ==> les fréquences des lettres du cryptogramme sont similaires Exemple: chiffrement de viginère (1586) 15 M&K Hdhili Chiffrement de viginère Traiter les lettres comme nombres: {A=0, B=1,...Z=25} Notation Zn={0, 1, 2,...(n-1)} Définition: Soit : P: plaintext, C: Ciphertext m un entier >0, P=C=(Z26)n et K={k1, k2, ..km} Encryption: ek(p1, p2... pm) = (p1+k1, p2+k2...pm+km) (mod 26) Decryption: dk(c1, c2... cm) = (c1- k1, c2- k2...cm - km) (mod 26) Exemple Plaintext: ATTACKATDAWN Key: LEMONLEMONLE (la clé est re-écrite) Ciphertext: LXFOPVEFRNHR 16 M&K Hdhili Tableau de viginère Clés ki Lettres du message 17 M&K Hdhili Chiffrement de viginère: sécurité et cryptanalyse Sécurité: La fréquence d'apparition des lettres est masqué ==> complique l'analyse fréquentielle Un chifrement viginère = collection de plusieurs chiffrement par décalage (plusieurs ie la longueur de la clé) Cryptanalyse: Quoi faire? Trouver la longueur de la clé Kasisky test Index of coincidence (Freidman) Diviser le message en plusieurs substitutions simples à résoudre Comment? 18 M&K Hdhili Kasisky test (1863) Constat: Deux segments identiques du texte clair donnent le même cryptogramme s'ils apparaissent dans le texte à la distance ∆ (∆=0 mod m). m est la longueur du mot clé. Algorithm Rechercher les paires de segments identiques de longueur au minimum 3 Enregistrer les distances ∆1, ∆2,... M divise le PGCD(∆1, ∆2,...). 19 M&K Hdhili Wakeupalicedearsaidh ersisterwhywhatalong sleepyouvehadohiveha dsuchacuriousdREAmsAI DaliceandshetolDHER SISTERaswellasshecou Ldrememberthemallthe Sestrangeadventureso Fhersthatyouhavejust BeenREAdingaboutandw HenSHEhadfiniSHEDHER SISTERkissEDHerandsA Iditwasacuriousdream dearcertainlybutnowr unintoyourteaitsgettinglate Hegmmaehquphaijdeelz pvoqkeinezjadillpkvy dpamhjsqdwsezwztzaps owqkzlgqzazyolJPEiaS THwtaniwvvdlabgwHDMJ DMOBWCeoewwpwaksiywm whnmepqxmjelauswpppw diobjlrcmsozavlfvaag qlazkelwbqzydinpnqal miavJPEzqfrexwmeejlo sijAZPlwlxtreAZPHDMJ DMOBWCoeakPHDmjlrzaS THebolwwkmcmkckovaie oiwzupvpiaypujmerkej frevlzckcjeiwqldkabltrctsei Test de KASISKI: exemple Distances observées: JPE(110), STH(160), HDMJDMOBWC(120), PHD(15), AZP(10) ==> longueur de la clé a une forte probabilité d'être PGCD(110,160,120,15,10)=5 20 M&K Hdhili One Time PAD and perfect secrecy …... ... 21 M&K Hdhili One Time PAD (Verman 1920) Résoud la faiblesse du chiffrement de viginère Solution: taille de la clé >= taille du message Une clé est utilisé pour chiffrer un seul message (One Time) Soit l'alphabet Zm={0, 1, 2,...(m-1)} Espace des clés=espace des textes clair=espace des textes chiffrés= (Zm)n P={p1, p2, ..pn}, K={k1, k2, ..kn} et C={c1, c2, ..cn} Encryption: ek(p1, p2... pn) = (p1+k1, p2+k2...pn+kn) (mod m) Decryption: dk(c1, c2... cn) = (c1- k1, c2- k2...cn - kn) (mod m) One Time PAD has perfect secrecy (proved) Le texte chiffré ne donne aucune idée sur le texte clair 22 M&K Hdhili Perfect secrecy Le texte chiffré ne doit donner aucune idée sur le texte en clair  Les deux variables aléatoires P (plaintext) and C (ciphertext) sont indépendantes Définition: (GEN, ENC, DEC) sur un espace S de messages est parfaitement secret si  distribution de probabilité sur S  message msg sur S  texte chiffré c∈ C avec Pr[C=c] > 0, on a Pr [M=msg | C=c] = Pr [M = msg]. Ou : Pr [M=msg et C=c] = Pr [M = msg].Pr [C = c] Ou : Pr [C=c | M=msg] = Pr [C = c]. Ou : Pr [C=c | M=msg1 ] = Pr [C=c | M=msg2 ]  msg1, msg2 sur S 23 M&K Hdhili Usage de One Time PAD Taille de la clé >= taille du message La clé est utilisé une seule fois (One Time)  il est plus adéquat d'échanger le message sur un canal sécurisé que d'échanger la clé pour chiffrer le message OTP reste utile La distribution des clés peut se faire au préalable (avant d'avoir des messages à envoyer) 24 M&K Hdhili Stream ciphers …... ... 25 M&K Hdhili Stream ciphers Dans One Time PAD: Taille de la clé >= taille du message Clé= chaine aléatoire Stream ciphers Idée: remplacer “aléatoire” par “pseudo aléatoire” Utiliser un PRNG (Pseudo Random Number Generator) G: {0,1}s--> {0,1}n avec n>>s Étendre une clé aléatoire K de petite taille (exemple 128bits) pour avoir une clé pseudo aléatoire de grande taille (exemple 106 bits) Chiffrement: EK(M)=MG(K) Exemple: RC4 26 M&K Hdhili Message Authentication Code (MAC) …... ... 27 M&K Hdhili Intégrité des données et authentification de la source Integrité: Les données doivent arriver au destinataire dans leur forme originale envoyé par la source Authentification de la source Les données proviennent d'une source authentique MAC La source et le destinataire partage une clé K qui est utilié pour l'authentification des messages Key generation: k=GEN (1n) Tag generation: t=MACk(m) Verification algorithm: b=verifyk(m,t) ( b=1 sig verification valide) 28 M&K Hdhili CBC MAC (fixed length MAC) Soit une fonction pseudo aléatoire PRF, et L(n) une fonction longueur PRF F:{0,1}nx{0,1}n{0,1}* CBC MAC est: macK(m), m est de longueur L(n).n Diviser m en m1, m2, ….mL chacune de taille n t0=0n Pour i de 1 à L, ti=FK(ti-1mi) Output: tL Verify (K, m, t)? ==> vérifier si macK(m)=tL Proved to be secure 29 M&K Hdhili Hash functions Une fonction de hashage génère à partir d'un message de longueur quelconque un résumé de taille fixe fonction de hashage cryptographique h: XY est: preimage resistant (one way): étant donné yY, il est impossible de trouver xX tel que h(x)=y 2nd preimage resistant (weak collision resistant): étant donné xX, il est impossible de trouver x'X tel que x'x et h(x')=h(x) collision resistant (strong collision resistant): Il est impossible de trouver deux valeurs distinctes x uploads/Management/ cryptograph-i-e-the-or-i-eet-prati-que.pdf