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é $g^{a}$ , prouver que l'on connaît l'exposant $a$ dans un groupe $G$ engendré par $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.

Description du protocole de Schnorr[modifier | modifier le code]

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.

Paramètres publics[modifier | modifier le code]

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

Données connues uniquement du prouveur[modifier | modifier le code]

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

Déroulé du protocole[modifier | modifier le code]

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

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

Ensuite commence la phase du défi:

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

Finalement, la phase de réponse:

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

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

Preuves de sécurité[modifier | modifier le code]

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.

Complétude[modifier | modifier le code]

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 $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.

Robustesse spéciale[modifier | modifier le code]

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

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

Non-divulgation de connaissance sous un vérifieur honnête[modifier | modifier le code]

Cette propriété se caractérise par l'existence d'un simulateur probabiliste qui fonctionne en temps polynomial qui, étant donné $(v,c)$ où $c$ est distribué comme un défis correct, alors le simulateur renvoie une transcription $(R,c,a)$ distribuée comme une vraie transcription pour $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 $a$ uniformément dans $\mathbb {Z} _{q}^{\star }$ et va générer $R$ pour qu'il vérifie la condition d'acceptation, c'est-à-dire $R=g^{a}\cdot v^{c}$ , et va renvoyer $(R,c,a)$ . On peut remarquer que $R$ est distribué uniformément puisque son logarithme discret selon la base $g$ l'est. Et par construction $a$ est distribué comme une réponse acceptante vis-à-vis de $(R,c)$ .

Taille des paramètres[modifier | modifier le code]

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

Schéma de signature[modifier | modifier le code]

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 ${\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 $c$ est remplacé par l'évaluation $c\gets {\mathcal {H}}(R,m)$ où $m\in \{0,1\}^{*}$ correspond au message à signer. La signature correspond au couple $(c,a)$ ; au moment de la vérification, $R$ est recalculé comme $R'=g^{a}\cdot v^{c}$ , le vérifieur teste si ${\mathcal {H}}(R',m)=c$ et accepte si cette vérification passe. La description complète est donnée ci-dessous.

Description[modifier | modifier le code]

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

Génération de clefs:

Les paramètres publiques ( $q$ et $g$ ) sont générées de la même manière que pour le protocole Σ.
Une fonction de hachage ${\mathcal {H}}:G\times \{0,1\}^{*}\to \mathbb {Z} _{q}^{\star }$ est ensuite générée et rajoutée aux paramètres publiques.
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 $s\in \mathbb {Z} _{q}^{\star }$ , et va le définir comme sa clef secrète.
Le signataire va ensuite calculer $v=g^{s}$ , et va le publier comme sa clef publique.

Signature(sk, m):

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

Vérification(vk, m, σ):

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

Efficacité[modifier | modifier le code]

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

Sécurité prouvée[modifier | modifier le code]

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.

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

↑ Schnorr 1989.
↑ Feige, Fiat et Shamir 1988.
↑ ^{a et b} Fiat et Shamir 1986.
↑ ^{a et b} Damgård 2010.
↑ Pointcheval et Stern 1996.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[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])

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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

Portail de la cryptologie

[Schnorr1989-1] Schnorr 1989.

[FeigeFiatShamir1988-2] Feige, Fiat et Shamir 1988.

[FiatShamir1986-3] {a et b} Fiat et Shamir 1986.

[Damgård2010-4] {a et b} Damgård 2010.

[PointchevalStern1996-5] Pointcheval et Stern 1996.

[1]

[2]

[3]

[4]

[5]