Se connecter sans envoyer sa clé
Le protocole de Schnorr est une preuve à divulgation nulle : vous prouvez que vous connaissez le nombre secret derrière une clé publique. La preuve tient en trois courts messages, et le secret ne quitte jamais votre appareil.
C’est la base des signatures de Schnorr, utilisées aujourd’hui dans de vrais systèmes.
À la fin de cette leçon
Remarque
Je peux lancer et vérifier le protocole de Schnorr avec de petits nombres.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Clé secrète | le nombre x que seul le prouveur connaît | |
| Clé publique | y, qui vaut G puissance x, modulo P | |
| Nonce | un nombre aléatoire utilisé pour une seule preuve | k |
| Réponse | ce que le prouveur répond au défi | s = k + c * x modulo Q |
| Simulateur | un programme qui fabrique une transcription sans le secret |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Schnorr se joue en trois échanges
Le prouveur connaît x, et tout le monde connaît y = G puissance x, modulo P.
- Engagement : le prouveur tire un k aléatoire et envoie t = G puissance k.
- Défi : le vérificateur envoie un c aléatoire.
- Réponse : le prouveur envoie s = k + c fois x, modulo Q.
Le vérificateur contrôle que G puissance s est égal à t fois y puissance c, modulo P. Les deux côtés valent G puissance k + c x.
Lancer une preuve de Schnorr
docker exec jupyter python3 steps/schnorr.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Exemple travaillé : ce que le labo a affiché
| Étape | Qui | Valeur |
|---|---|---|
| Secret et clé publique | Le prouveur | x = 65, y = 227 |
| Engagement | Le prouveur envoie | t = 504 |
| Défi | Le vérificateur envoie | c = 77 |
| Réponse | Le prouveur envoie | s = 38 |
| Contrôle | Le vérificateur | True |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À vous : une preuve avec le secret 11
P = 1019
Q = 509
G = 4
x = 11 # le secret
y = pow(G, x, P) # la clé publique
print("clé publique y =", y)
k = 30 # le nombre aléatoire du prouveur, utilisé une fois
t = pow(G, k, P)
c = 5 # le défi du vérificateur
s = (k + c * x) % Q
print("t =", t, "c =", c, "s =", s)
gauche = pow(G, s, P)
droite = t * pow(y, c, P) % P
print("G ** s =", gauche, "et t * y ** c =", droite)
# Remplacez s par s + 1 et relancez. Le contrôle passe-t-il encore ?
Pourquoi le défi doit venir en dernier
Supposons que le prouveur connaisse c avant d’envoyer t. Il pourrait choisir n’importe quel s et poser t = G puissance s divisé par y puissance c. Le contrôle passerait, sans jamais avoir besoin de x.
C’est exactement ce que fait un simulateur. Celui du labo a choisi c = 77 et s = 300 d’abord, a fabriqué t = 880, et le contrôle a passé. Une transcription ne prouve donc rien à qui n’a pas choisi le défi : voilà pourquoi elle ne dévoile rien.
Fabriquer une transcription sans le secret
docker exec jupyter python3 steps/simulate.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Un nonce utilisé deux fois livre le secret
Le labo a ensuite répondu à un second défi avec le même k. Deux réponses, s et s2, pour deux défis, c et c2, donnent x = (s moins s2) divisé par (c moins c2), modulo Q. Le labo a affiché 65.
Ce n’est pas qu’un problème de jouet. De vrais systèmes de signature ont laissé fuir des clés parce qu’un nombre aléatoire s’était répété. Un nonce sert une fois, puis on le jette.
Erreur fréquente
Attention
On croit souvent que le k aléatoire doit seulement avoir l’air aléatoire. Il ne doit surtout jamais se répéter. Si le même k répond à deux défis différents, quiconque a les deux transcriptions retrouve la clé secrète avec une seule division.
Trouver le secret jouet en essayant tout
docker exec jupyter python3 steps/bruteforce.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.