Schéma de Feistel

Schéma de Feistel

Réseau de Feistel

Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d'après le cryptologue d'IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure offre plusieurs avantages, le chiffrement et le déchiffrement ont une architecture similaire voire identique dans certains cas. L'implémentation matérielle est aussi plus facile avec un tel système même si les choses ont passablement changé depuis la fin des années 1970. Un réseau de Feistel repose sur des principes simples dont des permutations, des substitutions, des échanges de blocs de données et une fonction prenant en entrée une clé intermédiaire à chaque étage.

Il est vraisemblable que Feistel ne soit pas le seul inventeur de cette architecture. Durant une conférence, Don Coppersmith a laissé entendre que Bill Notz et Lynn Smith (de l'équipe d'IBM travaillant sur DES) avaient été en grande partie à l'origine du réseau de Feistel tel que nous le connaissons.

Sommaire

Structure

Réseau de Feistel à n tours utilisant l'opérateur XOR

Un réseau de Feistel est subdivisé en plusieurs tours ou étages. Dans sa version équilibrée, le réseau traite les données en deux parties de taille identique. À chaque tour, les deux blocs sont échangés puis un des blocs est combiné avec une version transformée de l'autre bloc. Pour simplifier, la moitié des données sont encodées avec la clef, puis le résultat de cette opération est ajouté grâce à un xor (ou exclusif) à l'autre moitié des données. Puis au tour suivant, on inverse : c'est au tour de la dernière moitié d'être chiffrée puis d'être ajoutée avec un xor à la première moitié, sauf qu'on utilise les données chiffrées précédemment (sinon ça ne servirait à rien de faire plus de deux tours). Le schéma ci-contre montre le cheminement des données (le "plus" entouré représente le xor). Chaque tour utilise une clé intermédiaire, en général tirée de la clé principale via une génération appelée key schedule. Les opérations effectuées pendant l'encryptage avec ces clefs intermédiaires sont spécifiques à chaque algorithme.

Dans le cas de DES, le réseau de Feistel possède 16 tours, chacun avec une sous-clé. Ces différentes clés permettent d'améliorer la robustesse d'un algorithme face à la cryptanalyse.

Une variante, le réseau de Feistel non-équilibré coupe les données en deux parties de tailles différentes. Cette variante a été utilisée dans MacGuffin de Bruce Schneier, ou encore Skipjack, candidat pour AES.

Définition formelle

Une définition formelle d'un réseau de Feistel peut être donnée sous plusieurs formes. Nous reprenons ici la notation utilisée par Knudsen dans Partial and Higher Order Differentials and Applications to DES.

C_0^L = P^L~ et C_0^R = P^R~
C_i = (C_i^L, C_i^R) = (C_{i-1}^R, f(C_{i-1}^R, K_i) + C_{i-1}^L)~
C^L = C_r^L~ et C^R = C_r^R~
  • l'exposant représente la sous-partie du bloc considérée (L à gauche, R à droite).
  • P~ correspond au bloc de texte clair, P_i^L correspond au bloc de gauche à l'entrée du tour i~
  • C~ correspond au bloc de texte chiffré, C_i^R correspond au bloc de droite à la sortie du tour i~
  • K_i~ est la clé du tour i~, elle est calculée grâce à un key schedule de la clé principale
  • r~ est le nombre de tours dans l'algorithme
  • +~ est une opération dans un groupe commutatif (souvent un XOR ou une addition)

Composition des tours

Chaque tour applique plusieurs transformations sur les données provenant du tour précédent :

On utilise les termes de confusion et diffusion pour décrire la propagation des informations dans la structure (termes utilisés par Claude Shannon). En effet, une modification d'un bit en entrée produira des variations très importantes dans les stages intermédiaires et en sortie. Un terme plus récent pour décrire ce phénomène est l'effet avalanche. L'utilisation des permutations permet d'améliorer la diffusion alors que les substitutions ont pour effet d'augmenter la confusion.

Cryptanalyse

Les schémas de Feistel ont été largement analysés et examinés par les experts. Plusieurs attaques sont possibles mais les deux principales sont :

Ces méthodes ont fait leur preuve sur DES et sur d'autres algorithmes similaires. Mais cela ne signifie pas que l'utilisation d'un réseau de Feistel va obligatoirement entraîner des vulnérabilités significatives. Grâce à l'ajout de différentes techniques et avec une conception bien menée, on peut considérablement améliorer la résistance d'un algorithme basé sur Feistel. C'est le cas pour Blowfish qui est cryptographiquement sûr en date de décembre 2008.

En général, les cryptanalystes s'attaquent en premier à des versions amoindries des chiffrements, c’est-à-dire comportant moins de tours.

Algorithmes

Un grand nombre d'algorithmes utilise des réseaux de Feistel, avec des variantes. Voici une liste non-exhaustive :


  • Portail de la cryptologie Portail de la cryptologie

Ce document provient de « R%C3%A9seau de Feistel ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Schéma de Feistel de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Schéma de Lai-Massey — Construction de Lai Massey Construction de Lai Massey dans IDEA La construction de Lai Massey est une structure utilisée dans les algorithmes de chiffrement par bloc. Elle a été inventée par Xuejia Lai et James Massey, publiée …   Wikipédia en Français

  • Reseau de Feistel — Réseau de Feistel Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d après le cryptologue d IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure… …   Wikipédia en Français

  • Réseau de feistel — Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d après le cryptologue d IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure offre plusieurs… …   Wikipédia en Français

  • Réseau de Feistel — Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d après le cryptologue d IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure offre plusieurs… …   Wikipédia en Français

  • MacGuffin (cryptologie) —  Pour l’article homonyme, voir MacGuffin pour l emploi au cinéma.  MacGuffin Tour de MacGuffin avec un schéma de Feistel non équilibré Résumé …   Wikipédia en Français

  • Macguffin (cryptologie) —  Pour l’article homonyme, voir MacGuffin pour l emploi au cinéma.  MacGuffin …   Wikipédia en Français

  • Blowfish — Résumé Concepteur(s) Bruce Schneier Première publication 1993 Dérivé de …   Wikipédia en Français

  • Algorithme DES — Data Encryption Standard Pour les articles homonymes, voir DES. DES (Data Encryption Standard) …   Wikipédia en Français

  • Data Encryption Standard — Pour les articles homonymes, voir DES. DES (Data Encryption Standard) fonction F de DES …   Wikipédia en Français

  • Data encryption standard — Pour les articles homonymes, voir DES. DES (Data Encryption Standard) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”