Fonction à sens unique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Sens unique.
Panneau de signalisation routière de sens unique

Une fonction à sens unique (ou one-way function en anglais) est une fonction qui peut être aisément calculée, mais qui est difficile à inverser — c'est-à-dire qu'étant donnée une image, il est difficile de lui trouver un antécédent. Les fonctions à sens unique sont utilisées en cryptographie asymétrique et dans les fonctions de hachage cryptographiques.

La théorie de la complexité des algorithmes est un élément central de la notion de fonction à sens unique. En effet, cette théorie donne un sens mathématique à la notion floue de difficulté à trouver un antécédent, et son existence implique l'inégalité entre les classes P et NP[1].

Définition[modifier | modifier le code]

Une fonction calculable en temps polynomial est dite à sens unique[1] si pour tout algorithme polynomial probabiliste , il existe une fonction négligeable telle que pour tout on ait

Implications théoriques[modifier | modifier le code]

L’existence de fonctions à sens unique a de nombreuses implications en cryptographies, en particulier elles permettent de construire : des générateurs et fonctions pseudo-aléatoires, des schémas de signature numérique, des schémas de mise en gage...[2]

Fonctions possibles[modifier | modifier le code]

Comme l’existence des fonctions à sens unique impliquerait la distinction entre les classes P et NP qui reste en 2017 une question ouverte, on ne peut considérer que des constructions candidates .

Le problème du sac à dos[modifier | modifier le code]

Un exemple classique de fonction à sens unique est le problème du sac à dos : soit un ensemble de nombres et un sous-ensemble de , il est très facile de calculer la somme des éléments de . En revanche, et étant fixés, il est très difficile de trouver sous ensemble de tel que la somme des éléments de soit égale à . La théorie de la complexité montre d'ailleurs que le problème du sac à dos est NP-complet, c'est-à-dire qu'il existe des instances supposées très difficile du point de vue du temps de calcul. Ce problème fut d'ailleurs à la base d'un des premiers algorithmes de cryptographie asymétrique, l'algorithme de Merkle-Hellman.

En revanche la NP-complétude du problème ne garantit que la difficulté des instances pire cas du problème du sac à dos, et non sa difficulté en moyenne, c'est ce qui fait qu'il faut faire attention aux paramètres du problème pris, ainsi par exemple la version initiale du cryptosystème de Merkle-Hellman s'est montré vulnérable[3][4].

La factorisation d'un entier[modifier | modifier le code]

Un autre exemple est celui de la factorisation d'un entier. Étant donnés deux nombres premiers et , calculer le est facile même si et sont très grands[note 1]. Par contre, le crible algébrique est le meilleur algorithme connu aujourd'hui pour retrouver et à partir de  ; il a un temps de calcul qui croît comme

où b est le nombre de bits de . Cet algorithme n’est pas de complexité polynomiale, mais sous-exponentielle (c'est-à-dire que sa complexité croît asymptotiquement moins vite que toute fonction exponentielle). Il faut cependant savoir qu'il n'existe pas de résultat en théorie de la complexité permettant de garantir l'appartenance ou non du problème de factorisation à la classe des problèmes polynomiaux. Le problème de factorisation est à la base du cryptosystème RSA.

Le logarithme discret[modifier | modifier le code]

Le problème du logarithme discret dit qu’il est difficile d’inverser la fonction pour générateur d'un groupe cyclique d’ordre suffisamment élevé, alors que le calcul de étant donné se fait efficacement par exponentiation rapide. Dans le cas d’un groupe générique (c'est-à-dire un groupe définit par sa table d’opérations), les meilleurs algorithmes ne peuvent résoudre le logarithme discret en moins de opérations de groupe ; où n représente la taille du groupe[5].

Mais en pratique, un groupe générique aléatoire est impossible à avoir, puisqu’il s’agirait de décrire entièrement la table de multiplication du groupe. C’est pourquoi les groupes utilisées sont soit définis sur où les attaques de crible algébrique sont de même complexité que pour la multiplication, soit définis sur des courbes elliptiques, où il n’existe pas d’attaques sur des courbes quelconques. En revanche le choix de la courbe est important puisque des courbes faibles (ne respectant pas l’hypothèse que le logarithme discret est difficile par exemple) existent[6].

Fonctions à porte dérobée[modifier | modifier le code]

Certaines fonctions à sens unique sont appelées fonctions à porte dérobée en raison d'une « porte dérobée » qui permet à quelqu'un la connaissant de revenir facilement en arrière. Ce principe est utilisé entre autres pour le cryptosystème RSA, la clé privée (obtenue à partir des nombres p et q ci-dessus) étant la porte dérobée.

De telles fonctions sont difficiles à trouver et tous les problèmes ne s'y prêtent pas. On pense que les fonctions basées sur le problème du logarithme discret (modulo un nombre premier ou défini sur le groupe d'une courbe elliptique) ne sont pas des fonctions à porte dérobée, car les groupes considérés ne semblent pas avoir de trappes connues[réf. nécessaire]. La construction de cryptosystèmes à base du logarithme discret se fait en utilisant pour un secret comme un masque jetable. Ainsi sans connaître , il est difficile de revenir en arrière, mais le connaissant on peut retirer le masque jetable en calculant .

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « One-way function » (voir la liste des auteurs).

Notes[modifier | modifier le code]

  1. Par exemple la multiplication naïve le calcule en

Références[modifier | modifier le code]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]