Etude des générateurs de permutations pseudo-aléatoires basés sur le schéma du DES / Jacques Patarin ; sous la direction de Paul Camion

Bibliogr.

Thèse de doctorat informatique 1991 université Paris VI

Dans la partie I, on présente une nouvelle démonstration d'un résultat obtenu en 1988 par M. LUBY et C. RACKOFF sur les générateurs de permutations basés sur le schéma du D.E.S. On met ainsi en lumière d'importantes «propriétés de base» de ces générateurs. Dans la partie II, les principaux nouveaux résultats obtenus sont les suivants: 1) il est possible d'obtenir un générateur de permutations pseudo-aléatoires avec trois passes du schéma du D.E.S. et une unique fonction aléatoire; 2) il est possible d'obtenir un générateur de permutations super pseudo-aléatoires avec quatre passes du schéma du D.E.S. et une unique fonction aléatoire. Ces résultats sont optimaux. Dans la partie III on observe finement ce qui se passe lorsque l'on augmente le nombre de passes. On observe alors une décroissance exponentielle de la probabilité de distinguer les permutations générées de permutations aléatoires. Enfin, la partie IV, indépendante des autres, indique comment casser la fonction de hachage proposée par I. DAMGARD à CRYPTO'89