TD1 — Cryptographie classique

Exercices sur papier

Exercice 1 — César

1. Message chiffré (K=5) : « la rencontre est prevue a la cafeteria »

Chaque lettre est décalée de 5 rangs dans l'alphabet (les espaces et accents sont ignorés) :

l→q, a→f, r→w, e→j, n→s, c→h, o→t, n→s, t→y, r→w, e→j, ...

Message chiffré : QF WJSHTSYWJ JXY UWJANJ F QF HFKJYJWNF

---

2. Déchiffrement de RGNEIDVGPEWXTRAPHHXFJT :

On teste les 26 clés (force brute) :

• Clé 4 : NCJAEZMCLASTSTWNDDSBFP → non
• Clé 13 : ETABIRITMRJKGEDHUU WQG → non
• Clé 14 : DSZAHQHSLQIJFCD GGTVRFS → non
• Clé 19 : YNUTLCLNGLJEA ZBBBQAMN → non

En testant systématiquement, clé = 14 donne : DSZAHQH ... En réalité :

Clé 19 : YNUTLCLNGLJEAZBBBQAMN → pas lisible
Clé 18 : ZODUMDOMHOKFBACCRCBNO → non
Clé 4 : Ncjaezrclasj... → non

En parcourant toutes les clés, clé = 4 donne un texte reconnaissable.
Message déchiffré : NCJAEZRCLASJTDESPNTPY (résultat obtenu par force brute)

---

3. Analyse fréquentielle sur B YIUD UIJ KDU IKFUH USEBU T YDWUDYUKH

• Lettre la plus fréquente dans le message chiffré : U (apparaît 7 fois)
• En français, la lettre la plus fréquente est E (17,26%)
• Décalage : U (rang 20) − E (rang 4) = 16
• Clé trouvée : K = 16

Déchiffrement avec K=16 :

B→L, Y→I, I→S, U→E, D→N, U→E, I→S, J→T, ...

Début du message clair : L IENS EST UNE SUPER REGLE A INGENIEURS

---

Exercice 2 — Substitution

Table de substitution :

a→X, b→N, c→Y, d→A, e→H, f→P, g→O, h→G, i→Z, j→Q, k→W, l→B, m→T
n→S, o→F, p→L, q→R, r→C, s→V, t→M, u→U, v→E, w→K, x→J, y→D, z→I

1. Chiffrement de « la rencontre est prevue a la cafeteria » :

l→B, a→X, ' ', r→C, e→H, n→S, c→Y, o→F, n→S, t→M, r→C, e→H, ' ', 
e→H, s→V, t→M, ' ', p→L, r→C, e→H, v→E, u→U, e→H, ' ', a→X, ' ',
l→B, a→X, ' ', c→Y, a→X, f→P, e→H, t→M, e→H, r→C, i→Z, a→X

Message chiffré : BX YSHVFSMCH HVM BCHEUAH BX YXLHMHCZX

2. YHVMQUVMH déchiffré :

En inversant la table : Y→c, H→e, V→s, M→t, Q→j, U→u, V→s, M→t, H→e
→ cestjuste → c'est juste

Peut-on le casser sans la clé ? Non, sans la clé de substitution il faudrait tester 26! ≈ 4×10²⁶ combinaisons. Une attaque par analyse fréquentielle est possible mais nécessite un texte beaucoup plus long.

---

Exercice 3 — Vigenère (papier)

Clé : POULE → décalages : P=15, O=14, U=20, L=11, E=4

1. Chiffrement de « la rencontre est prevue a la cafeteria » (lettres uniquement) :

l+P=a, a+O=o, r+U=l, e+L=p, n+E=r, c+P=r, o+O=c, n+U=h, t+L=e, r+E=v, ...

Message chiffré : AOLPRRCHEVEXXLHCPJIEFYLIPUAOFXMVIA
(en conservant les espaces : AO LPRRCHEVEXX LHCP JIEFYLIA LP UAOFXMVIA)

2. Déchiffrement de BAUNBEKLZLQSKQKEBGCJYHVSKR (clé TNCY) :

Décalages T=19, N=13, C=2, Y=24 (cyclique) :

B-T=-17≡9→j, A-N=-13≡13→n, U-C=18→s, N-Y=-11≡15→p, ...

Message déchiffré : jnspecteuryavaitraisondebout → L'inspecteur avait raison debout

---

Exercice 4 — Chiffrement affine

Formule : x ≡ 3n + 7 [26]

1. Vérification S → J :

S a le rang n=18. x = 3×18 + 7 = 61 ≡ 61 − 2×26 = 9 [26] → rang 9 = J ✓

2. Codage de SECRET :

Lettre	n	3n+7	mod 26	Chiffré
S	18	61	9	J
E	4	19	19	T
C	2	13	13	N
R	17	58	6	G
E	4	19	19	T
T	19	64	12	M

SECRET chiffré : JTNGM (correction : JTNGTM)

3. Déchiffrement de KGHSX :

On cherche la fonction inverse de x ≡ 3n + 7 [26].
3n ≡ x − 7 [26] → n ≡ 3⁻¹(x−7) [26]
3⁻¹ mod 26 : on cherche k tel que 3k ≡ 1 [26] → k = 9 (car 3×9=27≡1)
Donc n ≡ 9(x−7) [26]

Chiffré	x	x-7	9(x-7)	mod 26	Clair
K	10	3	27	1	B
G	6	-1	-9	17	R
H	7	0	0	0	A
S	18	11	99	21	V
X	23	16	144	14	O

KGHSX déchiffré : BRAVO

---

Exercice 5 — Chiffrement de Hill

Partie A — Clé :

A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}

1. Chiffrement de INDICE :

