Chiffre Feistel - Feistel cipher

En cryptographie , un chiffre Feistel (également connu sous le nom de chiffrement par bloc Luby-Rackoff ) est une structure symétrique utilisée dans la construction de chiffrements par bloc , du nom du allemand -Born physicien et cryptographe Horst Feistel qui a fait des recherches avant - garde tout en travaillant pour IBM (USA) ; il est également connu sous le nom de réseau Feistel . Une grande proportion de chiffrements par blocs utilisent le schéma, y ​​compris la norme américaine de chiffrement de données , le GOST soviétique / russe et les plus récents chiffrements Blowfish et Twofish . Dans un chiffrement Feistel, le chiffrement et le déchiffrement sont des opérations très similaires, et tous deux consistent à exécuter de manière itérative une fonction appelée «fonction ronde» un nombre fixe de fois.

L'histoire

De nombreux chiffrements par blocs symétriques modernes sont basés sur les réseaux Feistel. Les réseaux Feistel ont d'abord été vus commercialement dans le chiffrement Lucifer d'IBM , conçu par Horst Feistel et Don Coppersmith en 1973. Les réseaux Feistel ont gagné en respectabilité lorsque le gouvernement fédéral américain a adopté le DES (un chiffrement basé sur Lucifer, avec des modifications apportées par la NSA ) en 1976. Comme d'autres composants du DES, la nature itérative de la construction Feistel facilite la mise en œuvre du cryptosystème dans le matériel (en particulier sur le matériel disponible au moment de la conception du DES).

Conception

Un réseau Feistel utilise une fonction ronde , une fonction qui prend deux entrées, un bloc de données et une sous-clé, et renvoie une sortie de la même taille que le bloc de données. A chaque tour, la fonction round est exécutée sur la moitié des données à chiffrer et sa sortie est XORed avec l'autre moitié des données. Ceci est répété un nombre fixe de fois, et la sortie finale est les données cryptées. Un avantage important des réseaux Feistel par rapport aux autres conceptions de chiffrement telles que les réseaux de substitution-permutation est que toute l'opération est garantie d'être inversible (c'est-à-dire que les données chiffrées peuvent être déchiffrées), même si la fonction ronde n'est pas elle-même inversible. La fonction ronde peut être rendue arbitrairement compliquée, car elle n'a pas besoin d'être conçue pour être inversible. De plus, les opérations de chiffrement et de déchiffrement sont très similaires, voire identiques dans certains cas, ne nécessitant qu'une inversion de la planification des clés . Par conséquent, la taille du code ou des circuits requis pour mettre en œuvre un tel chiffrement est presque divisée par deux.

Travail théorique

La structure et les propriétés des chiffrements Feistel ont été largement analysées par les cryptographes .

Michael Luby et Charles Rackoff ont analysé la construction du chiffrement de Feistel et ont prouvé que si la fonction ronde est une fonction pseudo-aléatoire cryptographiquement sécurisée , avec K _i utilisé comme germe, alors 3 tours suffisent pour faire du chiffrement par bloc une permutation pseudo - aléatoire , tandis que 4 tours sont suffisantes pour en faire une permutation pseudo-aléatoire «forte» (ce qui signifie qu'elle reste pseudo-aléatoire même pour un adversaire qui obtient l' accès oracle à sa permutation inverse). En raison de ce résultat très important de Luby et Rackoff, les chiffrements Feistel sont parfois appelés chiffrements par blocs Luby – Rackoff.

D'autres travaux théoriques ont quelque peu généralisé la construction et donné des limites plus précises pour la sécurité.

Détails de construction

Soit la fonction ronde et soit les sous-clés pour les tours respectivement. ${\ displaystyle {\ rm {F}}}$${\ displaystyle K_ {0}, K_ {1}, \ ldots, K_ {n}}$${\ displaystyle 0,1, \ ldots, n}$

Ensuite, l'opération de base est la suivante:

Divisez le bloc de texte brut en deux parties égales, ( , ) ${\ displaystyle L_ {0}}$${\ displaystyle R_ {0}}$

Pour chaque tour , calculez ${\ displaystyle i = 0,1, \ points, n}$

${\ displaystyle L_ {i + 1} = R_ {i} \,}$

${\ displaystyle R_ {i + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}$

Où signifie XOR . Alors le texte chiffré est . ${\ displaystyle \ oplus}$${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$

Le décryptage d'un texte chiffré est effectué en calculant pour ${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$${\ displaystyle i = n, n-1, \ ldots, 0}$

${\ displaystyle R_ {i} = L_ {i + 1} \,}$

${\ displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ {i + 1}, K_ {i}).}$

Puis est à nouveau le texte en clair. ${\ displaystyle (L_ {0}, R_ {0})}$

Le diagramme illustre à la fois le cryptage et le décryptage. Notez l'inversion de l'ordre des sous-clés pour le déchiffrement; c'est la seule différence entre le cryptage et le décryptage.

Chiffrement Feistel déséquilibré

Les chiffrements Feistel non équilibrés utilisent une structure modifiée où et ne sont pas de longueurs égales. Le chiffrement Skipjack est un exemple d'un tel chiffrement. Le transpondeur de signature numérique de Texas Instruments utilise un chiffrement Feistel non équilibré exclusif pour effectuer une authentification défi-réponse . ${\ displaystyle L_ {0}}$${\ displaystyle R_ {0}}$

Le shuffle Thorp est un cas extrême de chiffrement Feistel déséquilibré dans lequel un côté est un seul bit. Cela a une meilleure sécurité prouvable qu'un chiffrement Feistel équilibré mais nécessite plus de tours.

Autres utilisations

La construction Feistel est également utilisée dans des algorithmes cryptographiques autres que les chiffrements par blocs. Par exemple, le schéma de remplissage de cryptage asymétrique optimal (OAEP) utilise un simple réseau Feistel pour randomiser les textes chiffrés dans certains schémas de cryptage à clé asymétrique .

Un algorithme de Feistel généralisé peut être utilisé pour créer de fortes permutations sur de petits domaines de taille pas une puissance de deux (voir chiffrement préservant le format ).

Réseaux Feistel en tant que composant de conception

Que le chiffrement entier soit un chiffrement Feistel ou non, les réseaux de type Feistel peuvent être utilisés en tant que composant de la conception d'un chiffrement. Par exemple, MISTY1 est un chiffrement Feistel utilisant un réseau Feistel à trois tours dans sa fonction ronde, Skipjack est un chiffrement Feistel modifié utilisant un réseau Feistel dans sa permutation G, et Threefish (partie de Skein ) est un chiffrement par bloc non Feistel qui utilise une fonction MIX semblable à Feistel.

Liste des chiffrements Feistel

Feistel ou Feistel modifié:

Feistel généralisé:

• CAST-256
• CLEFIA
• MacGuffin
• RC2
• RC6
• Bonite
• SMS4

Voir également

• Cryptographie
• Chiffrement de flux
• Réseau de substitution-permutation
• Le schéma de levage pour la transformation en ondelettes discrète a à peu près la même structure
• Cryptage préservant le format
• Schéma Lai – Massey

Références