Exercices td cryptographie chiffrement cesar arithmetique cr
Télécharger PDFLe chiffrement de César
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
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 ».
Des chiffres et des lettres
Il est plus facile de manipuler des nombres que des lettres. Nous passons donc à une formulation arithmétique : à chaque lettre de A à Z, nous associons un nombre de 0 à 25. En termes mathématiques, nous définissons une bijection :
A → 0
B → 1
C → 2
...
Z → 25
Par exemple, « ALEA » devient « 0 11 4 0 ». Le chiffrement de César est un cas particulier de substitution mono-alphabétique, c’est-à-dire un chiffrement lettre par lettre. L’intérêt réside dans le fait que cette méthode correspond à une opération mathématique très simple.
Modulo
Soit n > 2 un entier fixé. Définition : 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. Par exemple, 28 ≡ 2 (mod 26), car 28 − 2 est divisible par 26. De même, 85 ≡ 7 (mod 26), car 85 = 3 × 26 + 7.
On note Z/26Z l’ensemble de tous les éléments de Z modulo 26. Cet ensemble peut être représenté par les 26 éléments {0, 1, 2, ..., 25}. En effet, puisque l’on compte modulo 26 : 0, 1, 2, ..., 25, puis 26 ≡ 0, 27 ≡ 1, 28 ≡ 2,... et de même −1 ≡ 25, −2 ≡ 24,...
Plus généralement, Z/nZ contient n éléments. Pour un entier a ∈ Z, son représentant dans {0, 1, 2, ..., n−1} est 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.
L’addition et la multiplication d’entiers se transposent naturellement dans Z/nZ. Par exemple, dans Z/26Z, 15 + 13 ≡ 28 ≡ 2 (mod 26).
Chiffrer et déchiffrer
Le chiffrement de César est une simple addition dans Z/26Z ! Fixons un entier k comme décalage (par exemple, k = 3) et définissons la fonction de chiffrement de César de décalage k :
Ck : Z/26Z → Z/26Z
x → x + k
Par exemple, pour k = 3 : C3(0) = 3, C3(1) = 4, etc.
Pour déchiffrer, il suffit de soustraire. La fonction de déchiffrement de César de décalage k est :
Dk : Z/26Z → Z/26Z
x → x − k
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.
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).
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 ».
Alice transmet le mot crypté à Bruno, qui applique la fonction de déchiffrement D11(x) = x − 11.
Exemple
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 donc la même que la fonction de chiffrement !
Exemple : déchiffrez le mot « PRFNE ».
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, avec k = 0, 1, ..., 25. Le décalage k s’appelle la clé de chiffrement.
Ce chiffrement 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 sans connaître la clé secrète k. L’attaque la plus simple consiste à tester les 26 combinaisons possibles et à reconnaître celle qui donne un message compréhensible.
Algorithmes
Les ordinateurs ont révolutionné la cryptographie. Voici comment programmer et attaquer le chiffrement de César en Python :
Pour chiffrer un nombre :
def cesar_chiffre_nb(x, k):
return (x + k) % 26
Pour déchiffrer un nombre :
def cesar_dechiffre_nb(x, k):
return (x − k) % 26
Pour chiffrer un mot ou une phrase, on utilise les codes ASCII : ord(A) vaut 65, ord(B) vaut 66,... Ainsi, (ord(lettre) − 65) renvoie le rang de la lettre entre 0 et 25.
Le chiffrement de Vigenère
Substitution mono-alphabétique
Le chiffrement de César présente une sécurité faible, car l’espace des clés est trop petit : il y a seulement 26 clés possibles. Au lieu de faire correspondre circulairement les lettres, on associe maintenant à chaque lettre une autre lettre sans ordre fixe ou règle générale.
Exemple :
A → F
B → Q
C → B
D → M
E → X
F → I
G → T
H → E
I → P
J → A
K → L
L → W
M → H
N → S
O → D
P → O
Q → Z
R → K
S → V
T → G
U → R
V → C
W → N
X → Y
Y → J
Z → U
Pour crypter le message « ETRE OU NE PAS ETRE TELLE EST LA QUESTION », on remplace chaque lettre par sa correspondance. Par exemple, E devient X, T devient G, R devient K,... Le message crypté est : « XGKX DR SX OFV XGKX GXWWX XVG WF ZRXVGPDS ».
Pour le décrypter, en connaissant les substitutions, on effectue l’opération inverse.
Avantage : l’espace des clés est gigantesque, avec 26! choix possibles (soit environ 4 × 1026). Inconvénient : la clé à retenir est très longue, et ce protocole reste vulnérable à une attaque statistique.
Attaque statistique
La principale faiblesse du chiffrement mono-alphabétique est qu’une même lettre est toujours chiffrée de la même manière. En français, les lettres les plus fréquentes sont : E, S, A, I, N, T, R, U, L, O, D, C, P, M, V, Q, G, F, H, B, X, J, Y, Z, K, W.
Voici les fréquences approximatives :
E : 14.69%
S : 8.01%
A : 7.54%
I : 7.18%
N : 6.89%
T : 6.88%
R : 6.49%
U : 6.12%
L : 5.63%
O : 5.29%
D : 3.66%
La méthode d’attaque consiste à identifier la lettre la plus fréquente du texte crypté comme le chiffrement du E, la suivante comme celui du S, etc.
Exemple : déchiffrons la phrase « LHLZ HFQ BC HFFPZ WH YOUPFH MUPZH ». On compte les apparitions des lettres : H : 6, F : 4, P : 3, Z : 3. On suppose donc que H crypte E, F crypte S, etc.
Le chiffrement de Vigenère
L’espace des clés du chiffrement mono-alphabétique est immense, mais le fait qu’une lettre soit toujours cryptée de la même façon reste une faiblesse. Le chiffrement de Vigenère remédie à ce problème en regroupant les lettres par blocs.
Par exemple, le message « CETTE PHRASE NE VEUT RIEN DIRE » est divisé en blocs de 4 lettres : « CETT EPHR ASEN EVEU TRIE NDIR E ». Si k est la longueur d’un bloc, on choisit une clé composée de k nombres de 0 à 25 : (n1, n2, ..., nk).
Le chiffrement consiste à appliquer un décalage de César variable selon la position dans le bloc :
• un décalage de n1 pour la première lettre de chaque bloc,
• un décalage de n2 pour la deuxième lettre de chaque bloc,
• ...
• un décalage de nk pour la k-ème lettre de chaque bloc.
Exemple : pour la clé (3, 1, 5, 2), le bloc « CETT » devient « FFYV ».
Mathématiques
La fonction de chiffrement associe à un bloc de longueur k un autre bloc de longueur k :
Cn1,n2,...,nk : Z/26Z × Z/26Z × ... × Z/26Z → Z/26Z × Z/26Z × ... × Z/26Z
(x1, x2, ..., xk) → (x1 + n1, x2 + n2, ..., xk + nk)
La fonction de déchiffrement est C−n1,−n2,...,−nk.
Espace des clés et attaque
Pour des blocs de longueur k, il y a 26k clés possibles. Pour k = 4, cela donne 456 976 combinaisons. Cependant, si deux lettres A sont situées à la même position dans deux blocs différents, elles seront cryptées de la même manière. Une attaque consiste donc à regrouper les lettres par position dans les blocs et à appliquer une attaque statistique sur chaque regroupement.
Algorithmes
Voici un algorithme pour calculer la fréquence des lettres dans une phrase :
def statistiques(phrase):
liste_stat = [0 for x in range(26)]
for lettre in phrase:
i = ord(lettre) − 65
if 0 <= i < 26:
liste_stat[i] += 1
return liste_stat
Voici le chiffrement de Vigenère :
def vigenere(mot, cle):
message_code = []
k = len(cle)
i = 0
for lettre in mot:
nomb = ord(lettre) − 65
nomb_code = (nomb + cle[i]) % 26
lettre_code = chr(nomb_code + 65)
i = (i + 1) % k
message_code.append(lettre_code)
message_code = "".join(message_code)
return message_code
La machine Enigma et les clés secrètes
Un secret parfait
Les chiffrement précédents sont vulnérables aux attaques statistiques, car une même lettre est régulièrement chiffrée de la même façon. Pour créer un chiffrement parfait, il faut changer la correspondance à chaque lettre.
Exemple : Alice veut envoyer à Bruno le message « ATTAQUE LE CHATEAU ». Elle choisit une clé secrète C de même longueur que le message, composée d