Construction de Luby-Rackoff

{{#invoke:Bandeau|ébauche}}

En cryptologie, la construction de Luby-Rackoff est une technique permettant de construire des permutations dont on peut prouver qu'elles se comportent pratiquement comme des permutations pseudo-aléatoires, si on suppose l'existence de fonctions pseudo-aléatoires. De telles permutations jouent un rôle important dans la conception de cryptosystèmes, notamment des algorithmes de chiffrement par bloc, en ce qu'elles facilitent grandement l'analyse de leur sécurité. Il est toutefois important de noter que la construction de Luby-Rackoff est un modèle idéalisé<ref name=":0">Modèle:Chapitre</ref><ref group="Note">Un exemple notable est la cryptanalyse initiale de DEAL, qui est basé sur une construction de Luby-Rackoff de profondeur 7 ou 8.</ref>.

La construction s'appuie sur les théorèmes de Luby-Rackoff<ref name=":2" />, énoncés en 1988 par Michael Luby et Charles Rackoff<ref>{{#invoke:Langue|indicationDeLangue}} M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, vol. 17, no 2, pp. 373--386, April 1988.</ref>, et dont l'importance dépasse cette seule utilisation<ref name=":1">Modèle:Chapitre</ref><ref>Modèle:Article</ref>.

Les longueurs, de 3 et 4 respectivement, sont optimales<ref>Modèle:Chapitre</ref><ref name=":1" />. D'un point de vue théorique, ce résultat montre que les fonctions pseudo-aléatoires (VRF) suffisent pour construire des permutations pseudo-aléatoires. Comme par ailleurs l'existence de générateurs pseudo-aléatoires (PRNG) permet classiquement de construire des VRF<ref>Modèle:Article</ref>, on obtient une chaîne de réductions : <math>\mathrm{PRNG} \leq \mathrm{VRF} \leq \mathrm{PRP}</math>.

Depuis leur première preuve en 1988, les théorèmes de Luby-Rackoff ont été simplifiés et étendus de plusieurs manières<ref>Modèle:Chapitre</ref><ref name=":0" /><ref>Modèle:Chapitre</ref><ref>Modèle:Chapitre</ref><ref>Modèle:Article</ref><ref>Modèle:Chapitre</ref>. Toutefois, les progrès dans la cryptanalyse des chiffrements à base de réseau de Feistel<ref name=":2">Modèle:Ouvrage</ref>, des questions de performance, de nouveaux modèles d'attaque, et la découverte de nouvelles constructions pour le chiffrement par bloc (comme la construction de Lai-Massey<ref>Modèle:Chapitre</ref>) ont contribué à réduire la popularité des réseaux de Feistel utilisés dans la construction de Luby-Rackoff.

Notes et références

Notes

<references group="Note" />

Références

<references/>Modèle:PaletteModèle:Portail