Fiat-Shamira protokolla

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. joulukuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Fiat-Shamir-protokolla on yksi tunnetuimmista nolla - knowledge-tunnistusprotokollista. Pöytäkirjaa ehdottivat Amos Fiat ja Adi Shamir _ _

Kerro A: lle joitain salaisuuksia . Tämän salaisuuden tunteminen on todistettava jollekin osapuolelle B paljastamatta mitään salaista tietoa. Protokollan turvallisuus perustuu vaikeuteen poimia neliöjuuren modulo riittävän suuri yhdistelmäluku n , jonka tekijöiden jakoa ei tunneta.

Protokollan kuvaus

A todistaa B :lle, että hän tietää s : n t kierroksella. Kierrosta kutsutaan myös akkreditoinniksi. Jokainen akkreditointi koostuu 3 vaiheesta.

Alustavat toimet

Luotettu keskus T valitsee ja julkaisee moduulin , jossa p , q ovat yksinkertaisia ja salassa pidettyjä. $n = p*q$
Jokainen hakija A valitsee s koprimeen n : llä , missä . Sitten lasketaan V. T rekisteröi V :n A :n julkiseksi avaimeksi $s\in[1,n-1]$ $=s^2\pmod n$

Välitetyt viestit (kunkin akkreditoinnin vaiheet)

A B: $\Nuoli oikealle$ $x=r^2\pmod n$
A B: $\Vasen nuoli$ $e\in{0,1}$
A B: $\Nuoli oikealle$ $y=r*s^e\pmod n$

Perustoiminnot

Seuraavat toiminnot suoritetaan peräkkäin ja itsenäisesti t kertaa. B katsoo, että tieto on todistettu, jos kaikki t kierrokset onnistuivat.

A valitsee satunnaisen r :n , jonka se lähettää osapuolelle B (todistus) $r\in[1,n-1]$ $x=r^2\pmod n$
B valitsee satunnaisesti bitin e ( e =0 tai e =1) ja lähettää sen A: lle (puhelu)
A laskee y :n ja lähettää sen takaisin B :lle . Jos e = 0, niin , muuten (vastaus) $y=r$ $y=r*s\pmod n$
Jos y = 0, niin B hylkää todisteen, tai toisin sanoen A ei pystynyt todistamaan s :n tietämystä . Muussa tapauksessa osapuoli B tarkistaa, onko se voimassa , ja jos on, siirtyy protokollan seuraavalle kierrokselle. $y^2= x*v^e\pmod n$

e :n valinta joukosta {0,1} tarkoittaa, että jos osapuoli A todella tietää salaisuuden, se pystyy aina vastaamaan oikein, riippumatta e :n valinnasta . Oletetaan, että A haluaa huijata B :tä. Tässä tapauksessa A voi vastata vain tiettyyn e :n arvoon . Jos A esimerkiksi tietää saavansa e = 0, niin A:n tulee toimia tarkasti ohjeiden mukaan ja B hyväksyy vastauksen. Jos A tietää saavansa e = 1, niin A valitsee satunnaisen r :n ja lähettää sen puolelle B , jolloin saamme halutun . Ongelmana on, että A ei aluksi tiedä, mitä e hän saa, eikä siksi voi 100 %:n todennäköisyydellä lähettää puolelle B r :tä ja x :ää , joita tarvitaan pettämiseen ( jos e = 0 ja e = 1). Siksi pettämisen todennäköisyys yhdellä kierroksella on 50%. Pettämisen todennäköisyyden pienentämiseksi (se on yhtä suuri kuin ) t valitaan riittävän suureksi ( t =20, t =40). Siten B varmistaa, että A tietää, jos ja vain jos kaikki t kierrokset ovat onnistuneet. $x=r^2/v$ $y=r$ $x=r^2$ $x=r^2/v$ $1/2^t)$

Esimerkki

Anna luotetun keskuksen valita yksinkertainen p =683 ja q =811, sitten n =683*811=553913. A valitsee s = 43215.

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

A valitsee r =38177 ja laskee $x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$
Jos B lähetti e =0, niin A palauttaa y=38177. Muuten A palaa $y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$
Tarkista B : $y^2 \equiv x*v^e \pmod n$

Jos e oli 0, niin Vahvistettu. $y^2=38177^2\pmod{553913}=1457483329=138266$

Muuten, $y^2=266141^2 \pmod {553913}=70831031881 \pmod {553913}=514832$

ja Vahvistettu. $x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$

Kirjallisuus

Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 s. - ISBN 0-8493-8523-7 .
Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .