¿Te resulta más fácil leer con fondo crema, un tono de color, más contraste o un texto más grande? Elige tus colores y tu texto una sola vez, para todas las páginas.

Lección gratuita

Schnorr: demostrar que sabes una clave

Después de esta lección: Puedo ejecutar y verificar el protocolo de Schnorr con números pequeños.

Lección de 65 min3 comandosLaboratorio de pruebas de conocimiento cero: compromisos, Schnorr, Fiat-Shamir y Merkle en Python

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

PalabraQué significaEjemplo
Clave secretael número x que solo sabe el probador
Clave públicay, que es G elevado a x, mod P
Nonceun número aleatorio para una sola pruebak
Respuestalo que contesta el probador al retos = k + c * x mod Q
Simuladorun 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.

  1. Compromiso: el probador elige un k aleatorio y envía t = G elevado a k.
  2. Reto: el verificador envía un c aleatorio.
  3. 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

Comando
docker exec jupyter python3 steps/schnorr.py

Se muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.

Ejemplo: lo que imprimió el laboratorio

PasoQuiénValor
Secreto y clave públicaProbadorx = 65, y = 227
CompromisoEl probador envíat = 504
RetoEl verificador envíac = 77
RespuestaEl probador envías = 38
ComprobaciónVerificadorTrue

Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.

Pruébalo: una prueba con el secreto 11

Código: python
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

Comando
docker exec jupyter python3 steps/simulate.py

Se 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

Comando
docker exec jupyter python3 steps/bruteforce.py

Se muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.

Sobre este laboratorio y su código: Laboratorio de pruebas de conocimiento cero: compromisos, Schnorr, Fiat-Shamir y Merkle en Python

¿Enseñas a una clase? Asigna este módulo a tus alumnos con guía del profesor, tareas con corrección automática y un laboratorio para cada alumno.