Algoritmo de identificación de Schnorr

El Algoritmo de identificación de Schnorr es un esquema de identificación que se puede usar como prueba de conocimiento cero del conocimiento de la clave secreta del algoritmo de cifrado de ElGamal sin revelarla.

Descripción

El esquema requiere que una autoridad confiable, vamos a llamar TA, defina una serie de parámetros públicos para el esquema que cumplan una serie de propiedades:

• p es un primo grande ($p\approx 2^{1024}$)
• q es un primo grande divisor de p-1 ($q\approx 2^{160}$)
• $g\in Z_p^{*}$ tiene orden q por lo que es generador de un grupo $G_q$ el cual es un subrupo de $Z_p^{*}$
• t es un parámetro de seguridad tal que $q>2^t$ (La probabilidad del adversario de engañar a Alice o Bob será $2^{-t}$, así que t=40 dará una seguridad adecuada para la mayor parte de las aplicaciones)

Los parámetros p,q,g y t son públicos y serán usados por todas las parte en la red

Cada usuario de la red escoge su $x\in Z_q,0\le x\le q-1$ que se va a llamar clave secreta. A partir de ella construye $y=g^{-x}(modp)$ que será la correspondiente clave pública. Para calcularla podemos aprovechar que g tiene orden q en $Z_p^{*}$ y por tanto $y=g^{-x}(modp)=g^{q-x}(modp)$. Para cada usuario de la red (información de identificación) la TA certificará (creando un certificado con firma digital) su clave pública. El certificado también puede contener los parámetros p,q,g y t públicos.

Con el siguiente algoritmo el probador P puede probar que conoce x sin revelarlo al verificador V:

1. P escoge de forma aleatoria un valor $c\in Z_q,0\le c\le q-1$, y envía a V su certificado y $w=g^c(modp)$
2. V verifica, a partir del certificado, que la clave pública de P es y. A continuación envía a P un desafío aleatorio $e\in Z_q$ y $1\le e\le 2^t$
3. P calcula $s=c+xe(modq)$ y envía $s$ a V
4. V verifica la identidad de P si y solo si se cumple $w=g^s{y}^e(modp)$ ya que

$g^s{y}^e(modp)=g^{c+xe}{y}^e(modp)=g^{c+xe}{g}^{-xe}(modp)=g^c(modp)=w$

Ejemplo

Veamos un ejemplo de aplicación de algoritmo omitiendo la parte del certificado emitido por la TA

• Supongamos p=88667, q=1031, t=10 y g=70322.
• Supongamos que Alicia escoge como clave privada x=755.
• Por tanto la clave pública es $y=g^{-x}(modp)=g^{q-x}(modp)=70322^{1031-755}mod88667=13136$
• Supongamos que Alicia escoge c=543. Por tanto $w=70322^{543}mod88667=84109$
• Supongamos que Bob escoge el desafío e=1000. Entonces Alicia computa $s=c+xe(modq)=543+755*1000mod1031=851$
• Bob verifica que $84109=70322^{851}13136^{1000}mod88667$

Propiedades

Se puede demostrar que el algoritmo de identificación de Schnorr es muy rápido y eficiente, tanto desde un punto de vista computacional como de la cantidad de información que necesita ser intercambiada entre las partes.

Se puede demostrar que un parámetro de seguridad t suficientemente grande evita que un impostor pueda suplantar la identidad de un usuario legítimo. La probabilidad de que un impostor pueda suplantar es $2^{-t}$ siempre que e sea elegida de forma aleatoria.

Se puede demostrar que el sistema propuesto verifica los requisitos de una prueba de conocimiento cero: Totalidad, solvencia y conocimiento cero. Esto implica que el sistema es seguro bajo la suposición de la clave privada es imposible de calcular (logaritmo discreto).

Prueba de conocimiento cero de clave de cifrado de ElGamal

Además, para un texto cifrado de ElGamal $(G,M)=(m{y}^r,g^r)$, el algoritmo de identificación de Schnorr puede ser usado para probar el conocimiento del texto plano m sin revelarlo. El protocolo primero prueba que P conoce el factor de cegado r en $g^r$. Como $y$ es un parámetro público, si P conoce r, puede recuperar m calculando $m=G/y^r$. Por tanto el protocolo también prueba que P conoce el texto plano m.