Wiki du cours

Rédacteur: Mélanie Marques

A traiter [Bearbeiten]

• Signature de Schnorr (création de clé, algorithme de signature, algorithme de vérification).
• Agrégation de signatures.
• Agrégation de clés.
• Attaque de la clé malhonnête (rogue key).

Signature de Schnorr [Bearbeiten]

Le protocole de signature de Schnorr est le protocole non-interactif du protocole d'authentification de Schnorr. La sécurité de ce protocole est basée sur la difficulté du problème du logarithme discret.

Création de clé

Supposons qu'Alice veut signer un entier \(m \) (qui représente le message ou le résultat d'une fonction de hachage sur le message) qu'elle envoie à Bob.

Alice choisit les paramètres suivants:

- Soit \(G\) un groupe cyclique d'ordre p et \(g\) un générateur de \(G\)
- Soit H une fonction de hachage

On a donc comme clés:
- Clé privée : \(x \in \{1,..,p-1\} \)
- Clé publique : \(X = gx\)

Algorithme de signature

L'algorithme de signature d'un message \(m\) utilisant la clé privée \(x\) est le suivant:

input : \(m\) et \(x\)
1 Alice choisit un nombre aléatoire \(r \in \{1,..,p-1\}\) et elle calcule \(R= gr\)
2 Elle calcule ensuite \(c = H(X, R, m)\) et \(s = r + cx\) \( mod(p) \)
output : \(\sigma = (R,s)\)

Algorithme de vérification

input : \(X, m\) et \( \sigma \)
1 Bob calcule \(c= H(X, R, m) \)
2 Il vérifie que \(gs = R + cX\)

Agrégation de signature [Bearbeiten]

Schéma d'agrégation générale de signatures

Étant donné \(n\) signatures sur \(n\) messages distincts provenant de \(n\) signataires distincts, il est possible d'agréger toutes ces signatures en une seule signature.
En effet, chaque signataire \(i\) signe son message \(m_{i}\) pour obtenir une signature \(\sigma_{i}\). Chacun peut alors utiliser un algorithme d'agrégation public pour prendre toutes les \(n\) signatures \(\sigma_{1}\),..., \(\sigma_{n}\) et les compresser en une seule signature commune \(\sigma\).
Cette agrégation se fait par incrémentation, c'est-à-dire : les signatures \(\sigma_{1}\) et \(\sigma_{2}\) peuvent être agrégées en\(\sigma_{12}\), qui peut ensuite être agrégé avec \(\sigma_{3}\) pour obtenir \(\sigma_{123}\), etc. Il existe également un algorithme de vérification d'agrégat qui prend \(PK_{1}, ..., PK_{n}\), \(m_{1}, ..., m_{n}\) et \(\sigma\) et décide si la signature d'agrégat est valide ou pas.

Agrégation de signature dans le cas de Schnorr

L'agrégation de signatures n'est réalisable avec Schnorr que lorsque tous les signataires signent le même message: étant donné \(n\) signatures \(\sigma_{1},... \sigma_{n}\) sur un même message \(m\), il est possible de combiner ces \(n\) signatures en une unique signature \(\sigma\).

En effet,
Soit un groupe de \(n\) signataires qui veulent tous signer un même message \(m\) et \(L = \{ X_{1} = gx_{1}, ... X_{n}=gx_{1} \} \) l'ensemble de leurs clés publiques (respectives).
Chaque signataire calcule son \(R_{i} = gr_{i}\) et l'envoie de façon aléatoirement aux autres signataires.
Ensuite, chacun calcule:
° \(R = \prod_{i=1..n} R_{i}\)
° \(c = H(\tilde{X}, R, m)\) où \(\tilde{X} = \prod_{i = 1...n} X_{i}\) est le produit de clés publiques individuelles
° Une signature partielle \(s_{i} = r_{i} + cx_{i}\)
Les signatures partielles sont ensuite combinées en une seule signature \(\sigma = (R, s)\) où \(s = \prod_{i= 1...n} s_{i} \) \(mod p \).
La validité d’une signature \(\sigma =(R, s)\) sur le message \(m\) pour les clés publiques \(\{X_{1},. . . , X_{n}\}\) est \(gs = R+c\tilde{X}\).

Agrégation de clés [Bearbeiten]

L'agrégation de clés consiste à combiner toutes les clés publiques en une seule clé publique, indistinguable d’une clé publique classique, ce qui permet d'avoir une vérification qui est effectuée comme pour une signature normale. C'est ce qui se produit avec Schnorr quand tout le monde signe le même message. En effet, lorsque nous avons considéré la clé publique \(\tilde{X} = \prod_{i = 1...n} X_{i}\) comme étant le produit de clés publiques individuelles nous avons fait là une agrégation de clés.

Attaque de la clé malhonnête (rogue key) [Bearbeiten]

Un tel schéma d'agrégation de clé possède un problème de sécurité: l'attaque de la clé malhonnête.
En effet, considérons le scénario suivant:
Alice et Bob veulent produire une signature commune. Alice a une paire de clés \((x _{A} , X_{A})\) et Bob a \((x_{B} , X_{B})\). Cependant, rien n'empêche Bob d'avoir comme clé publique: \(X _{B'} = X_{B} - X_{A}\). S'il décide d'avoir une telle clé, d'autres supposeront que \(X_{A} + X_{B'}\) est la clé agrégée que Alice et Bob doivent avoir pour pouvoir signer. Malheureusement, cette somme est égale à \(X _{B}\) et Bob peut alors clairement le signer par lui-même.

De façon générale, nous avons:
Soient un sous-ensemble de \(t\) signataires corrompus ( avec \( 1 \leq t \leq n\) ) qui utilisent des clés publiques \(PK'_{n-t+1},...,PK'_{n}\) calculées en fonction de clés publiques \(PK_{1},...,PK_{n-t}\) d'utilisateurs honnêtes. Ceci leur permet de facilement produire des contrefaçons pour l'ensemble du public clés \(\{PK_{1},...,PK_{n-t}, PK'_{n-t+1},...,PK'_{n}\}\). En effet, un signataire \(j\) corrompu définit sa clé publique comme \(X_{j} = gx_{j}+ (\prod_{i=1..n}X_{i})^{-1}\) ce qui lui permet de produire des signatures pour les clés publiques \((X_{1},...,X_{n}) \) par lui-même.
Un moyen de prévenir de telles attaques consiste à exiger que les utilisateurs prouvent la connaissance (ou la possession) de la clé privée lors de l'enregistrement de la clé publique.