Utilisateur:Qwyvin/Schéma de signature de Merkle

Dans la cryptographie basée sur le hachage, le schéma de signature de Merkle est un schéma de signature numérique basé sur des arbres de Merkle (également appelés arbres de hachage) et des signatures uniques telles que le schéma de signature de Lamport. Il a été développé par Ralph Merkle à la fin des années 1970^[1] et est une alternative aux signatures numériques traditionnelles telles que le Digital Signature Algorithm ou RSA.

Un avantage du schéma de signature de Merkle est qu'il est censé être résistant aux attaques des ordinateurs quantiques . Les algorithmes à clé publique traditionnels, tels que RSA et ElGamal, deviendraient peu sûrs si un ordinateur quantique efficace pouvait être construit (à cause de l'algorithme de Shor). Le schéma de signature de Merkle, cependant, ne dépend que de l'existence de fonctions de hachage sécurisées. Cela rend le schéma de signature de Merkle très ajustable et résistant aux attaques informatiques quantiques. La signature de Merkle est une signature à usage unique avec un potentiel de signature fini. Le travail de Moni Naor et Moti Yung sur les permutations et les fonctions à sens unique basées sur la signature (et l'invention des fonctions de hachage universelle à sens unique) permet d'étendre une signature de type Merkle à un schéma de signature complet.^[2]

Génération de clé[modifier | modifier le code]

Le schéma de signature Merkle peut être utilisé pour signer un nombre limité de messages avec une clé publique ${\text{pub}}$ . Le nombre de messages possibles doit être une puissance de deux, on notera donc le nombre possible de messages comme $N=2^{n}$ .

La première étape de génération de la clé publique ${\text{pub}}$ est de générer $N$ paires de clés privées/publiques $(X_{i},Y_{i})$ d'un schéma de signature unique (comme le schéma de signature de Lamport par exemple). Pour chaque $1\leq i\leq 2^{n}$ , une valeur de hachage de la clé publique $h_{i}=H(Y_{i})$ est calculé.

On construit un arbre de hachage avec ces valeurs $h_{i}$ , en plaçant ces $2^{n}$ valeurs de hachage sous forme de feuilles et en hachant récursivement pour former un arbre binaire. Soit $a_{i,j}$ le nœud dans l'arbre avec la hauteur $i$ et position gauche-droite $j$ . Les valeurs de hachage $h_{i}=a_{0,i}$ sont alors les feuilles de l'arbre. La valeur de chaque nœud interne de l'arbre est le hachage de la concaténation des valeurs de ses deux enfants. Par exemple, $a_{1,0}=H(a_{0,0}||a_{0,1})$ et $a_{2,0}=H(a_{1,0}||a_{1,1})$ . On construit donc un arbre avec $2^{n}$ feuilles et $2^{n+1}-1$ nœuds.

La clé privée du schéma de signature de Merkle est l'ensemble complet de $(X_{i},Y_{i})$ paires. Un inconvénient du schéma est que la taille de la clé privée évolue linéairement avec le nombre de messages à envoyer.

La clé publique ${\text{pub}}$ est la racine de l'arbre, $a_{n,0}$ . Les clés publiques individuelles $Y_{i}$ peuvent être rendues publiques sans enfreindre la sécurité. Cependant, ils ne sont pas nécessaires dans la clé publique, et peuvent donc être gardés secrets pour minimiser la taille de la clé publique.

Génération de signatures[modifier | modifier le code]

Pour signer un message $M$ avec le schéma de signature de Merkle, le signataire choisit une paire de clés $(X_{i},Y_{i})$ , signe le message à l'aide du schéma de signature unique, puis ajoute des informations supplémentaires pour prouver que la paire de clés utilisée était l'une des paires de clés d'origine (plutôt qu'une nouvelle générée par un faussaire).

Arbre Merkle avec chemin A et chemin d'authentification pour i = 2, n = 3

