Les schémas de Feistel
Les algorithmes à clé secrète réduite cherchent, bien sûr, à tendre vers la perfection. Et la perfection, en cryptographie, c'est l'aléatoire : il faut que le message codé paraisse aussi aléatoire que possible, pour limiter au minimum les risques d'une attaque par analyse du texte chiffré, de ses redondances, etc... Le problème est que, si l'on sait depuis longtemps construire des fonctions qui ont l'air aléatoire, on ne savait pas avant les travaux de Feistel construire des bijections aléatoires. La solution apportée par Horst Feistel, ingénieur chez IBM qui dirigea l'équipe qui conçut l'algorithme de chiffrement DES, est très élégante : on suppose par exemple qu'on a une fonction f "presque aléatoire" qui prend comme argument un mot de n bits, et renvoie un mot de n bits (qui donne l'impression d'avoir été choisi au hasard). f n'est pas supposée bijective, c'est-à-dire que deux mots différents peuvent avoir la même image par f (ceci signifie encore que, si on dispose d'un mot de n bits chiffré par f, on ne peut pas retrouver le mot initial). Un algorithme utilisant un schéma de Feistel va procéder en chiffrant des blocs de 2n bits, qu'on partage en 2, partie gauche G, partie droite D. L'image du bloc (G,D) par le schéma de Feistel est le bloc (L,R), avec $L=D$, et $R= G \oplus f(D)$ ou $\oplus$ désigne le "ou exclusif" bit à bit. Cette transformation est cette fois bijective, car si on a un tel couple (L,R), on retrouve $(G,D)$ par $D=L$ et $G=R \oplus f(L)$. Bien sûr, la partie droite du texte clair se trouve inchangée en partie gauche du texte chiffré. Pour éviter cette faiblesse, on répète le schéma de Feistel un certain nombre de fois (on parle de tours - le DES en comporte 16).
Consulter aussi