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 ${\displaystyle f:\{0,1\}^{\star }\to \{0,1\}^{\star }}$ est dite à sens unique^[1] si pour tout algorithme polynomial probabiliste ${\displaystyle A}$, il existe une fonction négligeable ${\displaystyle \epsilon$ :\mathbb {N} \to [0;1]} telle que pour tout ${\displaystyle n}$ on ait

${\displaystyle \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...^[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 ${\displaystyle n}$ nombres ${\displaystyle I={a_{1},a_{2},...a_{n}}}$ et un sous-ensemble ${\displaystyle J}$ de ${\displaystyle I}$, il est très facile de calculer la somme ${\displaystyle m}$ des éléments de ${\displaystyle J}$. En revanche, ${\displaystyle I}$ et ${\displaystyle m}$ étant fixés, il est très difficile de trouver ${\displaystyle J}$ sous ensemble de ${\displaystyle I}$ tel que la somme des éléments de ${\displaystyle J}$ soit égale à Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle 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^[3],[4].

La factorisation d'un entier

Un autre exemple est celui de la factorisation d'un entier. Étant donnés deux nombres premiers ${\displaystyle p}$ et ${\displaystyle q}$, calculer le produit ${\displaystyle x=pq}$ est facile même si ${\displaystyle p}$ et ${\displaystyle q}$ sont très grands^{[note 1]}. Par contre, remonter à ${\displaystyle p}$ et ${\displaystyle q}$ connaissant ${\displaystyle x}$ est plus difficile. Le crible algébrique est le meilleur algorithme connu aujourd'hui pour retrouver ${\displaystyle p}$ et ${\displaystyle q}$ à partir de ${\displaystyle x}$ ; il a un temps de calcul qui croît comme

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x\mapsto g^{x}}$ pour ${\displaystyle g}$ générateur d'un groupe cyclique ${\displaystyle G}$ d’ordre suffisamment élevé, alors que le calcul de ${\displaystyle g^{x}}$ étant donné ${\displaystyle 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 ${\displaystyle {\mathcal {O}}\left(\exp \left({\tfrac {|n|_{2}}{2}}\right)\right)}$ 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 ${\displaystyle \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^[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^{[réf. nécessaire]}. La construction de cryptosystèmes à base du logarithme discret se fait en utilisant ${\displaystyle g^{s}}$ pour un secret ${\displaystyle s}$ comme un masque jetable. Ainsi sans connaître ${\displaystyle s}$, il est difficile de revenir en arrière, mais le connaissant on peut retirer le masque jetable en calculant ${\displaystyle g^{-s}}$.

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 ${\displaystyle {\mathcal {O}}(|p|\cdot |q|).}$

Références

1. Arora et Barak 2009.
2. Katz et Lindell 2014.
3. Shamir 1982.
4. Adleman 1982.
5. Shoup 1997.
6. Do Weak Elliptic Curves Exist? sur Stack Overflow

Annexes

Bibliographie

• [Shamir 1982] (en) Adi Shamir, « A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems », FOCS'82, Springer,‎ 1982 (DOI 10.1109/SFCS.1982.5)
• [Adleman 1982] (en) Leonard Adleman, « On breaking the titrated Merkle-Hellman public-key cryptosystem », Crypto'82, Springer,‎ 1982 (DOI 10.1007/978-1-4757-0602-4_29)
• [Shoup 1997] Victor Shoup, « Lower bounds for discrete logarithms and related problems », Eurocrypt,‎ 1997 (lire en ligne [PDF])
• [Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, 2014, 583 p. (ISBN 978-1-4665-7026-9, lire en ligne), « Chapitre 6.1 One Way Functions »
• [Arora et Barak 2009] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 9.2.1 (« One way functions: Definition and some examples »)
• Jean-Paul Delahaye, « Des progrès bienvenus en cryptologie », Pour la Science, n^o 545,‎ mars 2023.

Articles connexes

• Fonction à trappe
• Fonction pseudo-aléatoire
• Fonction de hachage cryptographique

• Portail de la cryptologie
• Portail des mathématiques
• Portail de l'informatique théorique