Horst Feistel

En 1971, chez IBM, Horst Feistel développe Lucifer. Pour imaginer un tour du réseau sur lequel repose cet algorithme, donnons un nom aux deux moitiés du bloc. Une règle de calcul, appelée fonction, transforme celle de droite ; son résultat est combiné à celle de gauche. La convention fixe alors leur place au tour suivant : la moitié droite passe à gauche et le résultat combiné passe à droite.

L’intérêt décisif de cette organisation est le retour en arrière. Le déchiffrement peut inverser l’ensemble sans imposer que chaque transformation intermédiaire soit elle-même inversible. Cette architecture, appelée réseau de Feistel, a ensuite directement inspiré DES.

Horst Feistel (1915–1990) est un cryptographe américain d’origine allemande. Né en Allemagne, il émigre aux États-Unis en 1934 et devient citoyen américain en 1944. Son parcours professionnel le conduit successivement au US Air Force Cambridge Research Center, au Massachusetts Institute of Technology, puis chez IBM.

Ses recherches concernent le chiffrement symétrique. Elles conduisent au réseau de Feistel, une architecture algorithmique itérative appliquée à un bloc séparé en deux moitiés. À chaque tour de chiffrement, une fonction agit sur une moitié ; son résultat est combiné à l’autre moitié, tandis que la première est conservée puis que les rôles sont échangés selon la convention. L’architecture complète reste facilement inversible pour le déchiffrement, même si les fonctions employées à chaque tour ne sont pas elles-mêmes inversibles.

Feistel développe pour IBM l’algorithme Lucifer en 1971. Le réseau de Feistel en constitue la structure fondamentale. Lucifer inspire directement le Data Encryption Standard, ou DES, adopté en 1977 comme norme fédérale américaine. L’héritage de Feistel relie ainsi une structure générale de chiffrement, un algorithme conçu chez IBM et un standard ultérieur.

Calculons un tour jouet sur deux moitiés binaires : à gauche L0 = 01 et à droite R0 = 11. La convention choisie pose L1 = R0 et combine L0 avec la sortie de fonction pour former R1. Supposons que la fonction donne F(R0) = F(11) = 10.

1. Appliquons la fonction à la moitié droite : la sortie à utiliser est F(11) = 10.

2. Combinons cette sortie avec la moitié gauche par un OU exclusif, bit par bit : 01 XOR 10 = 11. Nous obtenons donc R1 = 11.

3. Transmettons l’ancienne moitié droite à gauche : L1 = R0 = 11. Après ce tour, la paire (L1, R1) vaut donc (11, 11).

Le contrôle se fait en sens inverse avec la même sortie de fonction : R0 = L1 = 11, puis L0 = R1 XOR F(L1) = 11 XOR 10 = 01. On retrouve bien la paire initiale (01, 11), sans avoir eu à inverser la fonction F.

Dans une histoire de la cryptographie moderne, Horst Feistel sert de point de passage entre une recherche sur le chiffrement symétrique et le standard DES. Le bon geste est de suivre la chronologie : Lucifer est développé en 1971, DES est adopté en 1977.

Devant une construction de chiffrement, trois indices permettent de reconnaître un réseau de Feistel : deux moitiés, des tours répétés et, d’un tour au suivant, une moitié transmise tandis que l’autre est recomposée. Si une description donne seulement le nom d’un produit, par exemple Lucifer, elle désigne un algorithme particulier et non l’architecture générale.

Pour expliquer le déchiffrement, le point à examiner est l’architecture d’ensemble. Elle est facilement inversible sans exiger l’inversibilité de chaque fonction de tour : c’est cette propriété, et non la seule séparation en deux moitiés, qui donne au réseau son intérêt.

Horst Feistel et le réseau de Feistel. Horst Feistel est le cryptographe né en 1915 et mort en 1990. Le réseau de Feistel est la structure algorithmique issue de ses recherches. Une date de vie désigne la personne ; la séparation d’un bloc en deux moitiés, avec une fonction appliquée à l’une puis combinaison et échange des rôles à chaque tour, désigne la structure.

Lucifer et DES. Lucifer est l’algorithme développé par Feistel pour IBM en 1971. DES est le standard qu’il a directement inspiré et qui a été adopté comme norme fédérale américaine en 1977. Le nom et l’année permettent donc de trancher.

Réseau et algorithme. Le réseau de Feistel est une architecture itérative générale ; Lucifer est un algorithme construit sur cette architecture. Pour qualifier un objet précis, il faut vérifier si le texte décrit une organisation en tours ou nomme l’algorithme de 1971.

Une chronologie n’est pas une identité. Le fait que Lucifer ait directement inspiré DES ne rend pas les deux noms interchangeables. Le symptôme du piège est l’emploi de « Lucifer » pour désigner la norme de 1977 ; il faut rétablir la chaîne d’influence.

L’inversibilité porte sur l’architecture complète. Exiger que chaque fonction de tour soit inversible contredit précisément la propriété mise en avant par la source. Il faut distinguer la fonction locale de l’organisation globale qui rend le déchiffrement possible.

Deux moitiés ne suffisent pas à résumer le réseau. Si une description omet qu’à chaque tour une fonction agit sur une moitié, que son résultat est combiné à l’autre et que leurs rôles sont échangés selon la convention, elle perd un élément constitutif. Il faut conserver ensemble la séparation du bloc, l’itération et cette alternance des opérations.

Ne pas dater ce que la source ne date pas. Les passages de Feistel au US Air Force Cambridge Research Center, au MIT puis chez IBM sont ordonnés, mais aucune année n’est fournie pour chacun. Il faut donc préserver cet ordre sans lui attribuer de dates précises.

La cryptographie replace les travaux de Feistel dans le domaine qui étudie la protection des informations.

La fiche sur le chiffrement approfondit l’opération à laquelle le réseau de Feistel apporte une architecture.

La cryptologie offre un cadre plus large pour situer le chiffrement symétrique et son histoire.

La notion d’algorithme aide à distinguer une suite d’opérations, comme Lucifer, de l’architecture générale qui la structure.