OUAP-4113-chifffrement-cours.pdf

Cryptographie et Sécurité des communications Partie 1: Les bases du chiffrement Khaled Hamouid & Mawloud Omar [email protected] Département IT ESIEE-Paris Université Gustave-Eiffel Année: 2024/2025  Plan du cours — Introduction...

Cryptographie et Sécurité des communications Partie 1: Les bases du chiffrement Khaled Hamouid & Mawloud Omar [email protected] Département IT ESIEE-Paris Université Gustave-Eiffel Année: 2024/2025  Plan du cours — Introduction — Chiffrement classique — Chiffrement symétrique — Chiffrement asymétrique — Initiation à la cryptographie quantique 2  Introduction 𝒎 Bob Alice Eve Alice envoie un message m à Bob sur un canal de communication non sûr 3  Scénarios typiques d’attaques Ecoute clandestine Fabrication / Alice ? Usurpation 𝒎 𝒎 Rejeu Je suis Alice 𝒎 𝒎 𝒎 𝒎′ =? 𝒎 Interception/ Modification coupure 𝒎 X 𝒎 𝒎′ 4  Scénarios typiques d’attaques J’ai reçu ton message Répudiation 𝒎 J’ai rien envoyé 5  Besoins de l’émetteur et du récepteur — Le message ne doit parvenir qu'au destinataire (confidentialité) — Le message doit parvenir au bon destinataire (authentification) — L'émetteur du message doit pouvoir être connu avec certitude (authentification) — Le message reçu doit être identique au message émis (intégrité) — Le destinataire ne peut contester la réception d'un message (non-répudiation) — L'émetteur ne peut contester l'émission du message 6 (non-répudiation)  Objectifs de la cryptographie La cryptographie est une discipline consistant à manipuler des données de telle façon que les services suivants puissent être fournis : Confidentialité -Préserver le secret d’une information -Protection de l’information lors de sa conservation, du transfert ou du calcul Intégrité -Préserver contre les modifications inapropriées -Vérifier la non altération frauduleuse Preuve (authentification et non-répudiation) fournir un moyen de preuve garantissant la véritable identité des entités ainsi que l’imputation de leurs actions. 7  Techniques de protection de données — Cryptographie: l’étude de méthodes de manipulation et de transformation de messages pour préserver leur confidentialité, intégrité et authenticité o texte en clair ® Chiffrement ® texte chiffré (cryptogramme) o texte chiffré ® Déchiffrement ® texte en clair — Stéganographie: (écriture couverte) dissimuler un message secret dans un média de couverture (image, vidéo, son, texte...) 8  Principe de la cryptographie — Un Cryptosystème est composé de : o G – un algorithme de génération de clés o E – un algorithme de chiffrement o D – un algorithme de déchiffrement 9  Principe de la cryptanalyse — Casser un système cryptographique o Déchiffrer des messages sans connaître la clé o Chiffrer des messages sans connaître la clé o Trouver la clé secrète 10  Fonctions de base Chiffrer Transformer une donnée de telle façon qu’elle devienne incompréhensible. Déchiffrer Transformer une donnée précédemment chiffrée pour reconstituer la donnée d’origine. 11  Fonctions de base Signer Créer une signature électronique unique à la donnée et à son auteur. La signature lie donc la donnée Avec une clé privée et un d’origine et son auteur. message en entrée, on obtient une signature en sortie Vérifier la signature S’assurer que la donnée d’origine ü n’a pas été modifiée et que son auteur est authentifié. Si la signature Avec la clé publique, la ü n’est pas valide, alors il ne faut pas signature et le message en faire confiance au document. entrée, on obtient un verdict OK/NOK en sortie 12  Fonctions de base Chiffrement à sens unique Hacher En utilisant une fonction de hachage, UHD783L0 créer un condensé unique et d’une longueur fixe à la donnée en input quelque soit sa taille. Difficile Fonction de hachage : H(M) = h. h est de longueur fixe et inférieure à M. h caractérise M d’une façon quasi-unique. A partir de h, il est quasi-impossible de retrouver M. Il est difficile de trouver M’ TQ H(M’) = h. 13  La cryptographie en cybersécurité — Protection de données o Algorithmes de chiffrement et de signatures électronique pour la confidentialité, authenticité et intégrité des données — Conception de protocoles et mécanismes de protection des communications en réseaux o SSH o SSL / TLS o PKI/Certificats o S/MIME, OpenPGP 14  Stéganographie — Stéganographie classique : o Dissimuler un message secret dans un autre message — Stéganographie moderne : o Trames : exploiter les champs non-utilisés. o Exécutables : déclaration des variables inutiles. o Images : exploiter les bits de poids faibles du pixel. 15  Stéganographie — Stéganographie classique : Les écrivains facétieux et jeux littéraires o Un Pamphlet de la seconde guerre mondiale adressant des louanges à Hitler 16  Stéganographie — Stéganographie moderne: Dissimuler un message secret dans une image 17  Stéganographie — Chaque pixel est représenté par 3 nombres codés sur 8 bits : o R : intensité du rouge. o G : intensité du vert. o B : intensité du bleu. 18  Stéganographie — Exemple d’image composée de deux pixels : — Très discret. — Permet de cacher des messages de tailles importantes. Exemple : pour une — image de 40x40, on aura 40x40x6 = 9600 bits (1200 caractères). — La compression fait perdre le message caché. 19  Stéganographie — Stéganalyse (Steganalysis) o Détecter la stéganographie Þ Rechercher l’information stéganograhiée — Plusieurs techniques: o À base de signature o Statistique o Machine learning — Outils: o Stegdetect o StegCracker 20  Les bases de la cryptographie chiffrement classique 21  Historique — Existe depuis l‘invention de l’écriture — Une tablette d'argile, retrouvée en Irak, et datant du XVIe siècle av. J.-C. Un potier y avait gravé sa recette secrète en supprimant des consonnes et en modifiant l'orthographe des mots. — Anciens hiéroglyphes égyptiens encodés — Les Grecs entre le Xe et VIIe siècle av. J.-C., utilisaient une technique de chiffrement par transposition 22  Chiffrement classique — Premières solutions de la cryptographie — Chiffrer des textes afin d’en empêcher la lecture par des tiers — Deux méthodes : o Par substitution o Par transposition 23  Chiffrement par substitution — Chiffrement mono-alphabétique: les occurrences d’une même lettre du texte en clair sont substituées par la même lettre du texte chiffré o César o Chiffrement par décalage o Chiffrement affine o Polybe — Chiffrement polyalphabétique: une même lettre du texte en clair peut être substituée par différentes lettres du texte chiffré o Chiffrement de playfair o Chiffrement de Hill o Chiffrement de Vigenere 24  Chiffrement de césar — Principe de Jules César: décaler les lettres de l’alphabet de trois positions — Généralisation Þ chiffrement par décalage o Chiffrement : C = E(P) = (P + k) mod(26) o Déchiffrement : P = D(C) = (C - k) mod(26) o K: nombre de décalage Þ clé de chiffrement 25  Chiffrement de césar Exemple — Déchiffrez le texte ci-dessous en utilisant le chiffrement par décalage avec la clé K=4 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 — P = PE VYI EWWSYVHMWWERXI EYXSYV HI QSM LVPEMX — D(P) = LA RUE ASSOURDISSANTE AUTOUR DE MOI HURLAIT — Approche avec un tableur 26  Chiffrement affine — Fonction affine : 𝑦 = (𝑎𝑥 + 𝑏) 𝑚𝑜𝑑 26 — Principe: o Clé : k = (k1, k2)/ k1,k2 ∈ [0,25] pgcd(k1,26)=1 o Fonction de chiffrement : — Ek(P)= k1P+ k2 mod 26 = C o Fonction de déchiffrement : — Dk(C)= k1-1 (C– k2) mod 26 = P o Nombres de clés possibles : 12*26 = 312 27  Chiffrement affine Exemple — Déchiffrez le cryptogramme suivant, sachant qu’il a été chiffré en utilisant la clé (3, 11) o C=LAAJYX Transformation de déchiffrement : — k1-1= 3 -1mod 26 = 9 car 3 * 9 mod 26 = 1 — pi = Dk(Ci) = 9 * (Ci – 11) mod 26 — P = « affine » 28  Arithmétique modulaire — Anneau modulo N: 𝑍! ou 𝑍/𝑁𝑍 ={0,1,2,3,…,N-1} l'ensemble des restes modulo N (c- à-d. à la division par N) — Divisibilité : a divise b s’il existe un entier c tel que : b=a c — Congruence: On dit que a est congru à b modulo n (a=b mod n), ssi (b-a) est un multiple de n: b-a=k*n o a=b mod n ssi il existe k tq : b=k*n+a o Calcul du modulo: (E(x/y): partie entière de la division de x par y) 29  Arithmétique modulaire — L’inversibilité modulo N o a est inversible dans 𝑍! si PGCD(a,N)=1 o L’inverse de a est un entier u satisfaisant: au=1(mod N) o Exemple : u=3-1 mod 11; 3u= 1 mod 11 Þ 3x4=12 mod 11=1 u=4 30  Arithmétique modulaire — Calcul de l’inverse a-1 mod N: o Méthode-1: Euclide étendu: trouver les coefficients de bezout: au+Nv=1 où u=a-1 o Méthode-2: u est l’inverse de a alors: au= 1 mod N Þ au=N*q+1 et on itère sur q=1,2,3,…,N-1 jusqu’à trouver un multiple de a Exemple: o 9-1mod 16 Þ 9u=16q+1 après plusieurs essais on trouve q=5 o Donc 9-1mod 16 =9 31  Chiffrement du carrée du Polybe — Disposer en ordre les lettres de l’alphabet sur une matrice de 5x5 — Chaque lettre est remplacée par un groupe de deux chiffres: celui de sa ligne et celui de sa colonne. — Exemple: mot clé = DIFFICILE 1 2 3 4 5 1 D I F C L 2 E A B G H 3 J K M N O 4 P Q R S T 5 U V X Y Z — le chiffrement de « CARRE DE POLYBE » donne « 142243 432111 214135 155423 21 » 32  Faiblesses des chiffrements mono- alphabétiques — Chiffrement de Polybe o Clé trop courte --> l’ordre alphabétique de la plupart des lettres ne change pas dans la matrice --> déchiffrement sans clé est facile — Chiffrement par décalage o Petit espace de clés --> Attaque de brute force facile — Substitution mono alphapbétique o Motifs répétés --> attaques statistiques (analyse fréquentielle) 33 Cryptanalyse des chiffrements mono- alphabétiques Cryptanalyse par recherche exhaustive de la clé (Attaque en force Brute) — Essayer toutes les clés possibles — Condition : espace de clés restreint  Cryptanalyse des chiffrements mono- alphabétiques Cryptanalyse par analyse de fréquence Approche introduite par AbuYoussif Al-Kindi (IXe ciècle) — Principe o Utiliser des statistiques (fréquences de monogramme, de bigrammes, etc.) pour déduire : message en clair, clé, etc. — Méthode o Examiner les fréquences des caractères dans le texte chiffré. o Remplacer les caractères les plus fréquents du texte chiffré par les caractères les plus fréquents de la langue du texte d’origine.  Cryptanalyse des chiffrements mono- alphabétiques Cryptanalyse par analyse de fréquence Cryptanalyse des chiffrements mono- alphabétiques Cryptanalyse par analyse de fréquence — Exemple: — Fréquences : O = 14,Y = 9, Q = 7, J = 6… — Fréquences en français : E , S , A, I, T, … — Dans notre cas : O ?= E,Y ?= A ou Y ?= S, … — Texte déchiffré= NOUS VENONS JUSTE DE FAIRE UN TEST DANALYSE DE FREQUENCE SUR UN SIMPLE MESSAGE CODE Chiffrement de Vigenère (1568) — Substitution polyalphabétique o La même lettre peut être chiffrée par des caractères différents — Principe o Ce chiffrement utilise une clé qui définit le décalage pour chaque lettre du message (A: décalage de 0 cran, B: 1 cran, C: 2 crans,..., Z: 25 crans) o Chiffrement : 𝑐! = 𝐸 𝑘 𝑚𝑜𝑑 𝑑 (𝑚! ) 𝑚𝑜𝑑 26 = 𝑚! + 𝑘𝑖 𝑚𝑜𝑑 𝑑 𝑚𝑜𝑑 26 ! o Déchiffrement : 𝑀! = 𝐷 𝑘 𝑚𝑜𝑑 𝑑(𝑐! ) = 𝑐! – 𝑘𝑖 𝑚𝑜𝑑 𝑑 𝑚𝑜𝑑 26 ! o Clé : 𝐾 = (𝑘" , 𝑘# , … , 𝑘$ )  Chiffrement de Vigenère (1568) — Exemple : Clair L A V I E E S T B E L L E Clé B O N J O U R B O N J O U Décalage 1 14 13 9 14 20 17 1 14 13 9 14 20 Chiffré M O I R S Y J U P R U Z Y  Chiffrement de Playfair Exemple — Mot clé = MONARCHY — Les lettres répétées dans le même digramme seront Séparées par une nulle usuellement X : fille à fi lx le — Deux lettres dans la même rangée sont remplacées chacune par celle de droite : ar à RM — Deux lettres dans la même colonne sont remplacées chacune par celle de dessous : mu à CM — Sinon, chaque digramme est chiffré selon leurs rangée et colonne : hs à BP et ea à IM (ou JM) 40  Chiffrement de Hill — Chiffrement polygrammique (substitution par polygrammes) 𝑘!! 𝑘!" — La clé 𝐾 = est une matrice 2 x 2 où 𝑘𝑖𝑗ÎZ26 𝑘"! 𝑘"" — Chiffrement : 𝑪 = 𝑬𝒌(𝑴) = 𝑲×𝑴 𝒎𝒐𝒅 𝟐𝟔 𝑴 = 𝒎𝟏 , 𝒎𝟐 , … 𝒎𝒏 Découper M en digrammes : 𝑀! = 𝑚! 𝑚" , 𝑀" = 𝑚& 𝑚' , … 𝑐( 𝑘!! 𝑘!" 𝑚( 𝑐()! = 𝑘"! 𝑘"" × 𝑚()! 𝑚𝑜𝑑 26 41  Chiffrement de Hill — Chiffrement polygrammique (substitution par polygrammes) 𝑘!! 𝑘!" — La clé 𝐾 = est une matrice 2 x 2 où 𝑘𝑖𝑗ÎZ26 𝑘"! 𝑘"" — Déchiffrement: 𝑴 = 𝑫𝒌 𝑪 = 𝑲"𝟏 × 𝑪 𝒎𝒐𝒅 𝟐𝟔 𝟏 𝟏 𝒌𝟐𝟐 −𝒌𝟏𝟐 — 𝑲"𝟏 = 𝑪𝒐𝒎 𝑲 = 𝒅𝒆𝒕 𝑲 𝒌𝟏𝟏 𝒌𝟐𝟐 "𝒌𝟏𝟐 𝒌𝟐𝟏 −𝒌𝟐𝟏 𝒌𝟏𝟏 42  Chiffrement de Hill — Exemple1: Chiffrez le message suivant avec le chiffrement de Hill en utilisant la matrice : "Rendez-vous ce soir " en utilisant la clé C= HDTWK BNLSWOOEIGH — Exemple2: Soit C= "MFFTKYSNKOQYJUOILN " et k= 19 22 — 𝑘 $% = 11 19 — P=Dk(MF)Dk(FT)….. — P=Attaque demain à l’aube 43  Chiffrement par transposition Principe — Changer l’ordre des lettres Historique — Les Grecs entre le Xe et VIIe siècle av. J.-C., utilisaient une technique de chiffrement par transposition : Scytale 44  Chiffrement par transposition de colonnes — Clé o Choisir une clé de permutation 𝑘 = (𝑘1, 𝑘2, 𝑘3, … , 𝑘* ) (nouvelles positions des kième lettres) — Chiffrement o Écrire le texte clair ligne par ligne dans une matrice à m colonnes o Appliquer la permutation ligne par ligne conformément à la clé o Texte chiffré: lire le texte colonne par colonne — Déchiffrement o Écrire le texte chiffré dans le sens des colonnes o Appliquer la permutation inverse conformément à la clé o Texte clair: lire le texte ligne par ligne  Chiffrement par permutation — Exemple : o k=(2,4,1,3) o P=Transposition o Ek(P)=Ek(tran) Ek(spos) Ek(itio) Ek(nzzz) o Ek(P)=RPTXNSOXTSINAOIX Clé 2 4 1 3 2 4 1 3 1 2 3 4 T R A N Chiffrement R N T A Déchiffrement T R A N Texte clair S P O S P S S O Permutation S P O S Permutation I T I O + Lecture T O I I + Lecture I T I O horizontale verticale N X X X X X N X N X X X Texte chiffré=RPTXNSOXTSINAOIX  Enigma — Machine à chiffrer conçue au début du XXè siècle par les Allemands pendant la seconde guerre mondiale — Pour déchiffrer, il faut utiliser la même clé que le chiffrement — Cassée par des cryptanalystes polonais et britanniques pendant la guerre La méthode de chiffrement est basée sur de la substitution : – L’opérateur tape le message en clair. Chaque lettre du message en clair est remplacée par une autre lettre dans le message chiffré (les lettres chiffrées s’allument sur le tableau de sortie au fur et à mesure de la frappe en clair de l’opérateur) ; – L’utilisation des rotors a pour conséquence qu’une lettre en clair sera substituée par des 47 lettres différentes tout au long du message chiffré.  Enigma Fonctionnement Machine électromécanique composée de: — Tableau de connexion o Se situe avant l’entrée sur le brouilleur ; o Effectue des permutations simples. — De 3 à 6 rotors (selon le modèle) o Permutations aléatoires des lettres de l’alphabet ; o Le rotor tourne à chaque lettre tapée ; o Lorsque le premier rotor a fait un tour (26 positions), le second rotor tourne d’un cran, et ainsi de suite. — Le réflecteur o Dernière permutation 2 à 2 des lettres avant de les faire retraverser les retors et le tableau de connexion. 48  Enigma Réflecteur Rotor 1 Rotor 2 Rotor 3 Tambour E/S Enigma - exemple de chiffrement d’une lettre - - - - - - - - - - - - - - - - (T chiffré en G) D - - > - - D - - - - - - - - - - - - - - > - - G - - > G - - - - - - K - - > - - H - - H - - - - - - - - - - - - - - - - - - - - - - - - - - P - - > - - P R - - > - - R W - - > - - - - - - - > - - - - - - - U - - U - - > > Z P H N M S W C I Y T Q E D O B L R F K U V G X J A Tableau de 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 connexion > > Q W E R T Z U I O Q W E R T Z U I O A D S F G H J K A D S F G H J K P Y X C V B N M L P Y X C V B N M L 49  Les bases de la cryptographie Chiffrement conventionnel 50  Cryptographie conventionnelle — Algorithmes et standards de chiffrement o AES, Triple DES, IDEA, RC6, RSA, DSA, ELGamal,….. — Deux classes d’algorithmes o Chiffrement symétrique o Chiffrement asymétrique — Implémentation matériel et logiciel 51  La cryptographie symétrique (à clé secrète) — La clé utilisée pour le chiffrement est la même que celle utilisée pour le déchiffrement ; — Cette clé doit être secrète : partagée uniquement entre les utilisateurs habilités, sinon la confidentialité du message n’est plus assurée ! — Pour N communicants potentiels, il faut N(N-1)/2 clés secrètes — La clé secrète peut aussi partagée par un groupe d’utilisateurs 52  La cryptographie asymétrique (à clé public) — Une paire de clé publique/privée (kd ,ke): ke ≠ kd o Clé publique : connue de tous ; o Clé privée : clé personnelle et connue de son seul propriétaire. — Ces deux clés sont mathématiquement liées o Commutativité des méthodes de chiffrement et de déchiffrement : DKe ( E Kd ( M )) = EKd ( DKe ( M )) = MP o La connaissance de la clé publique ne permet pas de calculer facilement la clé privée 53  La cryptographie asymétrique (à clé public) — Une paire de clé publique/privée (kd ,ke): ke ≠ kd o Clé publique : connue par tous ; o Clé privée : clé personnelle et connue de son seul propriétaire. 54  Quel type de chiffrement ? Chiffrement symétrique Chiffrement asymétrique Avantages Rapidité des opérations (adapté Facilité d’échange des clés : les à du trafic en temps réel) ; seules clés qui ont besoin d’être échangées sont des clés Clés courtes (256 bits suffisent publiques (dont il faut assurer la actuellement) ; protection en intégrité) ; Inconvénients Difficulté d’échange sécurisé des Lenteur des opérations (peu clés secrètes : comment le faire adapté à du trafic en temps réel) ; en protégeant ce secret ? Grande taille des clés (2048 bits minimum actuellement) ; Exemples d’algorithmes sûrs (ANSSI 2021) AES, 3-DES, ChaCha20 RSA, DSA, ECC 55 Source : Cyberedu  Principe de Kerckhoff — La difficulté ne doit pas dépendre du secret des algorithmes mais plutôt du secret des clés — La clé doit être le seul élément qui doit être protégé. 56  Sécurité des chiffrements — Inconditionnellement sûr: le chiffrement ne peut pas être cassé quelle que soit les ressources de calcul que l’on dispose — Algorithmiquement sûr : le chiffrement ne peut pas être cassé dans un temps raisonnable (polynomial) avec les ressources de calcul disponibles 57  Les bases de la cryptographie Chiffrement symétrique 58  Chiffrement symétrique Deux méthodes — Chiffrement par blocs — Chiffrement par flot — Le texte clair m est divisé en — Opère sur des données bit par bit blocs de taille fixe (ex: 64 bits, (en continu) 128 bits, 192 bits, …) — Exp: Vernam, RC4, ChaCha20 — On chiffre un bloc à la fois — Exp: AES, IDEA, … Par flot 59  Chiffrement symétrique — Deux principaux critères de sécurité o La taille du bloc (e.g. n = 64 ou 128 bits). Les modes opératoires permettent généralement des attaques quand plus de 2n/2 blocs sont chiffrés avec une même clé o La taille de clé (e.g. k = 128 bits). Pour un bon algorithme, la meilleure attaque doit coûter 2k opérations (recherche exhaustive) o La taille minimale des clés symétriques recommandée au- delà de 2020 est de 128 bits 60  Chiffrement par flot Système de Vernam (masque jetable) — Trois caractéristiques o Une clé de même taille que le texte à chiffrer o La clé est générée aléatoirement o La clé est jetable (ne sert qu’à chiffrer un seul message) 61  Chiffrement par flot Système de Vernam (masque jetable) — Avantage : Inconditionnellement sûr (sécurité parfaite) o il est impossible de déchiffrer sans connaître la clé, même avec une puissance illimitée de calcul. — Inconvénient ? o difficile à implémenter 62  Chiffrement par flot — Génération de clés pseudo-aléatoires 63  Chiffrement par flot LFSR (Linear Feedback Shift Register) — Un LFSR de degré m comporte un registre de m bits : (𝑠*"+, 𝑠*",, … , 𝑠-) — A chaque cycle, le registre subit un décalage à gauche en produisant 𝑠.. — Un feedback est poussé vers le bit de poids le plus fort. — On ajuste la participation des autres bits via (𝑝*"+ , 𝑝*", , … , 𝑝- ) 64  Chiffrement par flot LFSR (Linear Feedback Shift Register) — Modèle : 𝒑 𝒔𝒎*𝟏 , 𝒔𝒎*𝟐 , … , 𝒔𝟎 = 𝒑𝒎*𝟏. 𝒔𝒎*𝟏 ⨁ 𝒑𝒎*𝟐. 𝒔𝒎*𝟐 ⨁ … ⨁𝒑𝟎. 𝑠.. — Souvent représenté par un polynôme : 𝒑 𝒙 = 𝒙𝒎 + 𝒑𝒎*𝟏 𝒙𝒎*𝟏 + ⋯ + 𝒑𝟏 𝒙 + 𝒑𝟎. — La période maximale générée par un LFSR de degré m est : 2m – 1. — La périodicité pose un problème de sécurité. 65  Chiffrement par flot Périodicité du LFSR 66  Chiffrement par flot LFSR - Exercice — Calculer les deux premiers octets de la suite binaire produite par le LFSR de degré m = 8, ayant comme coefficients de rétroaction (p0, p1, p2, p3, p4, p5, p6, p7) = (1, 1, 0, 1, 1, 0, 0, 0) et initialisé par 0xff — Donnez le polynôme du LFSR 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 𝑝 𝑋 = 𝑋+ + 𝑋' + 𝑋& + 𝑋 + 1 67  Chiffrement par blocs — Un premier exemple : DES o DES = Data Encryption Standard o Standard de chiffrement symétrique conçu par le NIST o Standardisé en 1977 o Attaqué en 1999 en 22h o Remplacé par l’AES actuellement (depuis 2001) 68  AES (Advanced Encryption Standard) — Standard américain (NIST, 2000) remplaçant du DES — Utilise l’algorithme de Rijndael (Vincent Rijmen et Joan Daemen) — Taille des blocs : 128 bits, taille des clés : 128, 192 ou 256 bits 69  AES (Advanced Encryption Standard) — Chiffrement par bloc itératif — Une fonction de tour est réitérée t fois — Utilisation d’opérations simples et efficaces (substitution, transposition, XOR) — Génération de clés de tour (ou sous- clés) à partir de la clé secrète K — Taille des clés (bits): 128, 192, 256 — Taille des blocs: 128 bits 70  AES : Construction Découpage en blocs — Un bloc (128 bits) est découpé en 16 octets et placé dans une matrice 4x4 : 71  AES : Construction Fonction de tour 72  AES : Construction Substitution par octet (Boite S) — La substitution S est une fonction de 8 bits vers 8 bits (S-Box) : 𝑏&,( = 𝑆(𝑎&,( ) 73  AES : Construction Substitution par octet (Boite S) — La Boîte S (S-box) 74  AES : Construction ShiftRow — Pour chaque ligne i (0 ≤ i ≤ 3), effectuer i décalage circulaire (vers la gauche) 75  AES : Construction MixColumn — Multiplication par une matrice auxiliaire 76  AES : Construction MixColumn — MixColumn: Opérations linéaires dans GF(28) 77  AES : Construction KeySchedule (dérivation des sous clés) — La première colonne 78  AES : Construction KeySchedule (dérivation des sous clés) — Le reste des colonnes 79  AES : Construction AddRoundKey 80  Quel chiffrement utiliser aujourd’hui ? — Algorithmes recommandés (ANSSI, NIST,...) o AES (128, 192, 256 bits) o ChaCha20 — Autres algorithmes utilisés ponctuellement o Triple-DES (abandonné par NIST depuis 2019) o IDEA (PGP) o BlowFish o… 81  Modes opératoires — Découper les données à chiffrer en blocs de longueur fixe (par exemple 64 bits, 128 bits ou 256 bits) — Décrit comment appliquer un chiffrement par blocs — La taille du bloc dépend de l’algorithme de chiffrement (32 – 512 bits). — Padding — Les blocs sont chiffrés les uns après les autres — Principaux modes de chiffrement o Electronic Code Book (ECB). o Cipher Block Chaining (CBC). o Output Feedback (OFB). o Cipher Feedback (CFB). o Counter (CTR) 82  Electronic Code Book (ECB) — Déterministe : un même chiffré correspond toujours au même clair. — Pas de propagation d’erreurs : une erreur sur un bloc de chiffré modifie seulement un bloc de clair 83  Electronic Code Book (ECB) 84  Cipher Block Chaining (CBC) — Probabiliste : pour un même clair, chiffrés différents si IV choisis différents. — Propagation des erreurs 85  Cipher Block Chaining (CBC) 86  Counter(CTR) — Probabiliste : pour un même clair, des chiffrés différents. — Pas de propagation d’erreurs : une erreur sur un bloc de chiffré modifie seulement un bloc de clair. — Le déchiffrement d’un bloc ne dépend pas des blocs précédents 87  Les bases de la cryptographie Chiffrement asymétrique 88  Fonction à sens unique Facile 𝒙 f(𝒙) Difficile Þ Problème mathématique NP 89  Chiffrement asymétrique — La sécurité de ces algorithmes est basée sur des problèmes mathématiques difficile à résoudre: o Factorisation : étant donné n=pxq difficile à trouver p et q (nombres premiers) o Logarithme discret (DL) : étant données b=ga et g, trouver a o Problème du sac à dos: Etant donnée une suite A = {𝑃! , 𝑃" , … , 𝑃# , T}. Est-il possible de trouver une suite de bits 𝑏! 𝑏" … 𝑏# TQ 𝑇 = 𝑏! 𝑃! + 𝑏" 𝑃" + … + 𝑏# 𝑃# 90  Chiffrement asymétrique — Factorisation Facile Difficile 91  RSA — Introduit en 1978 par Ronald Rivest, Adi Shamir et Leonard Adleman, dans A Method for Obtaining Digital Signatures and Public-key Cryptosystems. — RSA est basé sur le calcul dans les groupes Z|nZ; plus précisément sur l'exponentiation modulaire — Sa sécurité repose essentiellement sur le problème de factorisation — C'est à l'heure actuelle le système à clé publique le plus utilisé 92  RSA Idée: sous certaines conditions de e, d, n, on aura pour tout M < n: Med mod n = M Algorithme: — Génération des clés o Choisir deux grands nombres premiers p et q et Calculer n = p.q o Calculer Q(n) = (p – 1). (q – 1) o Choisir e < Q(n) TQ PGCD (e,Q(n)) =1 o Calculer d TQ e.d mod Q(n) = 1 o Clé publique : (e, n) Clé privée : (d, n). — Chiffrement : C = Me mod n (condition : M < n) — Déchiffrement : M = Cd mod n 93  RSA: Exemple d’une pair de clés 94  RSA: Chiffrement vs Signature 95  RSA: Exemple 96  RSA: En pratique ? — Comment trouver deux grands nombres premiers p et q ? o Test probabiliste de primalité — Comment trouver 𝑒 premier avec 𝜑(𝑛) ? o Algorithme d’Euclide — Comment trouver d à partir de e ? o Algorithme d’Euclide étendu — Comment effectuer les gros calculs 𝑚, 𝑚𝑜𝑑 𝑛 ? o Algorithme de Square and Multiply 97  RSA: Square and Multiply Calcule de xa mod n : — Décomposition de l’exposant a en écriture binaire : a= — Le calcul se fait par passage de bit en bit (bits forts àbits faibles) de la façon suivante : — A chaque étape, élévation au carré (x2 mod n) et, suivant la valeur du bit auquel on passe, multiplication par x (mod n) si bit=1 ou multiplication par 1 (mod n) si bit=0. Exemple : calcule de 10011 mod 206 = 1001011 mod 206 [((1002*1)2*100)2* 100] mod 206= 116 mod 206 1 0 1 1 98 K.hamouid - Université de Batna  Sécurité de RSA 99  Sécurité de RSA — Une clé RSA de 768 bits a été factorisée en 2009 (il a fallu 425 CPU (4 cœurs) pendant 1 an) — En 2019, une clé de 795 bits a été factorisée — Taille de clé consillée par l’ANSSI : 3072 bits 100  Sécurité RSA: autres angles d’attaques — Attaque par factorisation de Fermat ! !/' — Attaque de Wiener sur d faible (𝑑 < 𝑛 ) & — Attaque sur modulo n commun — Attaque sur chiffrement du même message — Attaque par canal auxiliaire (side-channel) 101  RSA- attaque par factorisation de Fermat Théorème: soit n=p x q, Tel que p et q sont très proches (|𝑝 − 𝑞| < 𝑐𝑛+/0), alors n peut être factorisé en temps polynomiale par la méthode de Fermat — Principe de Fermat: o Rechercher deux entiers x et y tels que: 𝑛 = 𝑥 # − 𝑦 # = (𝑥 − 𝑦)(𝑥 + 𝑦)) o Si (𝑥 − 𝑦) ≠ 1 et (𝑥 + 𝑦) ≠ 1 alors: p = 𝑥 − 𝑦 , 𝑞 = (𝑥 + 𝑦) — Algorithme: o On essaie différentes valeurs de x : 𝑥 = √𝑛 + 𝑖 (𝑖 = 0,1,2, … ) o Si (𝑥 # −𝑛) est un carré alors on a trouvé x et y o p = 𝑥 − 𝑦 , 𝑞 = (𝑥 + 𝑦) 102  RSA- attaque par factorisation de Fermat — Exemple: Soit N = 2027651281 Racine N = 45029,44 ≈ 45030 i=0 ⟹ 45030² - N = 49619 (pas carré) i=1 ⟹ 45031² - N = 139 680 (pas carré)... i=11 ⟹ 45041² - N = 1040400 = 10202 N = (45041 – 1020) (45041 + 1020) = 44 021 × 46 061 103  RSA- attaque par canal auxiliaire — On réalise une analyse de la consommation sur un circuit implémentant RSA. Ce graphe est le courant en fonction du temps lors du déchirement d’un message — Déterminez les bits de la clé privée sachant que les « pics » de courant correspondent soit à des multiplications soit à des carrés. — Modifiez la fonction square and multiply afin qu’on contre cette attaque. 104  Chiffrement asymétrique — Logarithme discret (DL) Facile Difficile 105  Protocole du Diffie-Helman — Inventé par Whitfield Die et Martin Hellman en 1976 — Échange d’une clé secrète entre deux ou plusieurs participants — Problème du logarithme discret 106  D-H : idée de base — Partager une information secrète commune à partir d’informations échangées publiquement secret secret publique + + publique publique = ? = secret secret 107  D-H : idée de base Couleurs communes publiques + + Couleurs secrètes = = Couleurs publiques + + = = Couleur secrète commune 108  D-H: deux participants — A et B choisissent publiquement les paramètres (g, n). — A choisit un nombre secret 𝑥 ∈ 𝑍$ — A choisit un nombre secret 𝑦 ∈ 𝑍$ 109  D-H: trois participants 110  Chiffrement d’Elgamal — Inventé par Taher Elgamal en 1985. — Problème du logarithme discret. — Permet le chiffrement et déchirement des messages. 111  Chiffrement d’Elgamal 112  Chiffrement asymétrique — Problème du sac à dos o Etant donnée un ensemble d’entiers 𝐴 = {𝑃+ , 𝑃, , … , 𝑃1 , 𝑇} (T: la capacité total du sac à dos, Pi: le poids des objets). Est-il possible de trouver série de valeurs binaires 𝑏+, 𝑏, , … , 𝑏1 Tels que: 𝑇 = 𝑏+𝑃+ + 𝑏,𝑃, + … + 𝑏1 𝑃1 113  Chiffrement asymétrique — Problème du sac à dos o Etant donnée un ensemble d’entiers 𝐴 = {𝑷𝟏 , 𝑷𝟐 , … , 𝑷𝒌 , 𝑻} (T: la capacité total du sac à dos, Pi: le poids des objets). Est-il possible de trouver série de valeurs binaires 𝑏+, 𝑏, , … , 𝑏1 Tels que: 𝑻 = 𝒃 𝟏 𝑷𝟏 + 𝒃 𝟐 𝑷𝟐 + … + 𝒃 𝒌 𝑷𝒌 o Si A est une suite normale Þ Problème NP (difficile) 114  Chiffrement asymétrique — Problème du sac à dos o Etant donnée un ensemble d’entiers 𝑨 = {𝑷𝟏 , 𝑷𝟐 , … , 𝑷𝒌 , 𝑻} (T: la capacité total du sac à dos, Pi: le poids des objets). Est-il possible de trouver série de valeurs binaires 𝑏+, 𝑏, , … , 𝑏1 Tels que: 𝑻 = 𝒃 𝟏 𝑷𝟏 + 𝒃 𝟐 𝑷𝟐 + … + 𝒃 𝒌 𝑷𝒌 o Si A est une suite super-croissante (𝑃. > ∑."+ 23+ 𝑃2 , (1 ≤ 𝑖 ≤ 𝑘)) Þ problème linéaire (facile) 115  Chiffrement de Merkle-Hellman — Inventé par Ralph Merkle et Martin Hellman en 1978 — Idée: utiliser un problème de sac à dos super-croissant comme clé privée, et de le camoufler sous un problème de 116 sac à dos général pour en faire une clé publique.  Chiffrement de Merkle-Hellman — Choisir une suite super-croissante 𝑨 = {𝑷𝟏 , 𝑷𝟐 , … , 𝑷𝒌 } — Choisir deux nombres 𝒏 et 𝒎 TQ 𝒎 > ∑ 𝑷𝒊 et PGCD(n,m)=1 — Calculer la suite normale 𝑩 = {𝑷6𝟏 , 𝑷6𝟐 , … , 𝑷6𝒌 } TQ 𝑷6𝒊 = 𝒏. 𝑷𝒊 𝒎𝒐𝒅 𝒎. — Clé publique : B. — Clé privée : (A, n,m). — Chiffrement : o 𝑴 = 𝒃𝟏 𝒃𝟐 … 𝒃𝒌 o 𝑪 = 𝒃𝟏 𝑷/𝟏 + 𝒃𝟐 𝑷/𝟐 + … + 𝒃𝒌 𝑷/𝒌 — Déchiffrement : o Calculer 𝒏–𝟏 TQ 𝒏. 𝒏–𝟏 𝒎𝒐𝒅 𝒎 = 𝟏. o Calculer 𝑻 = 𝒏–𝟏. 𝑪 𝒎𝒐𝒅 𝒎. o Calculer les 𝒃𝒊 avec l’algorithme de résolution de suite super- croissante. 117  Les bases de la cryptographie Introduction à la cryptographie quantique 118  Le monde quantique — Les propriétés quantiques: o La superposition o L'intrication — Le paradoxe du chat de Schrödinger (superposition & mesure) — Superposition: l’état du chat est incertain, il est ni mort ni vivant o Notation bra-ket : 𝒄𝒉𝒂𝒕⟩ = 𝜶 𝒎𝒐𝒓𝒕⟩ + 𝜷|𝒗𝒊𝒗𝒂𝒏𝒕⟩ — Mesure: après la mesure, l’état est bien défini (soit mort, soit vivant) 119  Le qubit au cœurs de l’informatique quantique — qubit: unité de codage de l’information à deux niveaux (|0⟩ et |1⟩) en informatique quantique — Superposition d’états: un qbit peut être dans une infinité d'états (une combinaison linéaire de deux états) — Mesure: o Soit |𝟎⟩ avec une probabilité 𝜶 𝟐 o Soit |𝟏⟩ avec une probabilité 𝜷 𝟐 120  Encodage de qubits — Encodage 1: o On représente b = 0 par |𝟎⟩ et b = 1 par |𝟏⟩ o Pour lire b, il suffit de mesurer l’état — Encodage 2 : 𝟏 𝟏 o b = 0 par | −⟩ = |𝟎 ⟩ − |𝟏⟩ √𝟐 √𝟐 𝟏 𝟏 o b = 1 par| +⟩ = |𝟎 ⟩ + |𝟏⟩ √𝟐 √𝟐 * o Pour lire b, on fait tout d’abord une rotation de − et on mesure l’état. + — On sait récupérer b si et seulement si on connaît l’encodage. — Si on essaie de récupérer b avec le mauvais encodage, l’état est détruit 121  Algorithmique classique versus quantique — Superposition de plusieurs qubits qui fonctionnent ensemble (intrication) — Un système X à deux qubits :|𝑿⟩ = 𝜶|𝟎𝟎⟩ + 𝜷|𝟎𝟏⟩ + 𝜸|𝟏𝟎⟩ + 𝜹|𝟏𝟏⟩ — L’algorithme classique à 𝑛 bits effectue 𝑛 calculs en série — L’algorithme quantique à 𝑛 qubits explore 27 combinaisons en parallèle 122  Impact chiffrement symétrique Algorithme de Grover — L’algorithme de Grover (1996) permet d’accélérer l’attaque par force brute. — Algorithme classique : clé de n bits implique 2n instances de calcul unitaire. — Algorithme quantique : clé de n bits implique 2n/2 instances de 123 calcul intriqué  Impact chiffrement asymétrique Algorithme de Shor — L’algorithme de Shor (1994) permet la factorisation des nombres entiers.. — Algorithme classique : complexité exponentielle — Algorithme quantique : complexité polynomiale 124 Échange de clés quantique BB84 Échange de clés quantique BB84 Détection d’espionnage