Tout d'abord, le signataire choisit une paire $(X_{i},Y_{i})$ qui n'avait pas été utilisée auparavant pour signer un autre message, et utilise le schéma de signature unique pour signer le message, résultant en une signature ${\text{sig}}'$ et la clé publique correspondante $Y_{i}$ . Pour prouver au vérificateur de message que $(X_{i},Y_{i})$ était en fait l'une des paires de clés d'origine, le signataire inclut simplement les nœuds intermédiaires de l'arbre de Merkle afin que le vérificateur puisse vérifier que $h_{i}=a_{0,i}$ a été utilisé pour calculer la clé publique $a_{n,0}$ à la racine de l'arbre. Le chemin dans l'arbre de hachage depuis $a_{0,i}$ à la racine est $n+1$ nœuds longs. Appelez les nœuds $A_{0},\ldots ,A_{n}$ , avec $A_{0}=a_{0,i}=H(Y_{i})$ étant une feuille et $A_{n}=a_{n,0}={\text{pub}}$ étant la racine.

$A_{i}$ est un enfant de $A_{i+1}$ . Pour laisser le vérificateur calculer le nœud suivant $A_{i+1}$ étant donné le précédent, ils ont besoin de connaître l'autre enfant de $A_{i+1}$ , le nœud frère de $A_{i}$ . Nous appelons ce nœud ${\text{auth}}_{i}$ , pour que $A_{i+1}=H(A_{i}||{\text{auth}}_{i})$ . Ainsi, $n$ nœuds ${\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}$ sont nécessaires, pour reconstruire $A_{n}=a_{n,0}={\text{pub}}$ de $A_{0}=a_{0,i}$ . Un exemple de chemin d'authentification est illustré dans la figure de droite.

Ensemble, les nœuds ${\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}$ , la $Y_{i}$ , et la signature unique ${\text{sig}}'$ constituent une signature de $M$ en utilisant le schéma de signature Merkle : ${\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})$ .

On peut noter que lorsqu'on utilise le schéma de signature de Lamport comme schéma de signature unique, ${\text{sig}}'$ contient une partie de la clé privée $X_{i}$ .

Vérification de la signature[modifier | modifier le code]

Le destinataire connaît la clé publique ${\text{pub}}$ , le message $M$ , et la signature ${\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})$ . Tout d'abord, le destinataire vérifie la signature unique ${\text{sig}}'$ du message $M$ à l'aide de la clé publique de la signature à usage unique $Y_{i}$ . Si ${\text{sig}}'$ est une signature valide de $M$ , le récepteur calcule $A_{0}=H(Y_{i})$ en hachant la clé publique de la signature à usage unique. Pour $j=1,\ldots ,n-1$ , les nœuds de $A_{j}$ du chemin sont calculés avec $A_{j}=H(A_{j-1}||{\text{auth}}_{j-1})$ . Si $A_{n}$ est égal à la clé publique ${\text{pub}}$ du schéma de signature de Merkle, la signature est valide.

↑ Merkle, « Secrecy, authentication and public key systems », Ph.D. Dissertation,‎ 1979, p. 32–61 (lire en ligne)
↑ Naor et Yung, « Universal One-Way Hash Functions and their Cryptographic Applications », Symposium on Theory of Computing,‎ 1989, p. 33–43 (lire en ligne)

E. Dahmen, M. Dring, E. Klintsevitch, J. Buchmann, LC Coronado Garca. "CMSS - un schéma de signature merkle amélioré". Progrès en cryptologie - Indocrypt 2006, 2006.
E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen. "Signatures Merkle avec une capacité de signature pratiquement illimitée". 5e Conférence internationale sur la cryptographie appliquée et la sécurité des réseaux - ACNS07, 2007.
S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Représentation et traversée de l'arbre de merkle fractal". RSA-CT 03, 2003

Utilisation efficace des arbres Merkle - Explication des laboratoires RSA sur l'objectif initial des arbres de Merkle et des signatures de Lamport, en tant que schéma de signature unique efficace.
Une introduction aux signatures basées sur le hachage et aux signatures de Merkle par Adam Langley.
Une série en 4 parties sur les signatures basées sur le hash par David Wong.

[[Catégorie:Cryptographie post-quantique]] [[Catégorie:Cryptographie]] [[Catégorie:Pages avec des traductions non relues]]

[1] Merkle, « Secrecy, authentication and public key systems », Ph.D. Dissertation,‎ 1979, p. 32–61 (lire en ligne)

[2] Naor et Yung, « Universal One-Way Hash Functions and their Cryptographic Applications », Symposium on Theory of Computing,‎ 1989, p. 33–43 (lire en ligne)

[1]

[2]