Algoritme d'identificació de Schnorr

El Algoritme d'identificació de Schnorr és un esquema d'identificació que es pot usar com prova de coneiximent zero del coneiximent de la clau secreta de l'algoritme de sifrat de ElGamal sense revelar-la.

Descripció

L'esquema requerix que una autoritat confiable, anem a cridar TA, definixca una série de paràmetros públics per a l'esquema que complixquen una série de propietats: p és un cosí gran ($p\approx 2^{1024}$) q és un cosí gran divisor de p-1 ($q\approx 2^{160}$)

• $g\in Z_p^{*}$ té orde q per lo que és generador d'un grup $G_q$ el qual és un subrupo de $Z_p^{*}$

t és un paràmetro de seguritat tal que $q>2^t$ (La provabilitat de l'adversari d'enganyar a Alice o Bob serà $2^{-t}$, aixina que t=40 donarà una seguritat adequada per a la major part de les aplicacions) Els paràmetros p,q,g i t són públics i seran usats per totes les part en la ret

Cada usuari de la ret tria la seua $x\in Z_q,0\le x\le q-1$ que es va a cridar clau secreta. A partir d'ella construïx $y=g^{-x}(modp)$ que serà la corresponent clau pública. Per a calcular-la podem aprofitar que g té orde q en $Z_p^{*}$ i per tant $y=g^{-x}(modp)=g^{q-x}(modp)$. Per a cada usuari de la ret (informació d'identificació) la TA certificarà (creant un certificat en firma digital) la seua clau pública. El certificat també pot contindre els paràmetros p,q,g i t públics.

En el següent algoritme el provador P pot provar que coneix x sense revelar-ho al verificador V:

P tria de forma aleatòria un valor $c\in Z_q,0\le c\le q-1$, i envia a V el seu certificat i $w=g^c(modp)$

V verifica, a partir del certificat, que la clau pública de P és i. A continuació envia a P un desafiu aleatori $e\in Z_q$ i $1\le e\le 2^t$

P calcula $s=c+xe(modq)$ i envia $s$ a

V :V verifica l'identitat de P si i solament si es complix $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$

Eixemple

Vejam un eixemple d'aplicació d'algoritme ometent la part del certificat emés per la TA Supongam p=88667, q=1031, t=10 i g=70322. Supongam que Alicia tria com a clau privada x=755. Per tant la clau pública és $y=g^{-x}(modp)=g^{q-x}(modp)=70322^{1031-755}mod88667=13136$ Supongam que Alicia tria c=543. Per tant $w=70322^{543}mod88667=84109$ Supongam que Bob tria el desafiu i=1000. Llavors Alicia computa $s=c+xe(modq)=543+755*1000mod1031=851$ Bob verifica que $84109=70322^{851}13136^{1000}mod88667$