Protocolo Fiat-Shamira

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de diciembre de 2020; la verificación requiere 1 edición .

El protocolo Fiat-Shamir es uno de los protocolos de identificación de conocimiento cero más conocidos . El protocolo fue propuesto por Amos Fiat y Adi Shamir

Hágale saber a A algunos secretos . Es necesario demostrar el conocimiento de este secreto a alguna parte B sin revelar ninguna información secreta. La seguridad del protocolo se basa en la dificultad de extraer la raíz cuadrada módulo de un número compuesto n suficientemente grande cuya factorización se desconoce.

Descripción del protocolo

A le demuestra a B que sabe s en t rondas. La ronda también se llama acreditación. Cada acreditación consta de 3 etapas.

Acciones preliminares

El centro de confianza T selecciona y publica el módulo , donde p , q son simples y se mantienen en secreto. $n=p*q$
Cada aspirante A elige s coprimos con n , donde . Luego se calcula V. V está registrado por T como clave pública de A $s\in[1,n-1]$ $=s^2\pmod n$

Mensajes transmitidos (etapas de cada acreditación)

AB : $\Flecha correcta$ $x=r^2\pmod n$
AB : $\Flecha izquierda$ $e\en{0,1}$
AB : $\Flecha correcta$ $y=r*s^e\pmod n$

Acciones básicas

Las siguientes acciones se realizan secuencial e independientemente t veces. B considera probado el conocimiento si todas las rondas fueron exitosas.

A elige una r aleatoria tal que la envía a la parte B (prueba) $r\en[1,n-1]$ $x=r^2\pmod n$
B selecciona aleatoriamente el bit e ( e =0 o e =1) y lo envía a A (llamada)
A calcula y y se lo devuelve a B. Si e =0, entonces , de lo contrario (respuesta) $y = r$ $y=r*s\pmod n$
Si y = 0, entonces B rechaza la prueba o, en otras palabras, A no pudo probar el conocimiento de s . De lo contrario, la parte B verifica si es válido y, de ser así, continúa con la siguiente ronda del protocolo. $y^2= x*v^e\pmod n$

La elección de e del conjunto {0,1} implica que si la parte A realmente conoce el secreto, siempre podrá responder correctamente, independientemente de la elección de e . Digamos que A quiere engañar a B. En este caso, A , solo puede responder a un valor específico de e . Por ejemplo, si A sabe que obtendrá e = 0, entonces A debe actuar estrictamente de acuerdo con las instrucciones y B aceptará la respuesta. Si A sabe que recibirá e = 1, entonces A elige una r aleatoria y la envía al lado B , como resultado obtenemos la deseada . El problema es que A inicialmente no sabe qué e recibirá y por lo tanto no puede con un 100% de probabilidad enviar al lado B la r y la x necesarias para engañar ( para e = 0 y para e = 1). Por lo tanto, la probabilidad de hacer trampa en una ronda es del 50%. Para reducir la probabilidad de hacer trampa (es igual a ) t se elige suficientemente grande ( t =20, t =40). Por lo tanto, B se asegura de que A sepa si y solo si todas las t rondas han tenido éxito. $x=r^2/v$ $y = r$ $x=r^2$ $x=r^2/v$ $1/2^t)$

Ejemplo

Deje que el centro de confianza elija simple p = 683 y q = 811, luego n = 683 * 811 = 553913. A elige s =43215.

Dónde $v=43215^2 \pmod{553913}= 1867536225 \pmod{553913}=295502$

A elige r =38177 y cuenta $x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$
Si B envió e =0, entonces A devuelve y=38177. De lo contrario, A vuelve $y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$
Compruebe B : $y^2 \equiv x*v^e \pmod n$

Si e era igual a 0, entonces Confirmado. $y^2=38177^2\pmod{553913}=1457483329=138266$

De lo contrario, $y^2=266141^2 \pmod {553913}=70831031881 \pmod {553913}=514832$

y Confirmado. $x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$

Literatura

Menezes A., van Oorschot P., Vanstone S. Manual de criptografía aplicada. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .