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é , prouver que l'on connaît l'exposant dans un groupe engendré par .
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 .
Depuis 2021, le protocole Bitcoin implémente l'algorithme de signature établi sur le protocole de Schnorr, en plus de l'algorithme ECDSA choisit initialement par Satoshi Nakamoto[4].
Description du protocole de Schnorr
[modifier | modifier le code]Comme d'autres preuves à connaissances nulles, le protocole de Schnorr est un protocole Σ[5]: 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 premier. On note qu'il définit un groupe d'ordre engendré par , noté multiplicativement dans la suite.
- Un élément de groupe , d'ordre C'est ici un générateur d'un sous-groupe d'ordre de
- sont publics.
Données connues uniquement du prouveur
[modifier | modifier le code]- Un entier pris au hasard dans .
- Le prouveur calcule , et est rendu public, certifié par une autorité de confiance, tandis que 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 dans .
- P calcule et envoie à V
Ensuite commence la phase du défi:
- V tire un entier dans et l'envoie à P
Finalement, la phase de réponse:
- P calcule et l'envoie à V.
V accepte si et seulement si à l'issue du protocole, la relation est vérifiée.
Preuves de sécurité
[modifier | modifier le code]Pour prouver la sécurité d'un protocole Σ[5], 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 , 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 et sous les mêmes paramètres publics, alors l'extracteur renvoie le secret .
Cet extracteur se construit comme suit dans le cas du protocole de Schnorr : il va calculer et retourner , car cette valeur correspond au logarithme discret de par . En effet, les transcriptions et étant acceptantes, les relations et sont vérifiées, donnant ainsi puisque .
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é où est distribué comme un défis correct, alors le simulateur renvoie une transcription distribuée comme une vraie transcription pour . 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 uniformément dans et va générer pour qu'il vérifie la condition d'acceptation, c'est-à-dire , et va renvoyer . On peut remarquer que est distribué uniformément puisque son logarithme discret selon la base l'est. Et par construction est distribué comme une réponse acceptante vis-à-vis de .
Taille des paramètres
[modifier | modifier le code]La spécification du brevet indique que le groupe doit être choisi comme un sous-groupe d'au moins 140 bits d'un groupe où 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 est introduite dans les paramètres publics, et au moment du défi, le tirage aléatoire de est remplacé par l'évaluation où correspond au message à signer. La signature correspond au couple ; au moment de la vérification, est recalculé comme , le vérifieur teste si 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 ( et ) sont générées de la même manière que pour le protocole Σ.
- Une fonction de hachage 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 , et va le définir comme sa clef secrète.
- Le signataire va ensuite calculer , et va le publier comme sa clef publique.
Signature(sk, m):
- Pour signer un message, le signataire va commencer par tirer un nombre au hasard, et définir .
- Le « défi » va ensuite être généré comme , et la réponse calculée comme .
- Finalement la signature est renvoyée: .
Vérification(vk, m, σ):
- Pour vérifier la signature , un utilisateur commence par recalculer en utilisant la clef publique : .
- L'utilisateur va ensuite accepter si et seulement si .
Efficacité
[modifier | modifier le code]Cela donne une signature de taille 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[6] 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.
- Fiat et Shamir 1986.
- (en) Andreas M Antonopoulos, Mastering Bitcoin: Programming the Open Blockchain, Sebastopol, Californie, États-Unis, O'Reilly Media, , 3e éd., 239 p. (ISBN 9781098150099, OCLC 953432201).
- 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, (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, (lire en ligne [PDF])
- [Schnorr 1989] (en) Claus-Peter Schnorr, « Efficient Identification and Signature for Smart Cards », Theory and Application of Cryptology, Springer, (lire en ligne)
- [Pointcheval et Stern 1996] (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », Eurocrypt, (lire en ligne [PDF])
Articles connexes
[modifier | modifier le code]- Cryptographie asymétrique
- Preuve à divulgation nulle de connaissance
- Signature numérique
- Heuristique de Fiat-Shamir
Liens externes
[modifier | modifier le code]- [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],