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[1].
DĂ©finition
Une fonction calculable en temps polynomial est dite à sens unique[1] si pour tout algorithme polynomial probabiliste , il existe une fonction négligeable telle que pour tout on ait
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
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 nombres et un sous-ensemble de , il est trÚs facile de calculer la somme des éléments de . En revanche, et étant fixés, il est trÚs difficile de trouver sous ensemble de tel que la somme des éléments de soit égale à . 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 et , calculer le produit est facile mĂȘme si et sont trĂšs grands[note 1]. Par contre, remonter Ă et connaissant est plus difficile. Le crible algĂ©brique est le meilleur algorithme connu aujourd'hui pour retrouver et Ă partir de ; il a un temps de calcul qui croĂźt comme
oĂč b est le nombre de bits de . 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 pour gĂ©nĂ©rateur d'un groupe cyclique dâordre suffisamment Ă©levĂ©, alors que le calcul de Ă©tant donnĂ© 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 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 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. La construction de cryptosystĂšmes Ă base du logarithme discret se fait en utilisant pour un secret comme un masque jetable. Ainsi sans connaĂźtre , il est difficile de revenir en arriĂšre, mais le connaissant on peut retirer le masque jetable en calculant .
Notes et références
Notes
- Par exemple la multiplication naĂŻve le calcule en
Annexes
Bibliographie
- [Shamir 1982] (en) Adi Shamir, « A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems », FOCS'82, Springer,â (DOI 10.1109/SFCS.1982.5)
- [Adleman 1982] (en) Leonard Adleman, « On breaking the titrated Merkle-Hellman public-key cryptosystem », Crypto'82, Springer,â (DOI 10.1007/978-1-4757-0602-4_29)
- [Shoup 1997] Victor Shoup, « Lower bounds for discrete logarithms and related problems », Eurocrypt,â (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, , 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, (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, no 545,â .