Signature numérique et chiffrement

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.

La signature numérique : une validation sous forme numérique. © Luckystep, Adobe stock 

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

Signature à clé publique : la production de la signature nécessite une clé privée et change à chaque document. Sa vérification ne requiert qu'une clé publique accessible à tous. © P. Guillot

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 x₁,...x_net y₁,...y_n. La clé publique correspondante est constituée par les images a_i = f(x_i) et b_i = f(y_i) par une fonction à sens unique f. Pour signer un message m = m₁,...m_n où chaque m_i est une information binairebinaire valant 0 ou 1, j'appose au message la révélation des données x_i si m_i vaut 0 et y_i si m_i vaut 1. Le destinataire pourra aisément vérifier, grâce à la clé publique, que f(x_i) = a_i si m_i vaut 0 et f(y_j) = b_j si m_i 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 x_i et y_i.

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.