Fiat-Shamira protokoll

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. december 16-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Fiat-Shamir protokoll az egyik legismertebb nulla tudású azonosítási protokoll. A protokollt Amos Fiat és Adi Shamir javasolta _

Ismertesse meg A titkokat . Bizonyítani kell ennek a titoknak a ismeretét valamelyik B félnek anélkül, hogy bármilyen titkos információt felfedne. A protokoll biztonsága azon a nehézségen alapszik, hogy a négyzetgyök modulo egy kellően nagy n összetett számból nyerhető ki, amelynek faktorizációja ismeretlen.

A protokoll leírása

A t körben bizonyítja B -nek, hogy tudja , hogy s . A fordulót akkreditációnak is nevezik. Minden akkreditáció 3 szakaszból áll.

Előzetes intézkedések

A T megbízható központ kiválasztja és közzéteszi a modult , ahol p , q egyszerű és titkos . $n=p*q$
Minden A pályázó választja az s koprímet n - nel , ahol . Ekkor kiszámítjuk a V -t . V -t T regisztrálja A nyilvános kulcsaként $s\in[1,n-1]$ $=s^2\pmod n$

Továbbított üzenetek (az egyes akkreditációk szakaszai)

A B: $\Jobb nyíl$ $x=r^2\pmod n$
A B: $\Bal nyíl$ $e\in{0,1}$
A B: $\Jobb nyíl$ $y=r*s^e\pmod n$

Alapműveletek

A következő műveleteket egymás után és egymástól függetlenül hajtják végre t alkalommal. B a tudást bizonyítottnak tekinti, ha minden t kör sikeres volt.

A véletlenszerű r -t választ , amelyet elküld B félnek (bizonyíték) $r\in[1,n-1]$ $x=r^2\pmod n$
B véletlenszerűen kiválasztja az e bitet ( e =0 vagy e =1), és elküldi A -nak (hívás)
A kiszámítja y -t és visszaküldi B -nek . Ha e =0, akkor , egyébként (válasz) $y=r$ $y=r*s\pmod n$
Ha y =0, akkor B elutasítja a bizonyítást, vagy más szóval A nem tudta bizonyítani s ismeretét . Ellenkező esetben B fél ellenőrzi, hogy érvényes -e, és ha igen, akkor továbblép a jegyzőkönyv következő fordulójára. $y^2= x*v^e\pmod n$

Az e választása a {0,1} halmazból azt jelenti, hogy ha A fél valóban ismeri a titkot, akkor mindig tud helyesen válaszolni, függetlenül az e választásától . Tegyük fel, hogy A meg akarja csalni B -t. Ebben az esetben A , csak egy adott e értékre tud válaszolni . Például, ha A tudja, hogy e = 0 lesz, akkor A - nak szigorúan az utasítások szerint kell eljárnia, és B elfogadja a választ. Ha A tudja, hogy e = 1-et kap, akkor A véletlenszerű r -t választ, és elküldi a B oldalra , így megkapjuk a kívántat . A probléma az, hogy A kezdetben nem tudja, hogy mit fog kapni, és ezért nem tudja 100%-os valószínűséggel elküldeni a B oldalnak a megtévesztéshez szükséges r - t és x - et ( e = 0 és e = 1 esetén). Ezért a csalás valószínűsége egy körben 50%. A csalás valószínűségének csökkentése érdekében (ez egyenlő ) t -t kellően nagynak választjuk ( t =20, t =40). Így B gondoskodik arról, hogy A tudja, hogy minden t kör sikeres volt - e, és csak akkor . $x=r^2/v$ $y=r$ $x=r^2$ $x=r^2/v$ $1/2^t)$

Példa

Hagyja, hogy a megbízható központ válasszon egyszerű p =683 és q =811 értéket, majd n =683*811=553913. A az s =43215 értéket választja .

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

A kiválasztja az r =38177-et, és számol $x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$
Ha B e =0 értéket küld , akkor A y=38177 értéket ad vissza. Ellenkező esetben A visszatér $y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$
B ellenőrzés : $y^2 \equiv x*v^e \pmod n$

Ha e egyenlő 0, akkor Megerősítve. $y^2=38177^2\pmod{553913}=1457483329=138266$

Másképp, $y^2=266141^2 \pmod {553913}=70831031881 \pmod {553913}=514832$

és Megerősítve. $x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$

Irodalom

Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7 .
Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .