Remarque : nous aurons besoin de votre fonction algoeucli() du TP1. Pensez à la copier-coller dans ce notebook.
Nous utiliserons lors de ce TP la correspondance Lettre-Nombre suivante (en modulo 26) :
| 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 |
Pour ce faire, nous allons avoir besoin de la chaîne de caractères suivante :
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpha(m) qui fait à correspondre à un message numérique m (donné sous forme de liste) le message alphabétique correspondant (sous forme de chaîne de caractères).Exemple :
alpha([18,0,11,20,19])
'SALUT'
num(m) qui fait correspondre à un message alphabétique m le message numérique correspondant.Exemple :
num("SALUT")
[18, 0, 11, 20, 19]
Le chiffrement affine repose sur des calculs dans $(\mathbb{Z} /{26} \mathbb{Z})$. La clé $k$ est formée d'un couple ($\bar a$, $\bar b$) où $\bar a$ est inversible, d'inverse $(\bar a)^{-1}$.
Fonction de chiffrement : $e_{k}( \bar m) = \bar a \times \bar m + \bar b$
Fonction de déchiffrement : $d_{k}( \bar c) = (\bar a)^{-1} \times (\bar c-\bar b)$
chiffre(m,a,b) permettant de chiffrer un mot m à l'aide de la clé ($\bar a$, $\bar b$).Exemple :
chiffre("IUT", 3, 2)
# Explication : "I" donne 8, qui se chiffre en 26 (=3*8+2), et 26 donne "A".
'AKH'
inverse(x,n) qui renvoie l'inverse de $\bar x$ modulo n s'il existe (dans le cas contraire, renvoyer un message d'erreur)Exemple :
inverse(3,26)
9
inverse(4,26)
'pas inversible'
dechiffre(c,a,b) permettant de déchiffrer un message codé c.Exemple :
dechiffre("AKH",3,2)
'IUT'
c="EYCPRTYDWYNWTWQPRJWIQPRUIOTYCZZYQWOOYJFWHUYTUPRWKCJJWJ"
La cryptanalyse regroupe les techniques permettant de déchiffrer des messages codés sans disposer de la clé de chiffrement. L'analyse fréquentielle est une de ces techniques. Elle consiste à examiner la fréquence des lettres employées dans un message chiffré, et à la comparer avec la fréquence "théorique".
En français, la répartition "théorique" des lettres est la suivante (en %) :
| 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 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 9.42 | 1.02 | 2.64 | 3.39 | 15.87 | 0.95 | 1.04 | 0.77 | 8.41 | 0.89 | 0.0 | 5.34 | 3.24 | 7.15 | 5.14 | 2.86 | 1.06 | 6.46 | 7.90 | 7.26 | 6.24 | 2.15 | 0.0 | 0.3 | 0.24 | 0.32 |
Soit un message chiffré suivant : message
frequence(c) qui renvoie une liste contenant la fréquence de chacunes des lettres de l'alphabet dans un message c. Le 1er élement de la liste contiendra la fréquence d'apparition de A, le deuxième la fréquence de B, etc.Exemple :
print(frequence(message))
[5.88, 4.55, 0.0, 0.38, 8.73, 1.52, 1.14, 7.02, 0.57, 2.09, 0.0, 7.78, 2.09, 0.38, 1.9, 0.57, 9.68, 5.31, 7.4, 3.42, 0.0, 5.5, 4.74, 0.0, 19.17, 0.19]
D'après la question précédente, en quoi la lettre $E$ a été chiffrée ? Et la lettre $A$ ? Quelle hypothèse peut-on alors faire sur la valeur de la clé ($\bar a$, $\bar b$) ? Essayer de déchiffrer le message en utilisant cette clé.
Faire une autre hypothèse sur le chiffrement de la lettre $A$. Quelle serait alors la valeur de la clé ($\bar a$, $\bar b$) ?
Déchiffrer le message.