TD1 — Cryptographie classique : Cesar & analyse frequentielle

Duree : 2h

Prerequis : CM1 — Histoire & fondamentaux Rendu : depot Forgejo

Objectifs

• Maitriser les chiffrements classiques (Cesar, substitution, Vigenere, affine, Hill, ADFGVX)
• Implementer chiffrement/dechiffrement de Cesar
• Attaque par force brute
• Analyse frequentielle

Fichiers du projet

Telecharger le scaffolding (td1-template.zip)

td1/
├── README.md          # template a remplir
├── cesar.py           # chiffrer / dechiffrer
├── force_brute.py     # attaque_force_brute
├── freq.py            # calculer_frequences / deviner_cle
├── messages/
│   ├── message_fr.txt # message francais chiffre (cle inconnue)
│   └── message_en.txt # message anglais chiffre (cle inconnue)
└── vigenere.py        # chiffrer_vigenere / casser_vigenere

---

Exercices sur papier

A la main

Les exercices de cette section sont a realiser sur papier, sans ordinateur.

Exercice 1 — Chiffrement par decalage (Cesar)

1. Chiffrer le message « la rencontre est prevue a la cafeteria » a l'aide du chiffrement par decalage et de la cle K = 5.

2. Decrypter le message « RGNEIDVGPEWXTRAPHHXFJT » sachant qu'il a ete cree par un chiffrement par decalage.

3. Dans un texte en francais les lettres les plus frequentes sont le A (8.4%) et le E (17.26%). Sachant que le message est en francais, chiffre en utilisant le chiffrement par decalage sur les 26 lettres de l'alphabet, determiner la clef et decrypter le debut du message :

B YIUD UIJ KDU IKFUH USEBU T YDWUDYUKH

---

Exercice 2 — Chiffrement par substitution

1. Chiffrer le message « la rencontre est prevue a la cafeteria » a l'aide du chiffrement par substitution et de la cle suivante :

a	b	c	d	e	f	g	h	i	j	k	l	m
X	N	Y	A	H	P	O	G	Z	Q	W	B	T

n	o	p	q	r	s	t	u	v	w	x	y	z
S	F	L	R	C	V	M	U	E	K	J	D	I

1. Est-il possible de decrypter le message « YHVMQUVMH » chiffre par un chiffrement par substitution sans connaitre la cle ? Dechiffrer ce message sachant qu'il a ete cree avec la cle precedente.

---

Exercice 3 — Chiffrement de Vigenere

Ici la lettre « A » correspond a un decalage de 0.

1. Chiffrer le message « la rencontre est prevue a la cafeteria » a l'aide de la methode de Vigenere et du mot cle POULE.

2. Est-il possible de decrypter le message « BAUNBEKLZLQSKQKEBGCJYHVSKR » chiffre par un chiffrement de Vigenere sans connaitre la cle ? Dechiffrer ce message sachant qu'il a ete cree a l'aide du mot cle TNCY.

---

Exercice 4 — Chiffrement affine

Pour coder un message, on peut proceder de la facon suivante : chaque lettre du message munie de son numero d'ordre n est remplacee par la lettre de l'alphabet munie du numero d'ordre x (x ∈ [0 … 25]) obtenu a l'aide de la formule x ≡ 3n + 7 [26].

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

1. Verifier qu'avec ce chiffrement, le S est remplace par J.
2. Coder le mot SECRET.
3. Dechiffrer le message suivant : KGHSX

---

Exercice 5 — Chiffrement de Hill

Le chiffrement de Hill utilise des matrices comme cle de chiffrement. Le message est decoupe en paires de lettres, chaque paire est convertie en un vecteur de deux nombres, puis multipliee par la matrice cle. Tous les calculs se font modulo 26.

On associe a chaque lettre de l'alphabet un entier de l'ensemble E = {0, 1, 2, ..., 25} suivant le tableau ci-dessous :

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

Principe du chiffrement :

Pour chiffrer une paire de lettres \((l_1, l_2)\) de numeros \((x_1, x_2)\) avec la matrice cle \(A\) :

\[\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = A \times \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \mod 26\]

Les nombres \(y_1\) et \(y_2\) sont ensuite reconvertis en lettres.

Exemple : chiffrer « OK » avec la matrice identite

O = 14, K = 10. Avec \(A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) :

\[\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \times \begin{pmatrix} 14 \\ 10 \end{pmatrix} = \begin{pmatrix} 14 \\ 10 \end{pmatrix} \mod 26 = \begin{pmatrix} 14 \\ 10 \end{pmatrix}\]

Resultat : O, K → OK (la matrice identite ne chiffre rien, logique !)

Exemple : chiffrer « HI » avec \(A = \begin{pmatrix} 3 & 2 \\ 1 & 5 \end{pmatrix}\)

