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

## Définition

Une fonction calculable en temps polynomial $f:\{0,1\}^{\star }\to \{0,1\}^{\star }$ est dite à sens unique si pour tout algorithme polynomial probabiliste $A$, il existe une fonction négligeable $\epsilon :\mathbb {N} \to [0;1]$ telle que pour tout $n$ on ait
    $\Pr _{x\in _{R}\{0,1\}^{n},~y=f(x)}[A(y)=x'{\mbox{ telle que }}f(x')=y]<\epsilon (n).$

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

## Fonctions possibles

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 $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 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$^,$.

### La factorisation d'un entier

Un autre exemple est celui de la factorisation d'un entier. Étant donnés deux nombres premiers $p$ et $q$, calculer le produit $x=pq$ est facile même si $p$ et $q$ sont très grands. Par contre, remonter à $p$ et $q$ connaissant $x$ est plus difficile. Le crible algébrique est le meilleur algorithme connu aujourd'hui pour retrouver $p$ et $q$ à partir de $x$ ; il a un temps de calcul qui croît comme
    $L\left({\sqrt[{3}]{\frac {64}{9}}},{\frac {1}{3}}\right)=O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right).$
où b est le nombre de bits de $x$. 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 $x\mapsto g^{x}$ pour $g$ générateur d'un groupe cyclique $G$ d’ordre suffisamment élevé, alors que le calcul de $g^{x}$ étant donné $x$ 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 ${\mathcal {O}}\left(\exp \left({\tfrac {|n|_{2}}{2}}\right)\right)$ opérations de groupe ; où n représente la taille du groupe.
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 $\mathbb {F} _{q}$ 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.

## 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 $g^{s}$ pour un secret $s$ comme un masque jetable. Ainsi sans connaître $s$, il est difficile de revenir en arrière, mais le connaissant on peut retirer le masque jetable en calculant $g^{-s}$.