Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Schnorr : prouver qu’on connaît une clé

Après cette leçon: Je peux lancer et vérifier le protocole de Schnorr avec de petits nombres.

Leçon de 65 min3 commandesLab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

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

MotCe que ça veut direExemple
Clé secrètele nombre x que seul le prouveur connaît
Clé publiquey, qui vaut G puissance x, modulo P
Nonceun nombre aléatoire utilisé pour une seule preuvek
Réponsece que le prouveur répond au défis = k + c * x modulo Q
Simulateurun 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.

  1. Engagement : le prouveur tire un k aléatoire et envoie t = G puissance k.
  2. Défi : le vérificateur envoie un c aléatoire.
  3. 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

Commande
docker exec jupyter python3 steps/schnorr.py

Affiché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é

ÉtapeQuiValeur
Secret et clé publiqueLe prouveurx = 65, y = 227
EngagementLe prouveur envoiet = 504
DéfiLe vérificateur envoiec = 77
RéponseLe prouveur envoies = 38
ContrôleLe vérificateurTrue

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

À vous : une preuve avec le secret 11

Code: python
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

Commande
docker exec jupyter python3 steps/simulate.py

Affiché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

Commande
docker exec jupyter python3 steps/bruteforce.py

Affichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.

À propos de ce labo et de sa source: Lab de preuves à divulgation nulle : engagements, Schnorr, Fiat-Shamir et Merkle en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.