« Fonction à sens unique » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

VisuelWikicode

Intégrés

Version du 3 février 2017 à 15:09

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (janvier 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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^[1]

Exemples

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 très difficile 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é vulnérable^[2]^[3].

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 $x=pq$ est facile même si $p$ et $q$ sont très grands^[4]. Par contre, 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

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

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

[Shamir 1982] (en) Adi Shamir, « A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems », Crypto'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)
[Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Chapman and Hall, 2014 (ISBN 978-1466570269), « 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 »)

Notes et références

↑ Arora et Barak 2009.
↑ Shamir 1982.
↑ Adleman 1982.
↑ Par exemple la multiplication naïve le calcule en ${\mathcal {O}}(|p|\cdot |q|).$

[AroraBarak2009-1] Arora et Barak 2009.

[Shamir1982-2] Shamir 1982.

[Adleman1982-3] Adleman 1982.

[4] Par exemple la multiplication naïve le calcule en ${\mathcal {O}}(|p|\cdot |q|).$

[1]

[2]

[3]

[4]

@@ Ligne 5 : / Ligne 5 : @@
 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, il est difficile de lui trouver un 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''.
+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''{{sfn|Arora|Barak|2009}}
 == Exemples ==
 === 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 intrinsèquement très difficile  au 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.
+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 très difficile 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é 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 <math>x = pq</math> est facile même si <math>p</math> et <math>q</math> sont très grands. Par contre, 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
+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 <math>x = pq</math> est facile même si <math>p</math> et <math>q</math> sont très grands{{note|texte=Par exemple la multiplication naïve le calcule en <math>\mathcal O(|p|\cdot|q|).</math>}}. Par contre, 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>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 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 [[Rivest Shamir Adleman|RSA]].
@@ Ligne 23 : / Ligne 25 : @@
 == Bibliographie ==
+* {{Article|auteur=[[Adi Shamir]]|titre=A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems|année=1982|éditeur=Springer|périodique=Crypto'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=Crypto'82|langue=en|doi=10.1007/978-1-4757-0602-4_29|libellé=Adleman 1982}}
+* {{ouvrage|langue=en
+ |    auteur1 = Jonathan Katz
+ |    auteur2 = Yehuda Lindell
+ |      année = 2014
+ |     titre = Introduction to Modern Cryptography, 2nd Edition
+ | éditeur = [[Chapman and Hall]]
+ |      isbn = 978-1466570269
+ | libellé   = Katz et Lindell 2014
+ | chapter  = Chapitre 6.1 One Way Functions
+ }}
+* {{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}}
 ==Notes et références==