Protocole d'authentification de Schnorr

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

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é 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 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é ecret.

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 Σ[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 , 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 et sous les mêmes paramètres publiques, alors l'extracteur renvoie le secret .

Cet extracteur se construit comme suit dans le cas du protocole de Schnorr : il va calculer .

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é 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 . Or 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 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 publiques, et au moment du défi, le tirage aléatoire de est remplacé par l'évaluation correspond au message à signer. La signature correspond au couple  ; au moment de la vérification, est recalculé comme , le verifieur teste si et accepte si cette vérification passe. La description complète est donné 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:

  1. Les paramètres publiques ( et ) sont générées de la même manière que pour le protocole Σ.
  2. Une fonction de hachage 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 , et va le définir comme sa clef secrète.
  4. Le signataire va ensuite calculer , et va le publier comme sa clef publique.

Signature(sk, m):

  1. Pour signer un message, le signataire va commencer par tirer un nombre au hasard, et définir .
  2. Le « défi » va ensuite être généré comme , et la réponse calculée comme .
  3. Finalement la signature est renvoyée: .

Vérification(vk, m, σ):

  1. Pour vérifier la signature , un utilisateur commence par recalculer en utilisant la clef publique : .
  2. 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[5] si le schéma d'identification sous-jacent est sûr.

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

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]

Liens externes[modifier | modifier le code]