Fiat-Shamira-protokollet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 december 2020; verifiering kräver 1 redigering .

Fiat-Shamir-protokollet är ett av de mest välkända noll - kunskapsidentifieringsprotokollen. Protokollet föreslogs av Amos Fiat och Adi Shamir _

Låt A veta några hemligheter . Det är nödvändigt att bevisa kännedom om denna hemlighet för någon part B utan att avslöja någon hemlig information. Säkerheten för protokollet är baserad på svårigheten att extrahera kvadratroten modulo ett tillräckligt stort sammansatt antal n vars faktorisering är okänd.

Beskrivning av protokollet

A bevisar för B att han kan s i t omgångar. Omgången kallas även ackreditering. Varje ackreditering består av 3 steg.

Preliminära åtgärder

Det betrodda centret T väljer och publicerar modulen , där p , q är enkla och hålls hemliga. $n=p*q$
Varje sökande A väljer s coprime med n , där . Sedan beräknas V . V registreras av T som A :s publika nyckel $s\in[1,n-1]$ $=s^2\pmod n$

Meddelanden som förmedlas (stadier av varje ackreditering)

A B: $\Höger pil$ $x=r^2\pmod n$
A B: $\Vänster pil$ $e\in{0,1}$
A B: $\Höger pil$ $y=r*s^e\pmod n$

Grundläggande åtgärder

Följande åtgärder utförs sekventiellt och oberoende t gånger. B anser att kunskapen är bevisad om alla t omgångar var framgångsrika.

A väljer en slumpmässig r så att den skickar till part B (bevis) $r\in[1,n-1]$ $x=r^2\pmod n$
B väljer slumpmässigt bit e ( e =0 eller e =1) och skickar den till A (anrop)
A beräknar y och skickar tillbaka det till B . Om e =0, då , annars (svar) $y=r$ $y=r*s\pmod n$
Om y =0, då förkastar B beviset, eller, med andra ord, A misslyckades med att bevisa kunskap om s . I annat fall kontrollerar part B om det är giltigt och går i så fall vidare till nästa omgång av protokollet. $y^2= x*v^e\pmod n$

Valet av e från mängden {0,1} innebär att om part A verkligen känner till hemligheten, så kommer den alltid att kunna svara rätt, oavsett valet av e . Låt oss säga att A vill lura B. I detta fall kan A endast svara på ett specifikt värde på e . Till exempel, om A vet att han kommer att få e = 0, då bör A agera strikt enligt instruktionerna och B kommer att acceptera svaret. Om A vet att han kommer att få e = 1, så väljer A ett slumpmässigt r och skickar det till sida B , som ett resultat får vi det önskade . Problemet är att A initialt inte vet vad e han kommer att få och därför inte med 100 % sannolikhet kan skicka till sidan B de r och x som behövs för att lura ( för e = 0 och för e = 1). Därför är sannolikheten för fusk i en omgång 50%. För att minska sannolikheten för fusk (det är lika med ) väljs t tillräckligt stort ( t =20, t =40). Således ser B till att A vet om och endast om alla t omgångar har varit framgångsrika. $x=r^2/v$ $y=r$ $x=r^2$ $x=r^2/v$ $1/2^t)$

Exempel

Låt den betrodda centern välja enkel p =683 och q =811, sedan n =683*811=553913. A väljer s =43215.

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

A väljer r =38177 och räknar $x=38177^2 \pmod{553913}=1457483329 \pmod{553913}=138226$
Om B skickade e =0, returnerar A y=38177. Annars återkommer A $y=38177*43215 \pmod{553913}=1649819055 \pmod {553913}=266141$
Check B : $y^2 \equiv x*v^e \pmod n$

Om e var lika med 0, då bekräftas. $y^2=38177^2\pmod{553913}=1457483329=138266$

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

och bekräftad. $x*v=138226*295502 \pmod {553913}=40846059452 \pmod {553913}=514832$

Litteratur

Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 sid. - ISBN 0-8493-8523-7 .
Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .