Réseau de Feistel

Un cas particulier d'algorithmes de chiffrement par blocs avec itération est la famille des réseaux de Feistel. Horst Feistel, né le 30 janvier 1915 à Berlin, mort le 14 novembre 1990, est un cryptographe américain d'origine allemande (voir photo ci-contre vers 1944). Il fut l'un des premiers cryptographes universitaires.
Dans ce système de chiffrement, un bloc de texte en clair est découpé en deux ; la transformation de ronde est appliquée à une des deux moitiés, et le résultat est combiné avec l'autre moitié par ou exclusif. Les deux moitiés sont alors inversées pour l'application de la ronde suivante. Un avantage de ce type d'algorithmes est que chiffrement et déchiffrement sont structurellement identiques.

À titre d'exemple, nous allons chiffrer par un réseau de Feistel à deux rondes un message constitué de quatre bits (24 = 16 possibilités de messages), ce qui revient à construire une bijection de quatre bits vers quatre bits à partir de deux fonctions f1 et f2 de deux bits vers deux bits.

Nous considérerons que pour une certaine clef entrée, ces fonctions sont les suivantes:

entrée f1 sortie entrée f2 sortie
00 01 00 11
01 11 01 00
10 10 10 00
11 01 11 01

On peut "additionner" deux bits à l'aide de la fonction XOR (symbolisée par un + entouré d'un cercle) donnée par le tableau ci-dessous. Il est à noter que l'opérateur XOR est son propre inverse.

XOR 0 1
0 0 1
1 1 0

Notons que ni f1 ni f2 ne sont des bijections. À titre d'exemple, chiffrons le message 1101. G désigne la moitié gauche du message à chiffrer, D la moitié droite. Vous trouverez ci-dessous le réseau de Feistel que l'on utilisera et (à droite) les chiffrements obtenus des 16 messages possibles.

message résultat
0000 0100
0001 1100
0010 1010
0011 0111
0100 0011
0101 1001
0110 1111
0111 0000
1000 1101
1001 0101
1010 0001
1011 1110
1100 1000
1101 0010
1110 0110
1111 1011

Vous constatez qu'il y a une correspondance univoque entre chaque message et son image par le réseau de Feistel: on a construit une bijection à partir de deux fonctions qui n'en sont pas.

Travail

Vérifiez les images des 16 messages possibles.

Trouvez comment déchiffrer les messages (cela revient à utiliser le schéma de Feistel "à l'envers").

Références

  Didier Müller, 24.1.21