1. Introduction à la Cryptographie
ALICE (émetteur) BOB (destinataire)
│ │
M (texte clair) ──► E(M, K) = C ──► D(C, K) = M
│ (Chiffrement) (Transmission) (Déchiffrement)
│ │ │ │
Clé K ───────────► Canal ◄──── Eve (intrus) ──► Clé K
réseau [écoute/attaque]
L'algorithme de chiffrement peut être public (pas besoin de le garder secret), mais la clé doit rester secrète. C'est le principe de Kerckhoffs.
Chaque lettre (ou groupe) est remplacée par une autre lettre selon une règle.
Sous-types : Mono-alphabétique (une lettre → une lettre fixe) et Poly-alphabétique (une lettre → plusieurs lettres possibles selon la position).
Les lettres du message sont réarrangées (permutées) selon un schéma défini, sans en changer la valeur.
Exemple : BONJOUR → OJRUBNO (selon une permutation).
2. Le Chiffrement de César
Le chiffre de César est le plus ancien chiffrement par substitution connu. Il a été utilisé par Jules César dans l'armée romaine durant la guerre des Gaules avec un décalage de k = 3. C'est un chiffrement par décalage alphabétique.
où x est le rang de la lettre claire (A=0, B=1, …, Z=25), K est la clé de décalage (0 ≤ K ≤ 25), et y est le rang de la lettre chiffrée.
Il n'existe que 25 clés possibles (de 1 à 25). Une attaque par force brute (tester toutes les clés) casse le code en quelques secondes. De plus, l'analyse de fréquence le brise facilement.
Clair : 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 Chiffré: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Exemple : BONJOUR (k=3) B → rang 1 → (1+3) mod 26 = 4 → E O → rang 14 → (14+3) mod 26 = 17 → R N → rang 13 → (13+3) mod 26 = 16 → Q J → rang 9 → (9+3) mod 26 = 12 → M O → rang 14 → (14+3) mod 26 = 17 → R U → rang 20 → (20+3) mod 26 = 23 → X R → rang 17 → (17+3) mod 26 = 20 → U Résultat : BONJOUR → ERQMRXU
4. Le Chiffrement de Vigenère
Vigenère améliore César en utilisant une clé de longueur m (un mot-clé). Chaque lettre du message est chiffrée avec un décalage différent selon la lettre correspondante de la clé (répétée cycliquement).
Où K = (k₁, k₂, ..., kₘ) est la clé (chaque kᵢ est le rang de la lettre du mot-clé, avec A=0, B=1, etc.)
C=2, I=8, P=15, H=7, E=4, R=17
Message : T H I S C R Y P T O S Y S T E M I S N O T S E C U R E Rangs M : 19 7 8 18 2 17 24 15 19 14 18 24 18 19 4 12 8 18 13 14 19 18 4 2 20 17 4 Clé(rep): C I P H E R C I P H E R C I P H E R C I P H E R C I P Rangs K : 2 8 15 7 4 17 2 8 15 7 4 17 2 8 15 7 4 17 2 8 15 7 4 17 2 8 15 Somme%26: 21 15 23 25 6 8 0 23 8 21 22 15 20 1 19 19 12 9 15 22 8 25 8 19 22 25 19 Chiffré : V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T Résultat : VPXZGIAXIVWPUBTTMJPWIZITW ZT ✓
Si le même segment du texte clair se retrouve aligné avec le même segment de la clé, le même texte chiffré apparaît. En cherchant les répétitions dans le texte chiffré et en calculant le PGCD des distances entre elles, on peut déduire la longueur de la clé, puis casser chaque sous-chiffrement César séparément.
5. Chiffrement Affine
Le chiffrement affine généralise César : au lieu d'un simple décalage, on applique une fonction affine y = ax + b. La clé est un couple K = (a, b).
Pour que le chiffrement affine soit inversible (= déchiffrable), il faut absolument que :
pgcd(a, 26) = 1 → a doit être premier avec 26.
Les valeurs valides pour a sont : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (12 valeurs).
Si a=2 par exemple, pgcd(2,26)=2≠1 → pas d'inverse → pas de déchiffrement possible.
Remarque : Si a=1 → on retrouve le chiffre de César (b = décalage). Si b=0 → le A est toujours chiffré A.
| a | a⁻¹ mod 26 | a | a⁻¹ mod 26 |
|---|---|---|---|
| 1 | 1 | 15 | 7 |
| 3 | 9 | 17 | 23 |
| 5 | 21 | 19 | 11 |
| 7 | 15 | 21 | 5 |
| 9 | 3 | 23 | 17 |
| 11 | 19 | 25 | 25 |
Lettre : S E C R E T Rang x : 18 4 2 17 4 19 Calcul : (3×18+7)%26 (3×4+7)%26 (3×2+7)%26 (3×17+7)%26 (3×4+7)%26 (3×19+7)%26 = 61%26 = 19%26 = 13%26 = 58%26 = 19%26 = 64%26 = 9 = 19 = 13 = 6 = 19 = 12 Chiffré: J T N G T M Résultat : SECRET → JTNGTM ── Déchiffrement ── (a⁻¹=9 car 3×9=27≡1 mod26) Lettre : J T N G T M Rang y : 9 19 13 6 19 12 Calcul : 9×(9−7)%26 9×(19−7)%26 9×(13−7)%26 9×(6−7)%26 9×(19−7)%26 9×(12−7)%26 = 9×2%26 = 9×12%26 = 9×6%26 = 9×(-1)%26 = 9×12%26 = 9×5%26 = 18 = 4 = 2 = 17 = 4 = 19 Clair : S E C R E T ✓
6. Chiffrement de Hill
Hill utilise l'algèbre matricielle sur Z/26Z. On traite les lettres par blocs de taille m (souvent m=2), et la clé est une matrice carrée K ∈ GL_m(Z/26Z).
La matrice K est inversible si et seulement si :
pgcd(det(K), 26) = 1
(le déterminant doit être inversible mod 26)
Pour m=2, clé K = [[a,b],[c,d]] :
Pour K = [[a,b],[c,d]] :
det(K) = (a·d − b·c) mod 26
K⁻¹ = (det K)⁻¹ · [[d, −b], [−c, a]] mod 26
Lettres : U S T O → rangs (a=1) : 20 18 19 14 Blocs : [U,S] = [20,18] | [T,O] = [19,14] ── Bloc 1 [U,S] ── C₁ = (9×20 + 4×18) mod 26 = (180+72) mod 26 = 252 mod 26 = 18 → S C₂ = (5×20 + 7×18) mod 26 = (100+126) mod 26 = 226 mod 26 = 18 → S ── Bloc 2 [T,O] ── C₃ = (9×19 + 4×14) mod 26 = (171+56) mod 26 = 227 mod 26 = 19 → T C₄ = (5×19 + 7×14) mod 26 = (95+98) mod 26 = 193 mod 26 = 11 → L Résultat : USTO → SSTL
det(K) = 9×7 − 4×5 = 63−20 = 43 mod 26 = 17
17⁻¹ mod 26 = 23 (car 17×23 = 391 = 15×26 + 1 ✓)
K⁻¹ = 23 × [[7,−4],[−5,9]] mod 26
= 23 × [[7,22],[21,9]] mod 26
= [[5,12],[15,25]] mod 26
Message UWGMWZRREIUB → Blocs : UW|GM|WZ|RR|EI|UB
Rangs : (20,22)|(6,12)|(22,25)|(17,17)|(4,8)|(20,1)
── Bloc 1 : (20,22) ──
5×20+12×22 mod 26 = 100+264=364 mod 26 = 0 → A
15×20+25×22 mod 26 = 300+550=850 mod 26 = 6 → G
→ AG
── Bloc 2 : (6,12) ──
5×6+12×12 mod 26 = 30+144=174 mod 26 = 18 → S
15×6+25×12 mod 26 = 90+300=390 mod 26 = 0 → O (... etc.)
→ SO …
7. Cryptanalyse des Chiffrements Classiques
Dans toute langue naturelle, les lettres n'apparaissent pas avec la même fréquence. En français, le E représente ~17.26% des lettres et le A ~8.4%. Un chiffre de substitution mono-alphabétique conserve ces fréquences.
| Méthode | Principe | Contre quel chiffre ? |
|---|---|---|
| Analyse de fréquence | Compter les lettres dans le texte chiffré. La plus fréquente correspond à E (en français). Déduire k = rang(lettre_freq) − 4. | César, substitution mono-alpha |
| Test de Kasiski | Chercher les séquences répétées dans le chiffré, calculer les distances, prendre le PGCD → longueur probable de la clé. | Vigenère |
| Indice de coïncidence | Mesurer la "régularité" du texte pour estimer la longueur de clé. IC ≈ 0.065 pour le français (mono), ≈ 0.038 pour aléatoire. | Vigenère |
| Force brute | Essayer toutes les clés possibles. Efficace si l'espace des clés est petit (25 clés pour César). | César (25 essais) |
Le One-Time Pad utilise une clé aléatoire de même longueur que le message, utilisée une seule fois. XOR bit par bit avec le message.
Conditions de sécurité inconditionnelle :
① La clé doit être parfaitement aléatoire
② La clé doit être au moins aussi longue que le message
③ La clé ne doit être utilisée qu'une seule fois (jamais réutilisée)
④ La clé doit être tenue secrète
Si une de ces conditions n'est pas respectée, la sécurité s'effondre. C'est pour ça que le OTP est difficile à utiliser en pratique (distribution sécurisée de la clé).
Message normalisé : LARENCONTREESTPREVUEALACAFETERIA
Formule : E(x, 5) = (x + 5) mod 26
Résultat : LARENCONTREESTPREVUEALACAFETERIA → QFWJSXHTSYWJJXYWJAZJFQFHFKJYJWNF
On essaie différentes valeurs de k jusqu'à obtenir un texte lisible :
Méthode : On essaie k de 1 à 25 et on cherche un texte en français/anglais. En pratique sur l'examen, la clé sera trouvée dès qu'un texte cohérent apparaît.
Clé k = 10. Le message commence par "ILENVOYE" = "IL ENVOYE..." — Cohérent en français !
- Chiffrer "la rencontre est prévue à la cafeteria" avec Vigenère et le mot-clé POULE
- Déchiffrer "DSJWPHYRSSUHPAJXVQV" sachant que la clé est BORDEAUX
POULE = P(15), O(14), U(20), L(11), E(4) — longueur 5, répété cycliquement
Message normalisé : LARENCONTREESTPREVUEALACAFETERIA
Résultat : LARENCONTREESTPREVUEALACAFETERIA → AOLPRRCHEVTSMETSPIZETUNEUSNPVXO
BORDEAUX = B(1),O(14),R(17),D(3),E(4),A(0),U(20),X(23) — longueur 8
Message : DSJWPHYRSSUHPAJXVQV
Message déchiffré : "CESTLHEUREDELAPAUCE" → "C'est l'heure de la pause !"
- Chiffrer CODE avec la clé (F, T) → F=5, T=19 → K=(a=5, b=19)
- Déchiffrer KZXI avec la clé (H, V) → H=7, V=21 → K=(a=7, b=21)
Vérification : pgcd(5, 26) = 1 ✓ → clé valide
E(x) = (5x + 19) mod 26
Vérification : pgcd(7, 26) = 1 ✓ → 7⁻¹ mod 26 = 15 (car 7×15=105=4×26+1)
D(y) = 15·(y − 21) mod 26
SUPINFO normalisé (a=1,b=2,...) : S=18, U=20, P=15, I=8, N=13, F=5, O=14 ... mais SUPINFO = 6 lettres → 3 blocs de 2
Blocs : [S,U]=[18,20] | [P,I]=[15,8] | [N,F]=[13,5] ... (O reste seul → on ajoute un padding X=23 si nécessaire)
En utilisant les rangs A=0 : S=18, U=20, P=15, I=8, N=13, F=5
Résultat : SUPINFO → IKLBHW
QCM — Chapitre 2 : Cryptographie Classique
15 questions techniques avec correction immédiate.