Fonction à sens unique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une fonction à sens unique 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.

Exemple[modifier | modifier le code]

Un exemple classique de fonction à sens unique est le problème du sac à dos: soit un ensemble de n nombres I={a_1, a_2,...a_n} et un sous-ensemble J de I, il est très facile de calculer la somme m des éléments de J. En revanche, I et m étant fixés, il est très difficile de trouver J sous ensemble de I tel que la somme des éléments de J soit égale à m. La théorie de la complexité montre d'ailleurs que le problème du sac à dos est NP-complet, c'est-à-dire qu'il n'existe presque certainement aucun algorithme capable de calculer une solution en un temps qui croisse comme un polynôme en n. Ce problème fut d'ailleurs à la base d'un des premiers algorithmes de cryptographie asymétrique, l'algorithme de Merkle-Hellman.

Un autre exemple est celui de la factorisation d'un entier. Soient deux nombres premiers p et q. Calculer x = pq est facile même si p et q sont très grands. Par contre, le meilleur algorithme (le General Number Field Sieve)[réf. souhaitée] connu aujourd'hui pour retrouver p et q à partir de x a un temps de calcul qui croît comme

O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right).

où b est le nombre de bits de x (cet algorithme n'est donc pas polynomial, et le temps de calcul croît rapidement en fonction de la taille des données). 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.

Fonctions à brèche secrète[modifier | modifier le code]

Certaines fonctions à sens unique sont appelées fonctions à brèche secrète en raison d'une « brèche secrète » 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 brèche.

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 à brèche secrète, car les groupes considérés ne semblent pas avoir de trappes connues[réf. nécessaire].

Bibliographie[modifier | modifier le code]

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