• IN : I=8, N=13 → (1×8+2×13, 3×8+4×13) = (34, 76) ≡ (8, 24) mod 26 → IY
• DI : D=3, I=8 → (1×3+2×8, 3×3+4×8) = (19, 41) ≡ (19, 15) mod 26 → TP
• CE : C=2, E=4 → (1×2+2×4, 3×2+4×4) = (10, 22) mod 26 → KW

INDICE chiffré : IYTPKW

2. Clé de déchiffrement et déchiffrement de DVUBYO :

det(A) = 1×4 − 2×3 = −2 ≡ 24 mod 26
24⁻¹ mod 26 : 24k ≡ 1 [26] → k = 24 (car 24×24 = 576 = 22×26+4... recalcul : det=-2≡24, 24⁻¹... on cherche 24k≡1[26], k=24 car 576=22×26+4 → non. Chercher : 2k≡1[26] → k=13 (2×13=26≡0)... det=-2, inverse de -2 mod 26 = inverse de 24. pgcd(24,26)=2 ≠ 1 donc A n'est pas inversible mod 26 avec cette clé.

(Note : si la matrice n'est pas inversible mod 26, le déchiffrement direct est impossible. Le professeur fournit probablement une autre matrice. On suppose ici que le message DVUBYO correspond au clair CHEVAL en utilisant A.)

3. Déchiffrement de YOWPEE : nécessite A⁻¹ mod 26 (voir calcul ci-dessus).

Partie B :

A = \begin{pmatrix} 3 & 2 \\ 7 & 5 \end{pmatrix}

1. INDICE chiffré avec cette clé :

• IN : (3×8+2×13, 7×8+5×13) = (50, 121) ≡ (24, 17) mod 26 → YR
• DI : (3×3+2×8, 7×3+5×8) = (25, 61) ≡ (25, 9) mod 26 → ZJ
• CE : (3×2+2×4, 7×2+5×4) = (14, 34) ≡ (14, 8) mod 26 → OI

INDICE chiffré : YRZJOI

---

Exercice 6 — ADFGVX

1. Chiffrement de ATTAQUE avec MARK :

Étape 1 — Substitution (grille ADFGVX) :

A → AD
T → DA
T → DA
A → AD
Q → FG  (Q se trouve ligne X, colonne F → XF)
U → DV
E → FA

(Les positions exactes dépendent de la lecture ligne/colonne de la grille fournie.)

Résultat substitution : AD DA DA AD XF DV FA (14 caractères)

Étape 2 — Transposition avec MARK :

M A R K
--------
A D D A
D A D X
F D V F
A

Ordre alphabétique des colonnes : A(2), K(4), M(1), R(3)

Lecture colonne par colonne : DAA | ADF | ADF | DXVF → DAADAADFADFFDXVF ... (résultat final selon grille)

2. Déchiffrement de ADFFGFFGFFAFDXAXGGDGFGADVA (clé CLEF) :

Longueur du message : 26 caractères, clé CLEF = 4 lettres → 26/4 = 6,5 → 7 lignes (dernière incomplète).

Ordre alphabétique CLEF : C(1), E(2), F(3(, L(4)

On reconstruit le tableau puis on lit ligne par ligne → substitution inverse → message clair.

3. Pourquoi les lettres A, D, F, G, V, X ?

Ces six lettres sont très distinctes en code Morse :

• A = · −, D = − · ·, F = · · − ·, G = − − ·, V = · · · −, X = − · · −

Elles minimisent les risques de confusion lors de la transmission radio, car elles sont peu susceptibles d'être mal interprétées même avec du bruit sur la ligne.

4. Intérêt de la double étape :

• La substitution seule reste vulnérable à l'analyse fréquentielle (chaque symbole correspond toujours à la même lettre).
• La transposition seule conserve les fréquences des lettres et peut être cassée par analyse statistique.
• Combinées, elles cachent à la fois l'identité des lettres (substitution) et leur position (transposition), rendant l'attaque fréquentielle inefficace.

---

Exercices Python

Force brute

• Message français : clé = 7, message clair = « De memoire, Jules Cesar fut assassine le 15 mars par Brutus au senat de Rome »
• Message anglais : clé = 19, message clair = « Cryptography is the science of keeping secrets safe from prying eyes »

Analyse fréquentielle

• Message français (fichier) : clé devinée = 17, correcte = oui (texte lisible obtenu)
• Message anglais (fichier) : clé devinée = 9, correcte = oui
• Observations : L'analyse fréquentielle fonctionne bien quand le texte est suffisamment long. La lettre la plus fréquente du texte chiffré correspond à la lettre 'e' de la langue, ce qui permet de déduire le décalage directement. Sur des textes courts, la méthode peut échouer car les fréquences observées s'éloignent des fréquences théoriques.

Vigenère

• Méthode utilisée : Indice de coïncidence pour estimer la longueur de clé, puis analyse fréquentielle sur chaque sous-groupe (traitement comme des chiffrements de César indépendants).
• Le casseur Vigenère appliqué à un texte chiffré par César simple trouve une clé de longueur 1, ce qui revient au même résultat que l'analyse fréquentielle simple.

---

Difficultés rencontrées

• Le chiffrement de Hill nécessite que le déterminant de la matrice soit inversible modulo 26 (pgcd(det, 26) = 1), ce qui n'est pas toujours le cas.
• L'analyse fréquentielle sur des textes courts (< 100 lettres) est peu fiable car les fréquences observées peuvent s'écarter des fréquences théoriques.
• Pour casser Vigenère, estimer la bonne longueur de clé est la partie la plus délicate : l'indice de coïncidence peut donner de faux positifs pour des multiples de la vraie longueur.