Signature de cercle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La signature de cercle (en anglais : Ring signature), aussi appelé signature d’anneau, est un procédé cryptographique permettant à une personne de signer électroniquement de façon anonyme un message ou un document au nom d’un « cercle ». Les membres de ce cercle sont choisis par l’auteur de la signature et ne sont pas nécessairement informés de leur implication dans la création de la signature électronique. La seule contrainte est qu’ils doivent tous avoir une clef cryptographique publique.

La signature de cercle a donné lieu a un dérivé : la signature de cercle à seuil, où la signature est initiée par un nombre pré-défini de membres du cercle.

Principe[modifier | modifier le code]

Comme l'indique le titre de l'article où elle est décrite pour la première fois, How to Leak a Secret[1], le but premier de cette signature est de permettre la fuite d'information.

Dans cet article est donné l'exemple d'un membre d'un cabinet ministériel voulant donner à un journaliste des informations sur le premier ministre. Il ne désire évidemment pas divulguer son identité, mais souhaite que le journaliste sache que la fuite vient du cabinet et non pas d'un plaisantin. La signature de cercle lui permet ainsi de signer en tant que membre du cabinet ministériel, et non en tant qu'individu, sans que ses collègues soient au courant, ni que quiconque puisse remonter à lui, contrairement à la signature de groupe qui impose une coopération des membres inclus dans la signature et la possibilité de pour une personne déterminé à l'initialisation de connaître l'identité du signataire.

Une autre utilisation proposée dans cet article est celle permettant de générer une signature qui n'aura de valeur que pour le destinataire. Ainsi la source envoie un document signé à l'aide d'une signature de cercle comprenant sa clef et celle du destinataire. Ce dernier, sachant qu'il ne l'a pas produit, a donc la preuve que le message provient bien de la source. Mais s'il montre le document à un tiers, ce dernier ne peut pas être sûr que le message n'est pas un faux, créé par le destinataire.

Définition[modifier | modifier le code]

Dans le schéma de base, l'utilisateur génère une signature σ basée sur le message m à signer, la valeur v originale utilisée, son couple clef privée / publique et les clefs publiques des autres membres du cercle. Le ou les destinataires peuvent vérifier cette signature à l'aide de σ, m, v et de l'ensemble des clefs publiques impliquées dans le processus de création.

Signature[modifier | modifier le code]

Le signataire génère un hash σ du message m (par exemple). Il choisit ensuite un v (aléatoirement ou non). Pour chaque clef publique p autre que la sienne, le signataire choisit un x aléatoirement, le chiffre avec la clef publique p et "xore" le résultat avec la valeur v avant de subir une permutation symétrique Eσ, ce qui donnera un nouveau "v".

Ce qui donne : v = Eσ (f (x) ⊗ v) avec f la fonction de cryptage à l'aide de la clef publique.

On recommence la manipulation avec les autres clefs publiques.

À la fin, on se retrouve avec une valeur différente du v de départ. On recherche alors la valeur y qui, "xoré" avec le v trouvé et permuté avec Eσ, permet de retrouver le v original. On utilise sa clef privée pour trouver le x qui, passé par sa clef publique donnera le y.

Vérification[modifier | modifier le code]

Le destinataire refait le calcul v = Eσ (f (x) ⊗ v) pour toutes les clefs publiques de la signature et vérifie qu'il retrouve bien le v original à la fin.

La taille de la signature est linéaire en N, qui correspond à la taille du cercle, car il faut spécifier les clefs publiques utilisées.

Codage[modifier | modifier le code]

Voici un codage en Python ou Python3 du papier original avec RSA. Le cercle contient quatre membres.

import os, hashlib, random, functools, Crypto.PublicKey.RSA
 
class ring:
    def __init__(self, k, l=2048):
        self.k, self.l, self.n, self.q = k, l, len(k), 1 << l - 1
 
    def sign(self, m, z):
        self.permut(m)
        s, u = [None]*self.n, random.randint(0, self.q)
        c = v = self.E(u) 
        for i in list(range(z+1, self.n)) + list(range(z)):
            s[i] = random.randint(0, self.q)
            v = self.E(v^self.g(s[i], self.k[i].e, self.k[i].n)) 
            if (i+1) % self.n == 0: c = v
        s[z] = self.g(v^u, self.k[z].d, self.k[z].n)
        return [c, ] + s
 
    def verify(self, m, X):
        self.permut(m)
        y = [self.g(X[i+1], self.k[i].e, self.k[i].n) for i in range(len(X)-1)]
        return functools.reduce(lambda x, i:self.E(x^y[i]), range(self.n), X[0]) == X[0]
 
    def permut(self, m):
        self.p = int(hashlib.sha1(m.encode('utf8')).hexdigest(), 16)
 
    def E(self, x): 
        return int(hashlib.sha1(('%s%s'% (x, self.p)).encode('utf8')).hexdigest(), 16)

    def g(self, x, e, n):
        q, r = divmod(x, n)
        return q*n + pow(r, e, n) if (q+1)*n <= (1<<self.l)-1 else x

if __name__ == '__main__':
    size, msg1, msg2 = 4, 'hello', 'world!'
    r = ring([Crypto.PublicKey.RSA.generate(2048, os.urandom) for x in range(size)])
    for i in range(size):
        s1, s2 = r.sign(msg1, i), r.sign(msg2, i)
        assert r.verify(msg1, s1) and r.verify(msg2, s2) and not r.verify(msg1, s2)

Variante[modifier | modifier le code]

De nombreuses variantes ont été créées, dont celle de Dodis, Kiayias, Nicolosi et Shoup[2], qui propose un schéma à taille constante en utilisant les fonctions d'accumulation et le schéma d'authentification de Fiat-Shamir. Une autre version possédant une taille en O(rac(N)) a été proposée par Chandran, Groth et Sahai[3].

Cryptomonnaies[modifier | modifier le code]

La technologie Cryptonote[4] utilise des signatures de cercles. Celle-ci est le fondement de crypto-monnaies telles que Monero, Bytecoin ou DarkNote. Le principe de Signature de Cercle a également été portée sur ShadowCash[5], une crypto-monnaie issue de Bitcoin.

Notes et références[modifier | modifier le code]

  1. Ronald L. Rivest, Adir Shamir et Yael Tauman, How to Leak a Secret, 4 juin 2001.
  2. Dodis, Kiayias, Nicolosi et Shoup, Anonymous identification in ad-hoc groups.
  3. Chandran, Groth et Sahai, Ring signatures of sub-linear size without random oracle
  4. Cryptonote [PDF]
  5. ShadowCash [PDF]

Liens externes[modifier | modifier le code]