Cryptographie Vidéo ■partie 1. Le chiffrement de César Vidéo ■partie 2. Le chif

Cryptographie Vidéo ■partie 1. Le chiffrement de César Vidéo ■partie 2. Le chiffrement de Vigenère Vidéo ■partie 3. La machine Enigma et les clés secrètes Vidéo ■partie 4. La cryptographie à clé publique Vidéo ■partie 5. L'arithmétique pour RSA Vidéo ■partie 6. Le chiffrement RSA 1. Le chiffrement de César 1.1. César a dit... Jules César a-t-il vraiment prononcé la célèbre phrase : DOHD MDFWD HVW ou bien comme le disent deux célèbres Gaulois : « Ils sont fous ces romains ! ». En fait César, pour ses communications importantes à son armée, cryptait ses messages. Ce que l’on appelle le chiffrement de César est un décalage des lettres : pour crypter un message, A devient D, B devient E, C devient F,... A 7−→D B 7−→E C 7−→F ... W 7−→Z X 7−→A Y 7−→B Z 7−→C Voici une figure avec l’alphabet d’origine en haut et en rouge, en correspondance avec l’alphabet pour le chiffrement en-dessous et en vert. Nous adopterons la convention suivante, en vert c’est la partie du message à laquelle tout le monde a accès (ou qui pourrait être intercepté), c’est donc le message crypté. Alors qu’en rouge c’est la partie du message confidentiel, c’est le message en clair. Pour prendre en compte aussi les dernières lettres de l’alphabet, il est plus judicieux de représenté l’alphabet sur un anneau. Ce décalage est un décalage circulaire sur les lettres de l’alphabet. CRYPTOGRAPHIE 1. LE CHIFFREMENT DE CÉSAR 2 Pour déchiffrer le message de César, il suffit de décaler les lettres dans l’autre sens, D se déchiffre en A, E en B,... Et la célèbre phrase de César est : ALEA JACTA EST qui traduite du latin donne « Les dés sont jetés ». 1.2. Des chiffres et des lettres Il est plus facile de manipuler des nombres que des lettres, aussi nous passons à une formulation mathématique. Nous associons à chacune des 26 lettres de A à Z un nombre de 0 à 25. En termes mathématiques, nous définissons une bijection : f :  A, B, C,..., Z −→  0,1,2,...,25 par A 7−→0 B 7−→1 C 7−→2 ... Z 7−→25 Ainsi "A L E A" devient "0 11 4 0". Le chiffrement de César est un cas particulier de chiffrement mono-alphabétique, c’est-à-dire un chiffrement lettre à lettre. Quel est l’intérêt ? 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. 1.3. 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 peut par exemple être représenté par les 26 éléments {0,1,2,...,25}. En effet, puisqu’on compte modulo 26 : 0, 1, 2, ..., 25, puis 26 ≡0, 27 ≡1, 28 ≡2,..., 52 ≡0, 53 ≡1,... et de même −1 ≡25, −2 ≡24,... Plus généralement Z/nZ contient n éléments. Pour un entier a ∈Z quelconque, son représentant dans {0,1,2,..., n− 1} s’obtient comme le reste k de la division euclidienne de a par n : a = bn + k. De sorte que a ≡k (mod n) et 0 ⩽k < n. De façon naturelle l’addition et la multiplication d’entiers se transposent dans Z/nZ. Pour a, b ∈Z/nZ, on associe a + b ∈Z/nZ. CRYPTOGRAPHIE 1. LE CHIFFREMENT DE CÉSAR 3 Par exemple dans Z/26Z, 15 + 13 égale 2. En effet 15 + 13 = 28 ≡2 (mod 26). Autre exemple : que vaut 133 + 64 ? 133+64 = 197 = 7×26+15 ≡15 (mod 26). Mais on pourrait procéder différemment : tout d’abord 133 = 5×26+3 ≡3 (mod 26) et 64 = 2 × 26 + 12 ≡12 (mod 26). Et maintenant sans calculs : 133 + 64 ≡3 + 12 ≡15 (mod 26). On fait de même pour la multiplication : pour a, b ∈Z/nZ, on associe a × b ∈Z/nZ. Par exemple 3 × 12 donne 10 modulo 26, car 3 × 12 = 36 = 1 × 26 + 10 ≡10 (mod 26). De même : 3 × 27 = 81 = 3 × 26 + 3 ≡3 (mod 26). Une autre façon de voir la même opération est d’écrire d’abord 27 = 1 (mod 26) puis 3 × 27 ≡3 × 1 ≡3 (mod 26). 1.4. Chiffrer et déchiffrer Le chiffrement de César est simplement une addition dans Z/26Z ! Fixons un entier k qui est le décalage (par exemple k = 3 dans l’exemple de César ci-dessus) et définissons la fonction de chiffrement de César de décalage k qui va de l’ensemble Z/26Z dans lui-même : Ck :  Z/26Z −→ Z/26Z x 7−→ x+k Par exemple, pour k = 3 : C3(0) = 3, C3(1) = 4... Pour déchiffrer, rien de plus simple ! Il suffit d’aller dans l’autre sens, c’est-à-dire ici de soustraire. La fonction de déchiffrement de César de décalage k est Dk :  Z/26Z −→ Z/26Z x 7−→ x−k En effet, si 1 a été chiffré en 4, par la fonction C3 alors D3(4) = 4 −3 = 1. On retrouve le nombre original. Mathématiquement, Dk est la bijection réciproque de Ck, ce qui implique que pour tout x ∈Z/26Z : Dk Ck(x)
= x En d’autres termes, si x est un nombre, on applique la fonction de chiffrement pour obtenir le nombre crypté y = Ck(x) ; ensuite la fonction de déchiffrement fait bien ce que l’on attend d’elle Dk(y) = x, on retrouve le nombre original x. Z/26Z Z/26Z Ck Dk Une autre façon de voir la fonction de déchiffrement est de remarquer que Dk(x) = C−k(x). Par exemple C−3(x) = x + (−3) ≡x + 23 (mod 26). Voici le principe du chiffrement : Alice veut envoyer des messages secrets à Bruno. Ils se sont d’abord mis d’accord sur une clé secrète k, par exemple k = 11. Alice veut envoyer le message "COUCOU" à Bruno. Elle transforme "COUCOU" en "2 14 20 2 14 20". Elle applique la fonction de chiffrement C11(x) = x + 11 à chacun des nombres : "13 25 5 13 25 5" ce qui correspond au mot crypté "NZFNZF". Elle transmet le mot crypté à Bruno, qui selon le même principe applique la fonction de déchiffrement D11(x) = x −11. ALICE BRUNO COUCOU 2 14 20 2 14 20 13 25 5 13 25 5 NZFNZF COUCOU 2 14 20 2 14 20 13 25 5 13 25 5 NZFNZF Ck Dk CRYPTOGRAPHIE 1. LE CHIFFREMENT DE CÉSAR 4 Exemple 1. Un exemple classique est le "rot13" (pour rotation par un décalage de 13) : C13(x) = x + 13 et comme −13 ≡13 (mod 26) alors D13(x) = x + 13. La fonction de déchiffrement est la même que la fonction de chiffrement ! Exemple : déchiffrez le mot "PRFNE". Notons ici deux points importants pour la suite : tout d’abord nous avons naturellement considéré un mot comme une succession de lettres, et chaque opération de chiffrement et déchiffrement s’effectue sur un bloc d’une seule lettre. Ensuite nous avons vu que chiffrer un message est une opération mathématique (certes sur un ensemble un peu spécial). 1.5. Espace des clés et attaque Combien existe-t-il de possibilités de chiffrement par la méthode de César ? Il y a 26 fonctions Ck différentes, k = 0,1,...,25. Encore une fois, k appartient à Z/26Z, car par exemple les fonctions C29 et C3 sont identiques. Le décalage k s’appelle la clé de chiffrement, c’est l’information nécessaire pour crypter le message. Il y a donc 26 clés différentes et l’espace des clés est Z/26Z. Il est clair que ce chiffrement de César est d’une sécurité très faible. Si Alice envoie un message secret à Bruno et que Chloé intercepte ce message, il sera facile pour Chloé de le décrypter même si elle ne connaît pas la clé secrète k. L’attaque la plus simple pour Chloé est de tester ce que donne chacune des 26 combinaisons possibles et de reconnaître parmi ces combinaisons laquelle donne un message compréhensible. 1.6. Algorithmes Les ordinateurs ont révolutionné la cryptographie et surtout le décryptage d’un message intercepté. Nous montrons ici, à l’aide du langage Python comment programmer et attaquer le chiffrement de César. Tout d’abord la fonction de chiffrement se programme en une seule ligne : Code 1 (cesar.py (1)). def cesar_chiffre_nb(x,k): return (x+k)%26 Ici x est un nombre de {0,1,...,25} et k est le décalage. (x+k)%26 renvoie le reste modulo 26 de la somme (x+k). Pour le décryptage, c’est aussi simple : Code 2 (cesar.py (2)). def cesar_dechiffre_nb(x,k): return (x-k)%26 Pour chiffrer un mot ou un phrase, il n’y a pas de problèmes théoriques, mais seulement des difficultés uploads/S4/ ch-crypto.pdf

Documents similaires

CODES ET CODAGE DE HUFFMAN Un code est un ensemble de mots E sur un alphabet Σ 0 0

Section A : Lexicologie et Sémantique 1. Trouvez 1 exemple pour illustrer le fa 0 0

1 COMME SI…I PARTIE A 1. L’orthographe grammaticale et la morphologie Entourez 0 0

FRANÇAIS DE SPECIALITE 1 2 INTRODUCTION : I. DEFINITION Le langage du droit sus 0 0

chapitre 7 Information et données 4 TD : Découverte de la cryptographie Seul un 0 0

Exemple de demande de travail gratuit Exemple de demande de travail gratuit Exe 0 0

Codes de Hamming AU 2021-2022 66  Code de Hamming (1948): • code linéaire • co 0 0

  Page 14 TD6 : Algorithme, invariant de boucle et complexité (2/2) : Algorit 0 0

MODELE DE LETTRE Lettre de mise en demeure de faire cesser la contrefaçon d'une 0 0

Cours n°1 - Adieu YouNAG Bienvenue dans la cité du crack! ;) J'utiliserai au dé 0 0

• Détails
• Publié le Jui 12, 2022
• Catégorie Law / Droit
• Langue French
• Taille du fichier 3.7271MB