Sciences

Signature numérique et chiffrement

Dossier - Cryptologie : l'art des codes secrets
DossierClassé sous :Mathématiques , cryptologie , Philippe guillot

Rendre incassables les codes secrets est un vieux rêve des professionnels de sécurité. Depuis l’Antiquité, les Hommes inventèrent des systèmes manuels puis mécaniques avant la révolution électronique. Découvrez la cryptologie et ses utilisations, du chiffrement traditionnel à l’usage de l’informatique en passant par le chiffrement RSA.

  
DossiersCryptologie : l'art des codes secrets
 

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érique de la signature, produite par une personne particulière et vérifiable par tous : une signature numérique.

Un mécanisme à clé 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

Cet exemple de la signature RSA qui consiste en un chiffrement avec clé 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ète constituée de deux couples de valeurs x1,...xnet y1,...yn. La clé publique correspondante est constituée par les images aif(xi) et bi = f(yi) par une fonction à sens unique f. Pour signer un message m = m1,...mn où chaque mi est une information binaire 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.