H = 7, I = 8.

\[\begin{pmatrix} 3 & 2 \\ 1 & 5 \end{pmatrix} \times \begin{pmatrix} 7 \\ 8 \end{pmatrix} = \begin{pmatrix} 3 \times 7 + 2 \times 8 \\ 1 \times 7 + 5 \times 8 \end{pmatrix} = \begin{pmatrix} 37 \\ 47 \end{pmatrix}\]

Modulo 26 : \(37 \mod 26 = 11\) = L, \(47 \mod 26 = 21\) = V.

Resultat : HI → LV

Pour dechiffrer, on utilise la matrice inverse de A (calculee modulo 26). C'est la que les choses se compliquent...

---

Partie A : On se donne pour cle de chiffrement la matrice :

\[A = \begin{pmatrix} 2 & 5 \\ 1 & 3 \end{pmatrix}\]

On va chiffrer dans la suite le mot INDICE a l'aide de la grille ci-dessus.

1. Chiffrer le mot INDICE en utilisant la cle A. (Decouper en paires : IN, DI, CE)
2. On souhaite a present retrouver le message clair correspondant au message chiffre DVUBYO. En deduire la cle de dechiffrement (message clair associe au texte chiffre).
3. Dechiffrer le message YOWPEE.

Partie B : On se donne maintenant pour cle la matrice :

\[A = \begin{pmatrix} 9 & 5 \\ 4 & 7 \end{pmatrix}\]

1. Chiffrer le mot INDICE avec cette cle.
2. Soit la matrice \(M = \begin{pmatrix} 7 & -5 \\ -4 & 9 \end{pmatrix}\). Calculer le produit MA et en deduire que A est inversible. On appellera B la matrice inverse de A.
3. Expliquer pourquoi l'utilisation de la cle B ne permet pas de dechiffrer le message HTPQMK.
4. Verifier que l'utilisation de la matrice C = 23M permet le dechiffrage du message HTPQMK.

---

Exercice 6 — Chiffrement ADFGVX

Le chiffrement ADFGVX est un systeme utilise par l'armee allemande durant la Premiere Guerre mondiale. Il combine une substitution (via une grille 6×6) et une transposition (via un mot cle).

Etape 1 — Substitution : On utilise la grille suivante, ou chaque lettre ou chiffre est remplace par un couple de lettres parmi {A, D, F, G, V, X} :

	A	D	F	G	V	X
A	N	A	1	C	3	H
D	8	T	B	2	O	M
F	E	5	V	R	I	S
G	D	U	F	X	G	Y
V	0	P	L	W	7	6
X	J	9	Q	Z	4	K

Par exemple, la lettre E se trouve a l'intersection de la ligne F et de la colonne A, donc E → FA.

Etape 2 — Transposition : On utilise le mot cle MARK. On ecrit le resultat de la substitution sous le mot cle (ligne par ligne), puis on reordonne les colonnes par ordre alphabetique du mot cle. Le message chiffre final se lit colonne par colonne (de haut en bas, de gauche a droite) dans le tableau reordonne.

Exemple detaille avec le mot « TE »

Substitution : T → DD, E → FA → resultat : DDFA

Transposition avec la cle MARK (4 colonnes) :

On ecrit les caracteres ligne par ligne sous le mot cle :

M	A	R	K
D	D	F	A

On reordonne les colonnes dans l'ordre alphabetique (A, K, M, R) :

A	K	M	R
D	A	D	F

On lit colonne par colonne, de haut en bas, de gauche a droite : DADF

Questions :

1. Chiffrer le message « ATTAQUE » avec la grille ci-dessus et le mot cle MARK.

??? tip "Indication pour l'etape de substitution" Chaque lettre est remplacee par un couple de deux lettres parmi {A, D, F, G, V, X} en utilisant la grille. Le premier caractere du couple correspond a la ligne, le second a la colonne. Exemple : A se trouve ligne A, colonne D → A devient AD.

??? tip "Indication pour l'etape de transposition" Ecrire le resultat de la substitution (14 caracteres) ligne par ligne sous les lettres du mot cle MARK (4 colonnes), puis reordonner les colonnes dans l'ordre alphabetique : A, K, M, R. Attention : la derniere ligne peut etre incomplete. Lire ensuite colonne par colonne.

1. On recoit le message chiffre suivant : ADFFGFFGFFAFDXAXGGDGFGADVA. Le mot cle est CLEF. Dechiffrer ce message.

2. Pourquoi l'armee allemande a-t-elle choisi les lettres A, D, F, G, V, X pour ce chiffrement ? (Indice : pensez au code Morse et a la transmission radio.)

3. En quoi la double etape (substitution + transposition) rend-elle ce chiffrement plus resistant que chacune des deux techniques utilisee seule ?

