🎬 Introduction rapide
Le schéma de Feistel est la colonne vertébrale de nombreux chiffrements historiques (DES, variantes, etc.).
Son intérêt : il permet de construire un chiffrement réversible même si la fonction de ronde f n’est pas inversible.
Dit autrement : on n’a pas besoin de résoudre l’équation f^{-1} pour déchiffrer.
Pratique quand f est un bazar non linéaire (S-boxes, additions modulo, rotations…).
Spoiler : tu peux chiffrer avec une fonction complètement illisible à l’intérieur, et quand même déchiffrer parfaitement. Magique ? Non : ingénieux.
🔧 Règles du jeu (version jouet)
On travaille sur des blocs de 8 bits, divisés en 2 moitiés de 4 bits :
M = L_0 | R_0.
Une ronde Feistel transforme (L_i , R_i) en (L_{i+1} , R_{i+1}) par :
L_{i+1} = R_i,
R_{i+1} = L_i \oplus f(R_i , K_i)
où K_i est la sous-clé ronde et f une fonction (ici simple pour la démo).
Après n rondes, on obtient le bloc chiffré (L_n , R_n).
🧾 Preuve courte : pourquoi c’est inversible (intuitif & formel)
Imaginons qu’on connaisse (L_{i+1} , R_{i+1}).
On veut retrouver (L_i , R_i).
On a par définition :
L_{i+1} = R_i ;;\Rightarrow;; R_i = L_{i+1}.
Et :
R_{i+1} = L_i \oplus f(R_i , K_i).
Donc :
L_i = R_{i+1} \oplus f(R_i , K_i).
Mais R_i on l’a trouvé juste au-dessus (c’est L_{i+1}).
Donc :
L_i = R_{i+1} \oplus f(L_{i+1} , K_i).
Autrement dit, connaissant (L_{i+1} , R_{i+1}), on récupère (L_i , R_i) sans inverser f.
Résultat : à chaque ronde on recule d’un pas en appliquant la même fonction f (avec la même clé) — c’est cette symétrie qui rend la construction automatiquement réversible.
Pratique de lecture : pour déchiffrer un bloc chiffré après n rondes, il suffit d’appliquer les mêmes opérations mais en utilisant les sous-clés dans l’ordre inverse.
🔢 Exemple chiffré (à refaire sur papier) — 2 rondes, blocs 8 bits
Choix pour l’exemple (tout simple) :
- L_0 = 1011_2 (11 décimal),
- R_0 = 0101_2 (5 décimal) → message M = 1011\ 0101.
Définissons f(x , K) = (x + K) \bmod 16 (addition modulo 16 sur 4 bits) puis converti en 4 bits.
Clés : K_0 = 3 (0011), K_1 = 7 (0111).
🔹 Ronde 0 → 1
L_1 = R_0 = 0101.
f(R_0 , K_0) = (5 + 3) \bmod 16 = 8 = 1000.
R_1 = L_0 \oplus f(R_0 , K_0) = 1011 \oplus 1000 = 0011.
Donc (L_1 , R_1) = (0101 , 0011).
🔹 Ronde 1 → 2
L_2 = R_1 = 0011.
f(R_1 , K_1) = (3 + 7) \bmod 16 = 10 = 1010.
R_2 = L_1 \oplus f(R_1 , K_1) = 0101 \oplus 1010 = 1111.
Chiffré final : (L_2 , R_2) = (0011 , 1111) → C = 0011\ 1111.
🔄 Déchiffrement (clés inversées)
On commence de (L_2 , R_2) = (0011 , 1111), on connaît K_1 , K_0.
Reculer ronde 1 → 0 :
R_1 = L_2 = 0011.
L_1 = R_2 \oplus f(L_2 , K_1) = 1111 \oplus f(0011 , 0111).
f(3 , 7) = 10 = 1010 → L_1 = 1111 \oplus 1010 = 0101.
Reculer ronde 0 → -1 (retour à l’original) :
R_0 = L_1 = 0101.
L_0 = R_1 \oplus f(L_1 , K_0) = 0011 \oplus f(0101 , 0011).
f(5 , 3) = 8 = 1000 → L_0 = 0011 \oplus 1000 = 1011.
On retrouve bien (L_0 , R_0) = (1011 , 0101) → message initial ✔️
🧪 Exercices / À refaire chez toi (10 min)
- Reprends l’exemple ci-dessus et change K_1 = 12 ; recommence chiffrement + déchiffrement.
- Remplace f par : f(x , K) = \text{rotl}(x , 1) \oplus K (rotation gauche sur 4 bits puis XOR avec la clé).
- Implémente le schéma 4 rondes en 16 bits (8+8) en Python — publie ton résultat sur SecuSlice si tu fais un joli GIF.
Petit squelette Python (pseudo) :
def f(x, k): return (x + k) & 0xF # 4-bit
def feistel_round(L, R, k):
return R, L ^ f(R, k)
# applique n fois...
🏁 Conclusion
Le génie du Feistel, c’est d’avoir séparé réversibilité et complexité locale.
On peut construire f hyper-compliquée (S-boxes tordues, rotations, additions modulo…), tout en gardant la garantie :
- chiffrer = appliquer les rondes,
- déchiffrer = appliquer les mêmes rondes dans l’ordre inverse.
Résultat pratique : un design modulaire, robuste et super pratique à implémenter.
