Le protocole d'identification de Schnorr

Comment convaincre quelqu'un que vous connaissez un mot de passe sans le prononcer ? C'est exactement ce que résout le protocole d'identification de Schnorr, publié en 1989.

Le décor mathématique

On travaille dans un groupe où le logarithme discret est difficile : on se donne un générateur g et un grand ordre premier. Chacun possède une paire de clés :

• une clé privée x, un nombre secret ;
• une clé publique y = g^x, diffusée librement.

Calculer y à partir de x est facile. Faire l'inverse — retrouver x à partir de y — est le problème du logarithme discret, hors de portée pour de grands paramètres. C'est la même asymétrie qui protège RSA, mais fondée sur un autre problème difficile.

Le prouveur (appelons-le Pierre) veut convaincre le vérifieur (Valérie) qu'il connaît le x correspondant à y, sans révéler x.

Les trois échanges

Le protocole tient en trois messages, un schéma qu'on appelle engagement – défi – réponse.

   Pierre (connaît x)                Valérie (connaît y)
   ------------------                -------------------
1. choisit un aléa r
   calcule t = g^r
                        --- t --->        (engagement)

2.                                     choisit un défi
                                       aléatoire c
                        <--- c ---
3. calcule s = r + c*x
                        --- s --->
                                       vérifie que
                                       g^s = t * y^c ?

Détaillons chaque étape :

1. Engagement. Pierre tire un nombre aléatoire r (un nonce), calcule t = g^r et envoie t. Il s'engage sur r sans le dévoiler.
2. Défi. Valérie tire un nombre aléatoire c et l'envoie. Elle ne sait rien encore.
3. Réponse. Pierre calcule s = r + c*x et l'envoie.

La vérification

Valérie accepte si et seulement si :

g^s = t * y^c

Vérifions que l'égalité tient quand Pierre est honnête. On remplace s par r + c*x :

g^s = g^(r + c*x) = g^r * g^(c*x) = g^r * (g^x)^c = t * y^c

L'égalité est bien satisfaite. Pierre n'a jamais envoyé x. Il a seulement envoyé t (qui masque r) et s (qui mélange r et x). La clé secrète reste invisible.

Pourquoi un tricheur échoue

Imaginez Marc, qui ne connaît pas x. Il peut envoyer un t quelconque, mais il devra ensuite produire un s tel que g^s = t * y^c, pour un c qu'il ne connaît pas encore au moment de choisir t. Sans x, il est coincé : soit il triche sur t en pariant sur un c, soit il échoue à la vérification. Nous verrons à la leçon suivante pourquoi ce piège est solide.

En résumé

Schnorr permet de prouver la connaissance d'une clé privée x par trois échanges — engagement t = g^r, défi c, réponse s = r + c*x — validés par l'unique test g^s = t * y^c. Le secret n'est jamais transmis, seulement démontré.