---

Exercices de programmation (Python)

Programmation

Les exercices suivants sont a realiser en Python sur machine.

---

Partie 1 — Chiffrement de Cesar

Fichier : cesar.py

def chiffrer(texte: str, cle: int) -> str:
    """
    Chiffre un texte avec le chiffre de Cesar.
    - Seules les lettres sont chiffrees, le reste est conserve.
    - La casse est preservee.
    - La cle peut etre negative ou > 26.
    """
    pass

def dechiffrer(texte: str, cle: int) -> str:
    """
    Dechiffre un texte chiffre avec le chiffre de Cesar.
    """
    pass

Tests a passer :

assert chiffrer("Hello World!", 3) == "Khoor Zruog!"
assert dechiffrer("Khoor Zruog!", 3) == "Hello World!"
assert chiffrer(dechiffrer("Test", 13), 13) == "Test"

---

Partie 2 — Force brute

Fichier : force_brute.py

def attaque_force_brute(texte_chiffre: str) -> list[tuple[int, str]]:
    """
    Retourne tous les dechiffrements possibles sous forme de tuples (cle, texte),
    tries par cle croissante.
    """
    pass

Messages a casser :

FrancaisAnglais

Kl tltvpyl, Qbslz Jlzhy mba hzzhzzpul sl 15 thyz why Iybabz hb zluha kl Yvtl

Vkrimhzktiar bl max lvbxgvx hy dxxibgz lxvkxml ltyx ykhf ikrbgz xrxl

Note

Les deux messages sont dans des langues differentes. La force brute fonctionne dans les deux cas — mais pouvez-vous identifier la bonne cle sans comprendre la langue ?

README : noter la cle trouvee et le message clair pour chaque message.

---

Partie 3 — Analyse frequentielle

Fichier : freq.py

3a. Calculer les frequences

# Frequences de reference (top 10)
FREQ_FR = {'e': 0.1471, 'a': 0.0762, 'i': 0.0744, 's': 0.0733, 't': 0.0721,
           'n': 0.0711, 'r': 0.0655, 'u': 0.0631, 'l': 0.0546, 'o': 0.0514}

FREQ_EN = {'e': 0.1270, 't': 0.0906, 'a': 0.0817, 'o': 0.0751, 'i': 0.0697,
           'n': 0.0675, 's': 0.0633, 'h': 0.0609, 'r': 0.0599, 'd': 0.0425}

# Frequences completes (26 lettres) pour les graphiques
FREQ_FR_FULL = {
    'a': 0.0762, 'b': 0.0090, 'c': 0.0326, 'd': 0.0367, 'e': 0.1471,
    'f': 0.0107, 'g': 0.0087, 'h': 0.0074, 'i': 0.0744, 'j': 0.0061,
    'k': 0.0005, 'l': 0.0546, 'm': 0.0297, 'n': 0.0711, 'o': 0.0514,
    'p': 0.0286, 'q': 0.0136, 'r': 0.0655, 's': 0.0733, 't': 0.0721,
    'u': 0.0631, 'v': 0.0164, 'w': 0.0003, 'x': 0.0042, 'y': 0.0019,
    'z': 0.0021
}

def calculer_frequences(texte: str) -> dict[str, float]:
    """
    Calcule la frequence de chaque lettre dans le texte (float entre 0 et 1).
    Insensible a la casse. Ignore les non-lettres.
    Retourne un dictionnaire avec les 26 lettres (meme celles absentes, a 0.0).
    """
    pass

def deviner_cle(texte_chiffre: str, langue: str = "fr") -> int:
    """
    Estime la cle par analyse frequentielle.
    Strategie : lettre la plus frequente dans le texte chiffre ≈ 'e' dans la langue.
    langue : "fr" ou "en"
    Retourne la cle estimee (int 0-25).
    """
    pass

A faire : charger les messages depuis messages/message_fr.txt et messages/message_en.txt, deviner la cle, dechiffrer.

3b. Visualiser avec matplotlib

import matplotlib.pyplot as plt

def afficher_frequences(texte_chiffre: str, langue: str = "fr") -> None:
    """
    Affiche un graphique comparant :
    - les frequences des lettres dans le texte chiffre (barres bleues)
    - les frequences theoriques de la langue (barres rouges, transparentes)

    Etapes :
    1. Calculer les frequences du texte chiffre avec calculer_frequences()
    2. Recuperer les frequences theoriques (FREQ_FR_FULL ou FREQ_EN_FULL)
    3. Tracer deux series de barres cote a cote pour les 26 lettres (a-z)
    4. Ajouter titre, legende et labels des axes
    5. Appeler plt.show()
    """
    pass

Indices pour le graphique

