Protocolul Fiat-Shamira

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 decembrie 2020; verificarea necesită 1 editare .

Protocolul Fiat-Shamir este unul dintre cele mai cunoscute protocoale de identificare zero -knowledge. Protocolul a fost propus de Amos Fiat și Adi Shamir

Spune - i lui A câteva secrete . Este necesar să se dovedească cunoașterea acestui secret unei părți B fără a dezvălui vreo informație secretă. Securitatea protocolului se bazează pe dificultatea extragerii rădăcinii pătrate modulo un număr compus n suficient de mare a cărui factorizare este necunoscută.

Descrierea protocolului

A îi demonstrează lui B că știe s în t runde. Runda se mai numește și acreditare. Fiecare acreditare constă din 3 etape.

Acțiuni preliminare

Centrul de încredere T selectează și publică modulul , unde p , q sunt simple și ținute secrete. $n=p*q$
Fiecare solicitant A alege s coprim cu n , unde . Apoi se calculează V. V este înregistrat de T ca cheie publică a lui A $s\in[1,n-1]$ $=s^2\pmod n$

Mesaje transmise (etape ale fiecărei acreditări)

A B: $\Sageata dreapta$ $x=r^2\pmod n$
A B: $\Sageata stanga$ $e\în{0,1}$
A B: $\Sageata dreapta$ $y=r*s^e\pmod n$

Acțiuni de bază

Următoarele acțiuni sunt efectuate succesiv și independent de t ori. B consideră cunoștințele dovedite dacă toate rundele t au avut succes.

A alege un r aleator astfel încât să trimită părții B (dovada) $r\in[1,n-1]$ $x=r^2\pmod n$
B selectează aleatoriu bitul e ( e =0 sau e =1) și îl trimite către A (apel)
A calculează y și îl trimite înapoi la B . Dacă e =0, atunci , în caz contrar (răspuns) $y=r$ $y=r*s\pmod n$
Dacă y =0, atunci B respinge demonstrația sau, cu alte cuvinte, A nu a reușit să demonstreze cunoașterea lui s . În caz contrar, partea B verifică dacă este validă și, dacă da, trece la următoarea rundă a protocolului. $y^2= x*v^e\pmod n$

Alegerea lui e din setul {0,1} implică faptul că, dacă partea A știe cu adevărat secretul, atunci va putea întotdeauna să răspundă corect, indiferent de alegerea lui e . Să presupunem că A vrea să-l înșele pe B. În acest caz, A , poate răspunde doar la o anumită valoare a lui e . De exemplu, dacă A știe că va obține e = 0, atunci A ar trebui să acționeze strict conform instrucțiunilor și B va accepta răspunsul. Dacă A știe că va primi e = 1, atunci A alege un r aleatoriu și îl trimite în partea B , ca rezultat obținem . Problema este că A nu știe inițial ce e va primi și, prin urmare, nu poate trimite cu 100% probabilitate către partea B r și x necesare pentru a înșela ( pentru e = 0 și pentru e = 1). Prin urmare, probabilitatea de a înșela într-o rundă este de 50%. Pentru a reduce probabilitatea de a înșela (este egal cu ) t este ales suficient de mare ( t =20, t =40). Astfel, B se asigură că A știe dacă și numai dacă toate rundele t au avut succes. $x=r^2/v$ $y=r$ $x=r^2$ $x=r^2/v$ $1/2^t)$

Exemplu

Lăsați centrul de încredere să aleagă simplu p =683 și q =811, apoi n =683*811=553913. A alege s =43215.

Unde $v=43215^2 \pmod{553913}= 1867536225 \pmod{553913}=295502$

A alege r =38177 și contează $x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$
Dacă B a trimis e =0, atunci A returnează y=38177. În caz contrar, A revine $y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$
Verificați B : $y^2 \equiv x*v^e \pmod n$

Dacă e a fost egal cu 0, atunci Confirmat. $y^2=38177^2\pmod{553913}=1457483329=138266$

In caz contrar, $y^2=266141^2 \pmod {553913}=70831031881 \pmod {553913}=514832$

și Confirmat. $x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$

Literatură

Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .