Voir la source de Fonction à sens unique

{{Voir homonymes|Sens unique}}
[[Fichier:Sens unique.JPG|vignette|Panneau de [[signalisation routière]] de sens unique]]
Une '''fonction à sens unique''' (ou '''{{langue|en|one-way function}}''' en anglais) est une [[Fonction (mathématiques)|fonction]] qui peut être aisément calculée, mais qui est difficile à inverser — c'est-à-dire qu'étant donnée une [[Image (mathématiques)|image]], il est difficile de lui trouver un [[Antécédent (mathématiques)|antécédent]]. Les fonctions à sens unique sont utilisées en [[cryptographie asymétrique]] et dans les [[fonction de hachage|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'[[Problème P=NP|inégalité entre les classes]] ''P'' et ''NP''{{sfn|Arora|Barak|2009}}.

== Définition ==
Une fonction [[P (complexité)|calculable en temps polynomial]] <math>f : \{0,1\}^\star \to \{0,1\}^\star</math> est dite à ''sens unique''{{sfn|Arora|Barak|2009}} si pour tout algorithme [[PP (complexité)|polynomial probabiliste]] <math>A</math>, il existe une [[fonction négligeable (informatique)|fonction négligeable]] <math> \epsilon : \N \to [0;1]</math> telle que pour tout <math>n</math> on ait
: <math> \Pr_{x \in_R \{0,1\}^n,~y = f(x)} [A(y) = x' \mbox{ telle que } f(x') = y] < \epsilon(n). </math>

== Implications théoriques ==
L’existence de fonctions à sens unique a de nombreuses implications en cryptographie, en particulier elles permettent de construire : des [[générateur pseudo-aléatoire|générateurs]] et [[fonction pseudo-aléatoire|fonctions pseudo-aléatoires]], des schémas de [[signature numérique]], des schémas de [[mise en gage]]...{{sfn|Katz|Lindell|2014}}

== Fonctions possibles ==
[[File:Tesla valve principle.svg|thumb|La {{Lien|langue=en|fr=vanne inventée par Nikola Tesla|trad=Tesla valve}} 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 [[Problème P = NP|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 <math>n</math> nombres <math>I={a_1, a_2,...a_n}</math> et un sous-ensemble <math>J</math> de <math>I</math>, il est très facile de calculer la somme <math>m</math> des éléments de <math>J</math>. En revanche, <math>I</math> et <math>m</math> étant fixés, il est très difficile de trouver <math>J</math> sous ensemble de <math>I</math> tel que la somme des éléments de <math>J</math> soit égale à <math>m</math>. 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 [[Problème P=NP|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{{sfn|Shamir|1982}}{{,}}{{sfn|Adleman|1982}}.

=== La factorisation d'un entier ===
Un autre exemple est celui de la [[factorisation]] d'un entier. Étant donnés deux nombres premiers <math>p</math> et <math>q</math>, calculer le produit <math>x = pq</math> est facile même si <math>p</math> et <math>q</math> sont très grands{{note|groupe=note|texte=Par exemple la multiplication naïve le calcule en <math>\mathcal O(|p|\cdot|q|).</math>}}. Par contre, remonter à  <math>p</math> et <math>q</math> connaissant <math>x</math> est plus difficile. Le [[crible algébrique]] est le meilleur algorithme connu aujourd'hui pour retrouver <math>p</math> et <math>q</math> à partir de <math>x</math> ; il a un temps de calcul qui croît comme
:<math>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\over3} (\log b)^{2\over3}\right)\right).</math>
où b est le nombre de bits de <math>x</math>. 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é algorithmique|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 [[Rivest Shamir Adleman|RSA]].

=== Le logarithme discret ===
Le problème du [[logarithme discret]] dit qu’il est difficile d’inverser la fonction <math>x \mapsto g^x</math> pour <math>g</math> générateur d'un groupe cyclique <math>G</math> d’ordre suffisamment élevé, alors que le calcul de <math>g^x</math> étant donné <math>x</math> 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 <math>\mathcal O\left(\exp\left(\tfrac{|n|_2}{2}\right)\right)</math> opérations de groupe ; où ''n'' représente la taille du groupe{{sfn|Shoup|1997}}.

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 <math>\mathbb F_q</math> 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{{note|texte=[http://crypto.stackexchange.com/questions/30144/do-weak-elliptic-curves-exist Do Weak Elliptic Curves Exist?] sur [[Stack Overflow]]}}.

== 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]] [[Rivest Shamir Adleman|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érence nécessaire}}. La construction de cryptosystèmes à base du logarithme discret se fait en utilisant <math>g^s</math> pour un secret <math>s</math> comme un [[masque jetable]]. Ainsi sans connaître <math>s</math>, il est difficile de revenir en arrière, mais le connaissant on peut retirer le masque jetable en calculant <math>g^{-s}</math>.

== Notes et références ==
{{Traduction/Référence|lang1=en|art1=One-way function|id1=756402852|type=note}}

=== Notes ===
{{Notes}}

=== Références ===

{{references|taille=36}}

== Annexes ==
=== Bibliographie ===
* {{Article|auteur=[[Adi Shamir]]|titre=A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems|année=1982|éditeur=Springer|périodique=FOCS'82|langue=en|doi=10.1109/SFCS.1982.5|libellé=Shamir 1982}}
* {{Article|auteur=[[Leonard Adleman]]|titre=On breaking the titrated Merkle-Hellman public-key cryptosystem|année=1982|éditeur=Springer|périodique=[[IACR|Crypto]]'82|langue=en|doi=10.1007/978-1-4757-0602-4_29|libellé=Adleman 1982}}
* {{Article|auteur=[[Victor Shoup]]|titre=Lower bounds for discrete logarithms and related problems|lire en ligne=http://www.shoup.net/papers/dlbounds1.pdf|format=pdf|année=1997|périodique=[[IACR|Eurocrypt]]|libellé=Shoup 1997}}
* {{Ouvrage |langue=en |auteur1=Jonathan Katz |auteur2=Yehuda Lindell |titre=Introduction to Modern Cryptography, 2nd Edition |éditeur=[[Chapman and Hall]] |lieu=Boca Raton |année=2014 |pages totales=583 |isbn=978-1-4665-7026-9 |lire en ligne=https://books.google.com/books?id=OWZYBQAAQBAJ&printsec=frontcover |titre chapitre=Chapitre 6.1 One Way Functions |libellé=Katz et Lindell 2014}}
* {{Computational Complexity (Arora et Barak)|numéro chapitre=9.2.1|titre chapitre=One way functions: Definition and some examples|libellé=Arora et Barak 2009}}
* {{article | auteur = [[Jean-Paul Delahaye]]| périodique = [[Pour la Science]]| numéro=545| date = mars 2023| titre = Des progrès bienvenus en cryptologie}}.

=== Articles connexes ===
* [[Fonction à trappe]]
* [[Fonction pseudo-aléatoire]]
* [[Fonction de hachage cryptographique]]


{{Portail|cryptologie|mathématiques|informatique théorique}}

[[Catégorie:Algorithme de cryptographie asymétrique]]
[[Catégorie:Théorie de la complexité des algorithmes]]
[[Catégorie:Algorithme de hachage]]