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 Chapitre 1. Clef privée (secrète), chiffrement à flot et par bloc (4 Semaines

1 Chapitre 1. Clef privée (secrète), chiffrement à flot et par bloc (4 Semaines) 1. Rappels sur les concepts cryptographiques de base Cryptologie : Il s’agit d’une science mathématique comportant deux branches : la cryptographie et la cryptanalyse. Cryptographie : La cryptographie est l’étude des méthodes donnant la possibilité d’envoyer des données de manière confidentielle sur un support donné. Chiffrement : Le chiffrement consiste à transformer une donnée (texte, message, ...) afin de la rendre incompréhensible par une personne autre que celui qui a créé le message et celui qui en est le destinataire. Déchiffrement : La fonction qui permet de retrouver le texte clair à partir du texte chiffré. Texte chiffré : Appelé également cryptogramme, le texte chiffré est le résultat de l’application d’un chiffrement à un texte clair. Clef : Il s’agit du paramètre impliqué et autorisant des opérations de chiffrement et/ou déchiffrement. Cryptanalyse : Opposée à la cryptographie, elle a pour but de retrouver le texte clair à partir de textes chiffrés en déterminant les failles des algorithmes utilisés. Cryptosystème : Il est défini comme l’ensemble des clés possibles (espace de clés), des textes clairs et chiffrés possibles associés à un algorithme donné. Remarque : On parle de "décryptage" pour désigner l’action permettant de retrouver le texte clair sans connaître la clef de déchiffrement. On emploie également parfois les termes "cryptage" et "crypter" pour qualifier l’action de chiffrer un message. 2. Notations – M représente le texte clair, – C est le texte chiffré, – K est la clé (dans le cas d’un algorithme à clé symétrique), Ek et Dk dans le cas d’algorithmes asymétriques, – E(x) est la fonction de chiffrement, – D(x) est la fonction de déchiffrement. Ainsi, avec un algorithme à clef symétrique, C = E(M) et M = D(C) En cryptographie, la propriété de base est que M = D(E(M)) 2 3. Principe de Kerckhoff La sécurité du chiffre ne doit pas dépendre de ce qui ne peut pas être facilement changé. En d’autres termes, aucun secret ne doit résider dans l’algorithme mais plutôt dans la clé. Sans celle-ci, il doit être impossible de retrouver le texte clair à partir du texte chiffré. Par contre, si on connaît K, le déchiffrement est immédiat. 4. Les deux catégories de systèmes 4.1 Cryptosystème à clé symétrique Caractéristiques : – Les clés sont identiques : KE = KD = K, – La clé doit rester secrète, 4.2 Cryptosystème à clé publique Caractéristiques : – Une clé publique PK (symbolisée par la clé verticale), – Une clé privée secrète SK (symbolisée par la clé horizontale), – Propriété : La connaissance de PK ne permet pas de déduire SK, – DSK(EPK(M)) = M, Qualités d’un cryptosystème. Lorsque l’on parle de “sécuriser un échange”, on souhaite prêter attention aux 3 services suivants : la confidentialité, l’intégrité et l’authentification. 3 I Confidentialité : lisible uniquement par les personnes autorisées, I intégrité : être sûr qu’il n’a pas été modifié (intentionnellement ou accidentellement). I authenticité : être sûr de son origine, La cryptographie classique 1. chiffrement par substitution monoalphabétique Chaque lettre est remplacée par une autre lettre ou symbole. Parmi les plus connus, on citera le chiffre de César, le chiffre affine, ou encore les chiffres désordonnés. Tous ces chiffres sont sensibles à l’analyse de fréquence d’apparition des lettres (nombre de fois qu’apparait une même lettre dans un texte). 1.1 Chiffre de César (50 av. J-C) Son principe est un décalage des lettres de l’alphabet. Dans les formules ci-dessous, p est l’indice de la lettre de l’aphabet et k le décalage. Pour le chiffrement, on a la formule C = E(p) = (p + k) mod 26 Pour le déchiffrement, il viendra p = D(C) = (C − k) mod 26 Donc p=(p+k-k) mod 26 = p mod 26 Si on connait l’algorithme utilisé (ici César), la cryptanalyse est très facile. En effet, dans le cas du chiffre de César, seules 25 clés sont possibles. Cas du chiffrement de César (k=3). La transposition des caractères est la suivante: 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 D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A,B,C Exemple x= « CE TEXTE EST CHIFFRE PAR SUBSTITUTION » Y= « YV PVFPV VQP YAIHHJV RDJ QEXQPIPEPICS » Des chiffres et des lettres Il est plus facile de manipuler des nombres que des lettres, aussi nous passons à une formulation mathématique. Ainsi "A L E A" devient "0 11 4 0". 4 Nous allons voir que le chiffrement de César correspond à une opération mathématique très simple. Pour cela, rappelons la notion de congruence et l’ensemble Z / 26Z. Modulo Soit n > 2 un entier fixé. Définition 1. On dit que a est congru à b modulo n, si n divise b - a. On note alors a ≡ b (mod n). Pour nous n = 26. Ce qui fait que 28 ≡ 2 (mod 26), car 28 - 2 est bien divisible par 26. De même 85 = 3 . 26 + 7, donc 85 ≡ 7 (mod 26). On note Z/26Z l’ensemble de tous les éléments de Z modulo 26. Cet ensemble est représenté par les 26 éléments {0, 1, 2, . . . , 25}. En effet, puisqu’on compte modulo 26 : 26 ≡ 0, 27 ≡ 1, 28 ≡ 2, . . . , 52 ≡ 0, 53 ≡ 1, . . . et de même -1 ≡ 25, -2 ≡ 24,... Exemple (0 + 4) mod 26 = 4, ‘A’ + ‘E’ = ‘E’ (14 + 14) mod 26 = 2 ‘O’ + ‘O’ = ‘C’ (10 – 20) mod 26 = 16 ‘K’ – ‘U’ = ‘Q’ (3 · 7) mod 26 = 21 ‘D’ · ‘H’ = ‘V’ Exercice. L'inverse modulaire d'un entier En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif a pour la multiplication modulo n est un entier u satisfaisant l'équation : a.u ≡ 1(mod n) En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté Z/nZ. u peut être noté 1  a , étant entendu implicitement que l'inversion est modulaire et se fait modulo n. La définition est donc équivalente à : u ≡ 1  a (mod n) 5 L'inverse de a modulo n existe si et seulement si a et n sont premiers entre eux, (c.-à-d. si PGCD (a, n) = 1). Si cet inverse existe, l'opération de division par a modulo n équivaut à la multiplication par son inverse. D'après la définition ci-dessus, u est un inverse de a modulo n s'il existe un entier v tel que 1-au=nv Ou encore : au+nv=1 D'après le théorème de Bachet-Bézout, ceci a lieu si et seulement si PGCD(a, n) =1, c'est- à-dire si a et n sont premiers entre eux. Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11. u ≡ 1 3(mod 11) Cela revient à calculer u vérifiant 3.u ≡ 1(mod 11) Dans l'ensemble de Z/11Z, une solution est 4 car 3.4 = 12 ≡ 1(mod 11) et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4. 6 3. Chiffre affine On dit qu’une fonction est affine lorsqu’elle est de la forme f(x) =ax+b. L’idée est d’utiliser comme fonction de chiffrement 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 où b est le décalage (le k du chiffre de César). Propriété de neutralité : si b = 0, alors "a" est toujours chiffré "A" car il ne subit aucun décalage. 4. Chiffrement polygraphique Chiffre de Hill (1929) Les lettres sont d’abord remplacées par leur rang dans l’alphabet. Les lettres Pk et Pk+1 deviennent Ck et Ck+1 7 Les composantes de cette matrice doivent être des entiers positifs. De plus la matrice doit être inversible dans Z26. Cependant, sa taille n’est pas fixée à 2. Elle grandira selon le nombre de lettres à chiffrer simultanément. Chaque digramme clair (P1 et P2) sera chiffré (C1 et C2) selon : Exemple de chiffrement : On prend comme clef de cryptage la matrice Pour chiffrer le message "je". Après avoir remplacé les lettres par leur rang dans l’alphabet (a=1, b=2, etc.), elle obtiendra 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 Exemple de déchiffrement : Pour déchiffrer le message, on doit calculer : On prend donc cette matrice pour déchiffrer le message "FG". Après avoir remplacé les lettres par leur rang dans l’alphabet (A=1, B=2, etc.), il obtiendra : 5. Substitutions polyalphabétiques a- Chiffre de Vigenère (1568) C’est une amélioration décisive du chiffre de César. Sa force réside dans l’utilisation non pas d’un, mais de 26 alphabets décalés pour chiffrer un message. Ce chiffre utilise une clef qui définit le décalage uploads/Litterature/ courscryptom2-reseaux.pdf