Algoritmo de identificación de Schnorr

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:^[2]

• p es un primo grande (${\displaystyle p\approx 2^{1024}}$)
• q es un primo grande divisor de p-1 (${\displaystyle q\approx 2^{160}}$)
• ${\displaystyle g\in Z_{p}^{*}}$ tiene orden q por lo que es generador de un grupo ${\displaystyle G_{q}}$ el cual es un subrupo de ${\displaystyle Z_{p}^{*}}$
• t es un parámetro de seguridad tal que ${\displaystyle q>2^{t}}$ (La probabilidad del adversario de engañar a Alice o Bob será ${\displaystyle 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 ${\displaystyle x\in Z_{q},0\leq x\leq q-1}$ que se va a llamar clave secreta. A partir de ella construye ${\displaystyle y=g^{-x}(\mod p)}$ que será la correspondiente clave pública. Para calcularla podemos aprovechar que g tiene orden q en ${\displaystyle Z_{p}^{*}}$ y por tanto ${\displaystyle y=g^{-x}(\mod p)=g^{q-x}(\mod p)}$. 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.^[2]

Con el siguiente algoritmo el probador P puede probar que conoce x sin revelarlo al verificador V:^[2][1]

1. P escoge de forma aleatoria un valor ${\displaystyle c\in Z_{q},0\leq c\leq q-1}$, y envía a V su certificado y ${\displaystyle w=g^{c}(\mod p)}$
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 ${\displaystyle e\in Z_{q}}$ y ${\displaystyle 1\leq e\leq 2^{t}}$
3. P calcula ${\displaystyle s=c+xe\ (mod\ q)}$ y envía ${\displaystyle s}$ a V
4. V verifica la identidad de P si y solo si se cumple ${\displaystyle w=g^{s}y^{e}(\mod p)}$ ya que

${\displaystyle g^{s}y^{e}(\mod p)=g^{c+xe}y^{e}(\mod p)=g^{c+xe}g^{-xe}(\mod p)=g^{c}(\mod p)=w}$

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

• 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 ${\displaystyle y=g^{-x}(\mod p)=g^{q-x}(\mod p)=70322^{1031-755}\mod 88667=13136}$
• Supongamos que Alicia escoge c=543. Por tanto ${\displaystyle w=70322^{543}\mod 88667=84109}$
• Supongamos que Bob escoge el desafío e=1000. Entonces Alicia computa ${\displaystyle s=c+xe\ (mod\ q)=543+755*1000\mod 1031=851}$
• Bob verifica que ${\displaystyle 84109=70322^{851}13136^{1000}\mod 88667}$