Fonction à sens unique

Un article de Wikipédia, l'encyclopédie libre.

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

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Une fonction à sens unique est une fonction qui peut être aisément calculée, mais difficile à inverser — c'est-à-dire qu'il est difficile de calculer la donnée d'entrée à partir de la seule donnée de sortie. Les fonctions à sens unique sont utilisées en cryptographie asymétrique et dans les fonctions de hachage cryptographiques.

[modifier] Exemple

Soient deux nombres premiers $p~$ et $q~$ . Calculer $x = pq~$ est facile même si $p~$ et $q~$ sont très grands. Par contre, retrouver $p~$ et $q~$ à partir de $x~$ est irréalisable en pratique si $p~$ et $q~$ sont suffisamment grands. C'est le problème de la factorisation.

[modifier] 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 leur permet de revenir facilement en arrière. Ce principe est utilisé entre autres pour le cryptosystème RSA, la clé privée étant la brèche.

De telles fonctions sont difficiles à trouver et tous les problèmes ne s'y prêtent pas. 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 n'ont pas de trappes connues.