Fonction courbe

Fonction courbe

Une fonction booléenne avec un nombre pair de variables est dite fonction courbe -- bent dans la terminologie anglosaxonne -- si sa non-linéarité est maximale. Cela correspond à être à distance maximale -- pour la distance de Hamming -- de l'ensemble des fonctions booléennes linéaires, encore appelé code de Reed et Müller d'ordre 1. On dispose d'une borne générale sur la non-linéarité des fonctions booléennes, mais cette borne ne peut être atteinte que lorsque le nombre de variable est pair. De plus, dans ce cas, on sait construire des fonctions atteignant cette borne, par exemple la fonction

f(x_1,...,x_n)=\sum_{x=1}^{n/2} x_ix_{n/2+i}

est courbe. L'ensemble des fonctions affines formant un espace vectoriel sur le corps à deux éléments, il est facile de voir que si f est courbe, toute fonction f + a, avec a fonction affine, est également courbe, puisque dans ce cas f et f + a sont à la même distance de l'ensemble des fonctions affines.

Cet objet mathématique a été introduit par O. Rothaus en 1976 (mais il le connaissait déjà durant les années 60).

Les propriétés hautement non-linéaires des fonctions courbes sont utilisées en cryptologie pour constituer des S-Boxes (tables de substitution) comme par exemple dans le chiffrement CAST-128, ce principe a été considéré dès 1992 par C. Adams dans "On immunity against Biham and Shamir's differential cryptanalysis".

Une fonction courbe a l'avantage d'avoir un spectre plat (voir transformée de Fourier ou transformation de Hadamard-Walsh), ce qui fait qu'il n'existe pas de «bonne» approximation linéaire. Vu la définition de ces fonctions, cela paraît naturel. Cette caractéristique permet de contrer la cryptanalyse linéaire.

Un inconvénient important de ces fonctions est de ne pas être équilibrées : elles ne peuvent pas prendre autant de fois la valeur 0 que la valeur 1. De ce fait, certaines applications sont à exclure car le biais introduit par une fonction courbe rendrait le système de chiffrement vulnérable à des attaques différentes de la cryptanalyse linéaire. D'une certaine manière c'est un problème récurrent dans la conception d'algorithmes de chiffrements symétriques : on ne peut pas simultanément avoir la meilleure résistance à toutes les attaques connues. Les fonctions courbes sont optimales pour la cryptanalyse linéaire, mais pas pour les attaques par corrélation par exemple.

Voir aussi

Liens externes


Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Fonction Courbe — Une fonction booléenne avec un nombre pair de variables est dite fonction courbe bent dans la terminologie anglosaxonne si sa non linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l ensemble des… …   Wikipédia en Français

  • Fonction bent — Fonction courbe Une fonction booléenne avec un nombre pair de variables est dite fonction courbe bent dans la terminologie anglosaxonne si sa non linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l… …   Wikipédia en Français

  • Fonction Booléenne — Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l on s attache aux propriétés algébriques de ces… …   Wikipédia en Français

  • Fonction booleenne — Fonction booléenne Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l on s attache aux propriétés… …   Wikipédia en Français

  • Fonction booléenne — Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l on s attache aux propriétés algébriques de ces… …   Wikipédia en Français

  • Courbe Elliptique — Une sélection de courbes cubiques réelles définies par l équation y2 = x3 + ax + b.. La région montrée est [ 3,3]². La courbe pour a=b=0 n est pas elliptique. En mathématiques, une courbe elliptique est un cas particulier de courbe algébrique,… …   Wikipédia en Français

  • Courbe logistique — Fonction logistique (Verhulst) Fonction logistique, cas particulier: sigmoïde. En mathématiques les fonctions logistiques sont les fonctions ayant pour expression où K et r sont des réels positifs et a un réel quelconque …   Wikipédia en Français

  • Fonction Logistique (Verhulst) — Fonction logistique, cas particulier: sigmoïde. En mathématiques les fonctions logistiques sont les fonctions ayant pour expression où K et r sont des réels positifs et a un réel quelconque …   Wikipédia en Français

  • Fonction logistique (verhulst) — Fonction logistique, cas particulier: sigmoïde. En mathématiques les fonctions logistiques sont les fonctions ayant pour expression où K et r sont des réels positifs et a un réel quelconque …   Wikipédia en Français

  • Courbe Plane — En géométrie, une courbe plane est une courbe qui est entièrement contenue dans un (unique) plan, et qui est identifiable à une fonction continue : où I est un intervalle de l ensemble des nombres réels. L image d une courbe est aussi… …   Wikipédia en Français

Share the article and excerpts

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