Protocole d'authentification de Schnorr

En cryptographie, le protocole d'authentification de Schnorr (en) (souvent abrégé protocole de Schnorr) est une preuve à divulgation nulle de connaissance décrite en 1989 par Schnorr^[1] dont la sécurité repose sur la difficulté du problème du logarithme discret et servant à prouver la connaissance d’un logarithme discret, c’est-à-dire étant donné ${\displaystyle g^{a}}$, prouver que l'on connaît l'exposant ${\displaystyle a}$ dans un groupe ${\displaystyle G}$ engendré par ${\displaystyle g}$.

Ce protocole peut être dérivé en une signature numérique en rendant la preuve non interactive par l'heuristique de Fiat-Shamir^[2],[3]. Ce schéma de signature numérique a été breveté aux États-Unis sous le Brevet US 4995082 qui expirait en février 2008.

Comme d'autres preuves à connaissances nulles, le protocole de Schnorr est un protocole Σ^[4]: un protocole entre deux algorithmes interactifs P et V (pour Prouveur et Vérifieur) en trois phases: l'engagement, le défi et la réponse.

• Un nombre ${\displaystyle q}$ premier. On note qu'il définit un groupe ${\displaystyle G}$ d'ordre ${\displaystyle q}$ engendré par ${\displaystyle g}$, noté multiplicativement dans la suite.
• Un élément de groupe ${\displaystyle g}$, d'ordre ${\displaystyle q.}$ C'est ici un générateur d'un sous-groupe d'ordre ${\displaystyle q}$ de ${\displaystyle G}$
• ${\displaystyle q,g}$ sont publics.

• Un entier pris au hasard ${\displaystyle s}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$.
• Le prouveur calcule ${\displaystyle v=g^{s}}$, et ${\displaystyle v}$ est rendu public, certifié par une autorité de confiance, tandis que ${\displaystyle s}$ est gardé secret.

Dans un premier temps, P lance une étape d'engagement:

• P tire au hasard un entier ${\displaystyle r}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$.
• P calcule ${\displaystyle R=g^{r}}$ et envoie ${\displaystyle R}$ à V

Ensuite commence la phase du défi:

• V tire un entier ${\displaystyle c}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$ et l'envoie à P

Finalement, la phase de réponse:

• P calcule ${\displaystyle a=r-c\cdot s}$ et l'envoie à V.

V accepte si et seulement si à l'issue du protocole, la relation ${\displaystyle R=g^{a}\cdot v^{c}}$ est vérifiée.

Pour prouver la sécurité d'un protocole Σ^[4], il suffit de prouver la complétude, la robustesse spéciale, et la propriété de non-divulgation de connaissances sous un vérifieur honnête.

La complétude (ou correction) requiert que pour un déroulement honnête du protocole, le vérifieur est toujours convaincu.

Cela se vérifie par la condition d'acceptation de V qui donne que ${\displaystyle g^{a}\cdot v^{c}=g^{r-c\cdot s}\cdot g^{s\cdot c}=g^{r}=R}$, ce qui est toujours vérifié si le protocole s'est déroulé honnêtement.

La robustesse spéciale dit qu'il existe un extracteur de connaissance qui fonctionne en temps polynomial tel qu'étant donné deux transcriptions acceptantes ${\displaystyle (R,c,a)}$ et ${\displaystyle (R,c',a')}$ sous les mêmes paramètres publics, alors l'extracteur renvoie le secret ${\displaystyle s}$.