import matplotlib.pyplot as plt
import numpy as np

    lettres = list("abcdefghijklmnopqrstuvwxyz")
    x = np.arange(26)
    largeur = 0.35

    # Barres cote a cote
    plt.bar(x - largeur/2, freq_texte, largeur, label="Texte chiffre", color="steelblue")
    plt.bar(x + largeur/2, freq_langue, largeur, label="Francais theorique", color="indianred", alpha=0.7)

    plt.xticks(x, lettres)
    plt.ylabel("Frequence")
    plt.title("Analyse frequentielle — texte chiffre vs langue")
    plt.legend()
    plt.tight_layout()
    plt.show()
    ```

### 3c. Verifier visuellement la cle

```python
def afficher_comparaison_decalage(texte_chiffre: str, cle: int, langue: str = "fr") -> None:
    """
    Affiche un graphique comparant les frequences du texte DECHIFFRE
    (avec la cle donnee) aux frequences theoriques de la langue.

    Si la cle est correcte, les barres bleues et rouges doivent se superposer.
    """
    pass

!!! example "Resultat attendu" - Avant dechiffrement : les barres bleues sont decalees par rapport aux rouges. Le decalage correspond a la cle. - Apres dechiffrement (bonne cle) : les barres bleues et rouges se superposent → la cle est correcte. - Apres dechiffrement (mauvaise cle) : les barres ne correspondent toujours pas.

README : noter la cle devinee, le message dechiffre, et si l'analyse a fonctionne du premier coup. Inclure une capture d'ecran du graphique avant/apres dechiffrement.

---

Partie 4 — Vigenere

Fichier : vigenere.py

def chiffrer_vigenere(texte: str, cle: str) -> str:
    """
    Chiffre avec Vigenere. La cle est une chaine de lettres (ex: "CRYPTO").
    Seules les lettres sont chiffrees, le reste est conserve.
    """
    pass

def casser_vigenere(texte_chiffre: str, langue: str = "fr") -> tuple[str, str]:
    """
    Casse le chiffre de Vigenere par analyse frequentielle.
    Etapes suggerees :
    1. Trouver la longueur de cle (indice de coincidence ou test de Kasiski)
    2. Traiter chaque position comme un Cesar independant
    3. Appliquer l'analyse frequentielle sur chaque groupe
    Retourne (cle_trouvee, texte_dechiffre).
    """
    pass

---

README a rendre

# TD1 — Cryptographie classique

## Exercices sur papier

### Exercice 1 — Cesar

- 1. Message chiffre (K=5) : \_\_\_
- 2. Message dechiffre (RGNEIDVGPEWXTRAPHHXFJT) : **_, cle = _**
- 3. Cle trouvee : **_, debut du message clair : _**

### Exercice 2 — Substitution

- 1. Message chiffre : \_\_\_
- 2. YHVMQUVMH dechiffre : **_. Peut-on le casser sans la cle ? _**

### Exercice 3 — Vigenere (papier)

- 1. Message chiffre (cle POULE) : \_\_\_
- 2. BAUNBEKLZLQSKQKEBGCJYHVSKR dechiffre (cle TNCY) : \_\_\_

### Exercice 4 — Chiffrement affine

- 1. Verification S → J : \_\_\_
- 2. SECRET code : \_\_\_
- 3. Demonstration : \_\_\_
- 4. KGHSX dechiffre : \_\_\_

### Exercice 5 — Chiffrement affine (generalisation)

- 1. Demonstration (a premier avec 26) : \_\_\_
- 2a. Existence de u : \_\_\_
- 2b. Fonction de decodage : \_\_\_
- 2c. ZSPS decode (cle 15;2) : \_\_\_

### Exercice 6 — Hill

- Partie A : INDICE chiffre = **_, DVUBYO dechiffre = _**, YOWPEE dechiffre = \_\_\_
- Partie B : INDICE chiffre = **_, produit MA = _**, explication cle B = **_, verification C = 23M : _**

### Exercice 7 — ADFGVX

- 1. ATTAQUE chiffre : \_\_\_
- 2. DFAADDGAFXDDADFA dechiffre : \_\_\_
- 3. Pourquoi A, D, F, G, V, X ? \_\_\_
- 4. Interet de la double etape : \_\_\_

## Exercices Python

### Force brute

- Message francais : cle = **_, message clair = _**
- Message anglais : cle = **_, message clair = _**

### Analyse frequentielle

- Message francais : cle devinee = **_, correcte ? _**
- Message anglais : cle devinee = **_, correcte ? _**
- Observations : (l'analyse a-t-elle fonctionne du premier coup ? Pourquoi ?)

### Vigenere

- Cle trouvee : \_\_\_
- Methode utilisee : \_\_\_

## Difficultes rencontrees

(libre)