Identificarte sin enviar tu clave
El protocolo de Schnorr es una prueba de conocimiento cero de que sabes el número secreto que hay detrás de una clave pública. Lo demuestras con tres mensajes cortos, y el secreto nunca sale de tu dispositivo.
Es la base de las firmas de Schnorr, que hoy se usan en sistemas reales.
Al terminar esta lección
Nota
Puedo ejecutar y verificar el protocolo de Schnorr con números pequeños.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Clave secreta | el número x que solo sabe el probador | |
| Clave pública | y, que es G elevado a x, mod P | |
| Nonce | un número aleatorio para una sola prueba | k |
| Respuesta | lo que contesta el probador al reto | s = k + c * x mod Q |
| Simulador | un programa que falsifica una transcripción sin el secreto |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Schnorr tiene tres movimientos
El probador sabe x, y todo el mundo sabe y = G elevado a x, mod P.
- Compromiso: el probador elige un k aleatorio y envía t = G elevado a k.
- Reto: el verificador envía un c aleatorio.
- Respuesta: el probador envía s = k + c por x, mod Q.
El verificador comprueba que G elevado a s es igual a t por y elevado a c, mod P. Los dos lados llegan a G elevado a k + c x.
Ejecuta una prueba de Schnorr
docker exec jupyter python3 steps/schnorr.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Ejemplo: lo que imprimió el laboratorio
| Paso | Quién | Valor |
|---|---|---|
| Secreto y clave pública | Probador | x = 65, y = 227 |
| Compromiso | El probador envía | t = 504 |
| Reto | El verificador envía | c = 77 |
| Respuesta | El probador envía | s = 38 |
| Comprobación | Verificador | True |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Pruébalo: una prueba con el secreto 11
P = 1019
Q = 509
G = 4
x = 11 # el secreto
y = pow(G, x, P) # la clave pública
print("clave pública y =", y)
k = 30 # el número aleatorio del probador, de un solo uso
t = pow(G, k, P)
c = 5 # el reto del verificador
s = (k + c * x) % Q
print("t =", t, "c =", c, "s =", s)
left = pow(G, s, P)
right = t * pow(y, c, P) % P
print("G ** s =", left, "y t * y ** c =", right)
# Cambia s por s + 1 y ejecuta otra vez. ¿Sigue pasando la comprobación?
Por qué el reto va al final
Imagina que el probador supiera c antes de enviar t. Podría elegir cualquier s y poner t = G elevado a s dividido entre y elevado a c. La comprobación pasaría sin necesitar x.
Eso es justo lo que hace un simulador. El simulador del laboratorio eligió primero c = 77 y s = 300, construyó t = 880 y la comprobación pasó. Así que una transcripción no demuestra nada a quien no eligió el reto, y por eso no revela nada.
Falsifica una transcripción sin el secreto
docker exec jupyter python3 steps/simulate.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Un nonce usado dos veces delata el secreto
Después el laboratorio respondió a un segundo reto con el mismo k. Dos respuestas, s y s2, para dos retos, c y c2, dan x = (s menos s2) dividido entre (c menos c2), mod Q. Imprimió 65.
No es solo un problema de juguete. Hay sistemas de firma reales que han filtrado claves porque se repitió un número aleatorio. Un nonce se usa una vez y se tira.
Un error frecuente
Advertencia
Mucha gente cree que el k aleatorio solo tiene que parecer aleatorio. Además, nunca se puede repetir. Si el mismo k responde a dos retos distintos, quien tenga las dos transcripciones saca la clave secreta con una división.
Encuentra el secreto probando todos los números
docker exec jupyter python3 steps/bruteforce.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.