au sommaire
Les activités humaines reposent pour beaucoup sur la confiance dans les engagements des différents acteurs entre eux. Cette confiance se matérialise par une signature apposée sur un document. Il a fallu trouver un équivalent numériquenumérique de la signature, produite par une personne particulière et vérifiable par tous : une signature numériquesignature numérique.
Un mécanisme à clé publiqueclé publique comme le RSA autorise la production d'une telle signature numérique. Il suffit, pour s'engager, d'élever le document que l'on souhaite signer à la puissance exposant privé modulo n. Le résultat constituera la signature du document. Quiconque pourra vérifier la signature en l'élevant à la puissance exposant public modulo n, mais personne ne pourra produire la signature sans la connaissance de l'exposant privé.
Une signature numérique
Cet exemple de la signature RSARSA qui consiste en un chiffrementchiffrement avec clé privéeclé privée a conduit les chercheurs à se demander si cette propriété était consubstantielle à la notion de signature. La signature est-elle duale du chiffrement clé publique ? La réponse est négative. Il n'est pas nécessaire de disposer d'une fonction à sens unique avec trappe pour réaliser ce mécanisme. Une simple fonction à sens unique sans trappe suffit. Une fonction est dite « à sens unique » si elle est facilement calculable, mais étant donné une valeur, il est pratiquement impossible de trouver un paramètre qui donnera ce résultat.
Par exemple, pour un nombre premier p, il est facile d'élever n'importe quel nombre à la puissance n modulo p avec une succession de multiplications et d'élévations au carré. Pourtant, retrouver l'exposant n à partir du résultat est un problème qu'on ne sait pas résoudre de manière efficace aujourd'hui. C'est le problème du logarithme discret.
Pour signer un document avec une fonction à sens unique, il suffit de disposer d'une clé secrèteclé secrète constituée de deux couples de valeurs x1,...xnet y1,...yn. La clé publique correspondante est constituée par les images ai = f(xi)) et bi = f(yi) par une fonction à sens unique f. Pour signer un message m = m1,...mn où chaque mi est une information binairebinaire valant 0 ou 1, j'appose au message la révélation des données xi si mi vaut 0 et yi si mi vaut 1. Le destinataire pourra aisément vérifier, grâce à la clé publique, que f(xi) = ai si mi vaut 0 et f(yj) = bj si mi vaut 1. Comme la fonction est à sens unique, il sera difficile à un adversaire de révéler des valeurs convenables en l'absence de la connaissance des paramètres xi et yi.
Cette signature n'a qu'un intérêt théorique en raison de sa totale inefficacité. La signature d'un document est bien plus « lourde » que le document lui-même et la clé privée n'est pas réutilisable pour un autre document. Cependant, l'intérêt théorique est fondamental : la signature numérique peut se construire à partir d'une fonction à sens unique. Il n'y a pas besoin de trappe pour signer un document.