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 o u
permutation e n 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 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 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 MR P W WP N MA 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 retrouver M), il vous faut appliquer une opération différente,
utilisant la clé privée (d,n) :
Cd modulo n
– Et c’est là que les maths des nombres premiers nous sont utiles, car elles permettent de
prouver que ça marche c’est-à-dire que l’opération de décodage permet effectivement bien
de retrouver le message M initial. On peut en effet démontrer que :
Cd ≡ M [n]
Par exemple, Alice veut envoyer M = 3 à Bob. Elle code à l'aide de la clé publique (3, 10) :
33 = 27 ≡ 7 [10]
Le code à envoyer est C = 7. Bob reçoit le message codé C, il décode avec sa clé privée (7, 10) :
77 = 823543 ≡ 3 [10]. Il retrouve bien le message initial M = 3.
Le chiffrement RSA est très utilisé aujourd'hui pour sécuriser le commerce électronique et plus
généralement les échanges des données confidentielles sur internet, y compris les transactions
bancaires. Il représente une très grande sécurité, offerte par les mathématiques : si on veut
casser le codage, il faudrait retrouver la clé privée à partir de la clé publique, donc
essentiellement à décomposer n en nombres premiers. Alors qu'il n'existe pas d'algorithme
efficace de factorisation en nombre premier : le meilleur algorithme aujourd'hui a toujours une
complexité exponentielle (le temps d'exécution augmente en exponentielle avec le nombre à
décomposer).
Toutefois, Peter Shor, mathématicien américain, a publié un papier en 1994 dans lequel il a
prouvé qu'avec des ordinateurs quantiques, il existe un algorithme (algorithme de Shor ) qui
permet de casser le cryptage RSA de manière très efficace. En effet, les ordinateurs quantiques,
grâce à leurs spécificités, arrivent à trouver les facteurs premiers d'un nombre beaucoup plus
rapidement que nos ordinateurs d'aujourd'hui. Heureusement, le plus grand nombre qu'un
ordinateur quantique a réussi à factoriser est 143 (143 = 11*13) ... On a encore de la marge.
Néanmoins, le développement des ordinateurs quantiques devient un grand défi de la sécurité
informatique.
Inspiré de la vidéo « Les codes secrets » de la chaîne Youtube S cience étonnante
https://www.youtube.com/watch?v=8BM9LPDjOw0&t=446s
ttps://www.dcode.fr/
Découvrez d’autres codes et leur decodage sur h
