AccueilđŸ‡«đŸ‡·Chercher

Fonction Ă  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.

Panneau de signalisation routiĂšre de sens unique

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

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

L’existence de fonctions Ă  sens unique a de nombreuses implications en cryptographie, 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

La vanne inventée par Nikola Tesla (en) est une image d'une fonction à sens unique. Le liquide circule sans problÚme de droite à gauche, mais est bloquée ou presque de gauche à droite.

Comme l’existence des fonctions Ă  sens unique implique la distinction entre les classes P et NP qui reste une option ouverte Ă  laquelle la majoritĂ© des scientifiques adhĂšrent, on considĂšre gĂ©nĂ©ralement que les solutions proposĂ©es sont tout Ă  fait crĂ©dibles.

Le problĂšme du sac Ă  dos

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 difficiles 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ée vulnérable[3][4].

La factorisation d'un entier

Un autre exemple est celui de la factorisation d'un entier. Étant donnĂ©s deux nombres premiers et , calculer le produit est facile mĂȘme si et sont trĂšs grands[note 1]. Par contre, remonter Ă  et connaissant est plus difficile. 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

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Ă©fini 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

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. 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

(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

  1. Par exemple la multiplication naĂŻve le calcule en

Références

Annexes

Bibliographie

Articles connexes


Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.