Fonction à sens unique

(One-way function)




C'est une fonction facile à calculer et difficile à inverser en pratique (tout au moins pour des tailles bien choisies des objets mathématiques mis en jeu). En voici un exemple : fixons un nombre premier p ainsi qu'un élément primitif a du groupe multiplicatif des entiers modulo p sans le nombre 0. Supposons que p s'écrive avec 2048 bits. A tout entier k compris entre 0 et p-2 faisons correspondre y=a^k mod p. La fonction y=f(k) ainsi définie est une fonction à sens unique. Le calcul de l'image de la fonction est ici le calcul d'une puissance modulo p, et nous disposons d'un algorithme efficace pour mener à bien le calcul (algorithme square and multiply). En revanche le calcul de l'inverse (problème du logarithme discret) ne peut pas être fait à l'heure actuelle en temps raisonnable. Nous n'avons en fait aucune preuve qu'une telle fonction est réellement difficile à inverser, car personne n'a prouvé qu'on ne pourra pas trouver un jour un algorithme efficace qui puisse faire le calcul de l'inverse en un temps raisonnable.



[ Retour ]