Dans un algorithme de chiffrement itératif par blocs, le chiffré d'un
bloc de message est obtenu en itérant une permutation paramétrée par
une clef secrète dont la valeur est modifiée à chaque tour. Les
clefs utilisées successivement dans les différentes itérations sont en
général produites à partir d'une unique clef-maître. De par sa rapidité et sa
simplicité, ce principe est employé dans tous les algorithmes de
chiffrement à clef secrète utilisés actuellement (DES, IDEA, SAFER...).
Tous ces systèmes sont cependant sujets à la cryptanalyse
différentielle, introduite en 1991 par Biham et
Shamir, ainsi qu'à la cryptanalyse linéaire présentée par Matsui en
1993.
Résistance à la cryptanalyse différentielle
La cryptanalyse différentielle consiste à chiffrer deux
messages clairs dont la différence pour une certaine loi de groupe
(généralement le OU exclusif bit-à-bit) est fixée, et à estimer la
valeur de la différence de leurs images en sortie de l'avant-dernière
itération de l'algorithme de chiffrement. Si, pour une différence
fixée des textes clairs, la distribution de probabilités de la
différence des sorties de l'avant-dernier tour s'éloigne de la
distribution uniforme, il est possible de déterminer la valeur de la
clef secrète utilisée à la dernière itération dès que l'on connaît
suffisamment de couples clairs/chiffrés.
Un chiffrement de Feistel, tel le DES, opérant sur des blocs de message de 2m bits (on choisit généralement m égal à 32 ou 64), est construit sur la base d'une permutation f de GF(2^m). Sa résistance à la cryptanalyse différentielle dépend alors du nombre de solutions x de l'équation f(x+a) +f(x) = b pour a et b non nuls. Lorsque toutes les équations de ce type ont au plus d solutions, la fonction f est dite différentiellement d-uniforme et la complexité de la cryptanalyse différentielle du système est une fonction en 1/(d^2).
Un premier axe de recherche est donc de trouver des fonctions f optimales en ce sens, i.e. des permutations différentiellement 2-uniformes, également appelées permutations presque parfaitement non-linéaires (APN). Ces permutations correspondent également à des codes linéaires binaires dont la distance minimale est au moins 5. Jusqu'ici, très peu de familles infinies de permutations APN sont connues et la plupart d'entre elles sont extrêmement vulnérables à d'autres méthodes de cryptanalyse (cryptanalyse linéaire ou cryptanalyse différentielle d'ordre supérieur).
Un second problème vient du fait que l'on ne connaît aucune
permutation de GF(2^m) qui soit APN lorsque m est
pair. Or ce cas est le plus fréquent en cryptographie car on chiffre
généralement des blocs de message dont le nombre de bits est une
puissance de 2. Si, comme le suggèrent les explorations numériques,
de telles permutations n'existent pas dans ce cas, les meilleures
permutations au regard de la cryptanalyse différentielle seraient
celles qui sont différentiellement 4-uniformes. Par une étude poussée
de la cryptanalyse différentielle des chiffrements de Feistel (et
notamment de l'hypothèse de l'équivalence stochastique), nous
avons récemment construit plusieurs familles infinies de permutations
différentiellement 4-uniformes sur GF(2^m) pour n pair.
Résistance à la cryptanalyse linéaire
Pour résister à la cryptanalyse linéaire
les fonctions utilisées dans un
système de chiffrement à clef secrète doivent être aussi éloignées que
possible des fonctions affines. Ainsi une permutation de
GF(2^m) offre la meilleure résistance possible à la cryptanalyse
linéaire si sa non-linéarité est maximale.
Dans le cas où m est impair, la valeur de la plus grande non-linéarité
possible est connue ; les fonctions qui l'atteignent sont appelées
fonctions presque courbes (AB).
Cette propriété apparaît également dans l'étude des suites de longueur maximale ( m-sequences). En effet les exposants s qui sont tels que la permutation x -> x^s est de non-linéarité maximale coïncident avec les valeurs de s pour lesquelles la corrélation croisée entre une suite de longueur maximale et sa décimation par s est minimale.
C. Carlet, P. Charpin et V. Zinoviev ont récemment montré que la non-linéarité d'une fonction f de GF(2^m) dans GF(2^m) est donnée par la distance minimale du dual d'un code linéaire binaire de longueur (2^m-1). En particulier quand f est la fonction puissance x -> x^s, ce code est le code cyclique à deux zéros ayant pour ensemble de définition {1,s}. On sait également que, pour m impair, toute fonction AB sur GF(2^m) est APN, mais la réciproque est fausse. Dans un travail commun avec Pascale Charpin et Hans Dobbertin, nous avons montré que cette condition devient nécessaire et suffisante si l'on y ajoute une condition sur la divisibilité des poids du dual du code associé à la fonction AB. En combinant cette nouvelle caractérisation des fonctions AB et le théorème de McEliece sur la divisibilité des codes cycliques, nous avons notamment démontré une conjecture énoncée par Welch en 1968 stipulant que, pour m=2t+1 et s=2^t+3, la fonction x -> x^s est AB sur GF(2^m).
Retour à la page principale.