Cet extracteur se construit comme suit dans le cas du protocole de Schnorr : il va calculer et retourner ${\displaystyle {\frac {a-a'}{c'-c}}}$, car cette valeur correspond au logarithme discret de ${\displaystyle v}$ par ${\displaystyle g}$. En effet, les transcriptions ${\displaystyle (R,c,a)}$ et ${\displaystyle (R,c',a')}$ étant acceptantes, les relations ${\displaystyle R=g^{a}\cdot v^{c}}$ et ${\displaystyle R=g^{a'}\cdot v^{c'}}$ sont vérifiées, donnant ainsi ${\displaystyle g^{\left({\frac {a-a'}{c'-c}}\right)}=v}$ puisque ${\displaystyle c\not =c'}$.

Cette propriété se caractérise par l'existence d'un simulateur probabiliste qui fonctionne en temps polynomial qui, étant donné ${\displaystyle (v,c)}$ où ${\displaystyle c}$ est distribué comme un défis correct, alors le simulateur renvoie une transcription ${\displaystyle (R,c,a)}$ distribuée comme une vraie transcription pour ${\displaystyle v}$. On remarque que le simulateur n'a pas besoin du secret.

Ici, le simulateur va donc générer la réponse avant l'engagement: il va tirer ${\displaystyle a}$ uniformément dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$ et va générer ${\displaystyle R}$ pour qu'il vérifie la condition d'acceptation, c'est-à-dire ${\displaystyle R=g^{a}\cdot v^{c}}$, et va renvoyer ${\displaystyle (R,c,a)}$. On peut remarquer que ${\displaystyle R}$ est distribué uniformément puisque son logarithme discret selon la base ${\displaystyle g}$ l'est. Et par construction ${\displaystyle a}$ est distribué comme une réponse acceptante vis-à-vis de ${\displaystyle (R,c)}$.

La spécification du brevet indique que le groupe ${\displaystyle G}$ doit être choisi comme un sous-groupe d'au moins 140 bits d'un groupe ${\displaystyle \mathbb {Z} _{p}}$ où ${\displaystyle p}$ est un nombre premier de 512 bits pour 72 bits de sécurité.

L'heuristique de Fiat-Shamir peut être utilisée pour transformer le schéma d'identification en signature numérique.

Pour cela une (famille de) fonction de hachage cryptographique ${\displaystyle {\mathcal {H}}:G\times \{0,1\}^{*}\to \mathbb {Z} _{q}^{\star }}$ est introduite dans les paramètres publics, et au moment du défi, le tirage aléatoire de ${\displaystyle c}$ est remplacé par l'évaluation ${\displaystyle c\gets {\mathcal {H}}(R,m)}$ où ${\displaystyle m\in \{0,1\}^{*}}$ correspond au message à signer. La signature correspond au couple ${\displaystyle (c,a)}$ ; au moment de la vérification, ${\displaystyle R}$ est recalculé comme ${\displaystyle R'=g^{a}\cdot v^{c}}$, le vérifieur teste si ${\displaystyle {\mathcal {H}}(R',m)=c}$ et accepte si cette vérification passe. La description complète est donnée ci-dessous.

Une signature numérique est donnée par un triplet d'algorithmes (GenClefs, Signer, Vérifier).

Génération de clefs:

1. Les paramètres publiques (${\displaystyle q}$ et ${\displaystyle g}$) sont générées de la même manière que pour le protocole Σ.
2. Une fonction de hachage ${\displaystyle {\mathcal {H}}:G\times \{0,1\}^{*}\to \mathbb {Z} _{q}^{\star }}$ est ensuite générée et rajoutée aux paramètres publiques.
3. Pour générer une paire de clefs (vk, sk) (v pour vérification, et s pour signature), le signataire commence par tirer uniformément un nombre ${\displaystyle s\in \mathbb {Z} _{q}^{\star }}$, et va le définir comme sa clef secrète.
4. Le signataire va ensuite calculer ${\displaystyle v=g^{s}}$, et va le publier comme sa clef publique.

Signature(sk, m):

1. Pour signer un message, le signataire va commencer par tirer un nombre ${\displaystyle r\in \mathbb {Z} _{q}^{\star }}$ au hasard, et définir ${\displaystyle R=g^{r}}$.
2. Le « défi » va ensuite être généré comme ${\displaystyle c={\mathcal {H}}(R,m)}$, et la réponse calculée comme ${\displaystyle a=r-c\cdot {\mathsf {sk}}\in \mathbb {Z} _{q}}$.
3. Finalement la signature est renvoyée: ${\displaystyle \sigma =(c,a)}$.

Vérification(vk, m, σ):

1. Pour vérifier la signature ${\displaystyle \sigma =(c,a)}$, un utilisateur commence par recalculer ${\displaystyle R}$ en utilisant la clef publique : ${\displaystyle R'=g^{a}\cdot {\mathsf {vk}}^{c}}$.
2. L'utilisateur va ensuite accepter si et seulement si ${\displaystyle {\mathcal {H}}(R',m)~{\overset {?}{=}}~c}$.

Cela donne une signature de taille ${\displaystyle |c|+|a|=280{\mbox{ bits}}=35{\mbox{ octets}}}$ suivant les recommandations minimales du brevet pour 72 bits de sécurité.

Pointcheval et Stern ont montré en 1996 que l'heuristique de Fiat-Shamir^[3] est sûre dans le modèle de l'oracle aléatoire^[5] si le schéma d'identification sous-jacent est sûr.

• [Feige Fiat et Shamir 1988] (en) Uriel Feige, Amos Fiat et Adi Shamir, « Zero-knowledge proofs of identity », Journal of Cryptology,‎ 1988 (DOI 10.1007/BF02351717)
• [Fiat et Shamir 1986] (en) Amos Fiat et Adi Shamir, « How To Prove Yourself: Practical Solutions to Identification and Signature Problems », Crypto 1986,‎ 1986 (lire en ligne [PDF])
• [Schnorr 1989] (en) Claus-Peter Schnorr, « Efficient Identification and Signature for Smart Cards », Theory and Application of Cryptology, Springer,‎ 1989 (lire en ligne)
• [Pointcheval et Stern 1996] (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », Eurocrypt,‎ 1996 (lire en ligne [PDF])

• Cryptographie asymétrique
• Preuve à divulgation nulle de connaissance
• Signature numérique
• Heuristique de Fiat-Shamir

• [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],‎ 2010

• Portail de la cryptologie