vignette|Représentation de séquence pour signer un document avec une signature Lamport. La clé privée utilise des mots courants pour faciliter la visualisation du processus. En utilisation réelle, des valeurs cryptographiquement sécurisées doivent être utilisées. En cryptologie, le schéma de signature de LamportParfois appelé « schéma de signature de Lamport-Diffie », puisqu'on peut retracer l'idée à (Diffie et Hellman 1976, p. 650), mais la construction en entier et l'analyse de sécurité apparaissent pour la première fois dans (Lamport 1979). est un mécanisme à usage uniqueOn parle dans ce contexte de « signature à usage unique », ou de « signature jetable » (OTS, pour l'anglais one time signature), en analogie au masque jetable pour le chiffrement. permettant de signer numériquement un document. Il a été introduit en 1979 par l'informaticien américain Leslie Lamport Leslie Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.. La construction des signatures de Lamport repose uniquement sur les fonctions à sens unique, une approche qui a inspiré plusieurs constructions cryptographiques et qui s'avère être un candidat post-quantique.
Les signatures de Lamport souffrent de nombreux désavantages techniques, en particulier leur usage unique, la taille des clés et des signatures, qui ont motivé la création d'algorithmes plus efficaces (par Merkle et d'autres).
Description Le schéma de signature de Lamport est composé de trois algorithmes : génération de clés, signature et vérification.
Génération de clés L'algorithme de génération de clés prend en entrées un paramètre de sécurité et une taille de messages , puis détermine deux entiers , et une fonction à sens unique . L'algorithme de génération de clés tire ensuite éléments uniformément au hasard pour et .
L'algorithme retourne la clé privée , la clé publique et les paramètres publics .
Signature L'algorithme de signature prend en entrées les paramètres publics, la clé privée, et un message à signer. La signature correspondante est .
Vérification L'algorithme de vérification prend en entrées les paramètres publics, la clé publique, un message et une signature . S'il existe un indice tel que alors l'algorithme retourne une erreur. Sinon, il renvoie un succès.
Sécurité La sécurité du schéma de signature de Lamport face aux contrefaçons existentielles se ramène immédiatement (et dans le modèle standard) à la difficulté de calculer une préimage pour Pour les implémentations, une fonction de hachage cryptographique pourra jouer ce rôle.. Cependant, le schéma ne peut être utilisé que pour signer un seul message. En effet, la signature révèle par construction une partie (50%) de la clé privée.
Un calculateur quantique facilite la recherche d'une préimage (au moyen de l'algorithme de Grover), divisant par deux le niveau de sécurité par rapport à un adversaire classique. Ce phénomène est aisément compensé en doublant les paramètres de la fonction ; pour cette raison, le schéma de Lamport est considéré comme un candidat post-quantique.
Notes et références
Notes
Références
Catégorie:Cryptologie Catégorie:Signature électronique