Remerciez-le!

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

Comment devenir un agent secret ? --une introduction à la cryptographie Introdu

Comment devenir un agent secret ? --une introduction à la cryptographie Introduction : La cryptographie est la science du codage des messages. En effet, il est fréquent qu’une personne (appelons la Alice) cherche à communiquer avec une deuxième personne (prénommée Bob) sans qu’une troisième (Carl) ne puisse lire les messages envoyés. Il existe une très grande variété de manières de réaliser ce codage, dont les plus performantes font appel à des mathématiques de haut vol. I. Chiffrement par décalage ou code César 1. Codage La légende raconte que César inventa un système pour communiquer avec ses généraux pendant la guerre des Gaules. Le code utilisé par César consistait en un décalage de l’alphabet de trois lettres vers la gauche : un D devient un A, un E devient un B, etc... On peut résumer ceci dans un tableau : 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 Après cette première formation, vous, nos nouveaux agents secrets de CIA, serez envoyés à l'époque de la guerre des Gaules par une machine de temps. Cela sera votre premier entraînement. Vous êtes maintenant des généraux de César. Essayez de communiquer vos informations avec César, sans que les Gaulois connaissent vos messages. a. Coder le message : CEUX QUI VONT DECODER TE SALUENT b. Vous avez reçu un message de César YHQL YLGL YLFL. Déchiffrer-le →Le code de César est un chiffrement par décalage: en effet, on décale les lettres de l'alphabet. Mais au lieu de décaler 3 lettres vers la gauche, on peut faire autre décalage, par exemple 2 lettres vers la droite, 5 lettres vers la gauche. c. Ecrire un message à quelqu’un en lui donnant la clé de chiffrage 2. Comment casser un chiffrement par décalage ? En tant qu'agent secret, votre mission n'est pas seulement de coder un message pour l'envoyer, décoder le message envoyé par un autre agent. Vous avez une autre mission très importante : décrypter les messages des ennemis que vous avez interceptés, en sachant qu'ils utilisent un codage que vous ignorez a priori. Général de César ! Nous avons intercepté un message des Gaulois : RM XMCF B’MVDWGMZ LM TI XWBQWV UIOQYCM LMUIQV. La seule chose que nous savons c'est que ce message est écrit en français, et le codage est un chiffrement par décalage. 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 II. Chiffrement par substitution Le chiffrement par décalage est en fait très facile à casser : il suffit de tester les 26 possibilités de décalage (un ordinateur peut le faire en un millième de seconde). Pour améliorer ceci, il faut augmenter considérablement le nombre de possibilités. Pour se faire, on peut utiliser le chiffrement par substitution. Le chiffrement par substitution consiste à remplacer une lettre par une lettre quelconque. Par contre, chaque lettre cryptée doit correspondre à une seule lettre en clair. Autrement dit, deux lettres en clair ne peuvent avoir la même lettre cryptée. On parle d'une bijection ou permutation en mathématiques. a. Combien y a-t-il de substitutions possibles ? Est-il possible de casser un chiffrement par substitution en testant toutes les possibilités ? (on parle d'une attaque par force brute) b. Comment peut-on casser un chiffrement par substitution ? III. Un outil mathématique : modulo On vient de voir qu’il était assez simple - mais vite laborieux - de coder ou décoder des messages. C’est pourquoi on aime bien utiliser des algorithmes pour le faire à notre place. Ceci nécessite toutefois d’être capable de traduire mathématiquement le processus. Pour cela, nous utilisons une opération appelée modulo. Vous l’avez déjà un peu rencontrée en trigonométrie, lorsque vous dites que 3π ≡π[2π]. Vous l’utilisez également pour compter les heures : nous disons indifféremment "il est 14h" ou "il est 2h". En fait, de manière générale, on dira a ≡b[n] (se lit "a est congru à b modulo n) lorsque b −a est un multiple de n, c’est-à-dire qu’on passe de a à b en ajoutant ou soustrayant un certain nombre de fois n. Autrement dit, a et b ont le même reste par division euclidienne par n. a. Les égalités suivantes sont-elles vraies ? 1)10 ≡ 1[3] 2) 14 ≡ 5[6] 3) 72 ≡ 0[12] 4) 50 ≡ 24[26] b. Calculer : 1) 23+7 ≡ [5] 2) 53-2 ≡ [7] 3) 9*8 ≡ [3] 4) 5*9 ≡ [2] Pour transcrire mathématiquement le chiffrement, on commence par transformer chaque lettre du message en un nombre ("A" devient "0", "B" devient "1", etc...). Ensuite, on soustrait 3 à chaque nombre (pour décaler de 3), mais on le fait modulo 26 de manière à toujours rester entre 0 et 25. On traduit ensuite chaque nombre en lettre ("0" devient "A", etc...) et on obtient le message codé. Lettre 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 Transcription 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 c. Coder le message "ABSCISSE" avec ce procédé. d. Comment fait-on pour décoder mathématiquement le code de César ? IV. Cryptographie symétrique – Code de Vigenère Nous avons vu que le chiffrement par substitution est vulnérable par un attaque d'analyse des fréquences, car une lettre est toujours représentée par la même lettre. Si au contraire, une lettre est codée différemment au sein d'un même texte, le codage est alors incassable par cette attaque. Le code de Vigenère est un raffinement du code de César. Il utilise un décalage qui varie d’une lettre codée à l’autre. Ce décalage variable est défini grâce à ce qu’on appelle une clé. Voici le fonctionnement du code : on choisit par exemple le mot SCIENCE comme clé, avec laquelle on code le message JE TIENS ENFIN LA GAULE. On écrit la clé sous le message, en répétant si nécessaire, de sorte que chaque lettre du message correspond à une lettre de clé. On décale ensuite la lettre du message du nombre correspondant à la lettre de clé en dessous. Message : J E T I E N S E N F I N L A G A U L E Clé : S C I E N C E S C I E N C E S C I E N Code : B G B M R P W W P N M A N E Y C C P R a. Avec la clé TREMPLIN, coder le message J'AIME LA CRYPTO. Vous pouvez utiliser la transcription mathématique et les calculs avec modulo pour vous aider. b. Comment décode-t-on un message crypté par le code de Vigenère en connaissant la clé ? c. Quels sont les avantages du code de Vigenère par rapport aux chiffrements par décalage et par substitution ? d. quels sont les inconvénients du code de Vigenère ? V. Cryptographie asymétrique – chiffrement RSA Nous venons de voir un exemple de codage avec une clé, qui permet de chiffrer un message et de déchiffrer un message. L'inconvénient de ce type de chiffrement est que si on réussit à voler la clé, on arrivera alors à déchiffrer tous les messages. En 1977, Ronald Rivest, Adi Shamir et Leonard Adleman, trois chercheurs du Massachusetts Institute of Technology (MIT) ont inventé un algorithme de chiffrement asymétrique. Alice crée deux clés : une clé publique qu'elle donne à Bob pour qu'il code le message pour envoyer à Alice, qui garde une clé privée qui lui permet de déchiffrer le message. Le chiffrement RSA fonctionne de la manière suivante : – Choisissez deux nombres premiers p et q (que vous gardez pour vous), prenons par exemple p=3 et q=11. – Fabriquez le produit des deux n=p*q, dans notre cas n=33. – Choisissez un nombre e n’ayant pas de facteur premier commun avec (p-1)*(q-1). Dans notre cas, puisque (p-1)*(q-1) =1*4 = 4 = 2*2, on peut choisir par exemple e = 3. – La paire (e,n) constitue la clé publique, que vous donnez à votre ambassadeur. – Choisissez ensuite un nombre d tel e*d ≡1 [(p-1)*(q-1)] par exemple dans notre cas d = 7 fait l’affaire car 3*7 ≡ 1 [4] – La paire (d,n) constitue la clé privée, que surtout vous gardez pour vous. – Comment se passe la procédure d’encodage ? Tout d’abord il vous faut ramener votre message à un nombre. Vous pouvez le faire par le moyen que vous voulez comme A=0 ; B=1 ; ... ; Z =25 par exemple. Une fois votre message traduit sous la forme d’un nombre M vous allez encoder ce nombre avec la clé publique (e,n) de la manière suivante : C ≡ Me[n] – Pour décoder C (et donc uploads/S4/ cryptographie-vsg.pdf