Fiat-Shamir-Verfahren, Zero-Knowledge-Protokoll

Kryptographie mit MuPAD,

Prof. Dr.Dörte Haftendorn, Okt.99, Nov 02 05    Update Juni 07

-----------------------------------------------------------------------------------

Anton will Berta davon überzeugen, dass er ein Geheimnis s kennt,

ohne dass Berta irgendetwas von dem Geheimnis erfährt.

Schlüsselerzeugung:

Anton wählt zwei große Primzahlen p und q  und bildet ihr Produkt n.

//p:=numlib::prevprime(floor(sqrt(5*10^50)));

//q:=numlib::prevprime(floor(sqrt(29*10^50)));  // Exponent etwa 200 statt 50

//n:=p*q;

image

p:=11;  q:=17;  n:=p*q;

math

math

math

r:= random(p+1..n-1): s:=r(); // s wird zufällig kleiner n gewählt.

v:=powermod(s,2,n);

 

math

math

imageEr teilt v und n öffentlich mit und behält s als  sein Geheimnis.

v;n;  //Antons öffentliche Schlüssel

math

math

Anwendungsphase

Anton wählt r teilerfremd zu n und berechnet x

repeat 

rd:= random(2..n-1): r:=rd(): 

  until gcd(n,r)=1 end_repeat:r;   // r zufällig gewählt

 

math

x:=powermod(r,2,n); //A Csendet x an B.

math

image

rd:= random(0..1): b:=rd():b;  //B sendet 0 oder 1 an A

 

math

if b=0 then y:=r else y:=modp(r*s,n)end_if; // A sendet y an B

math

image

test:=powermod(y,2,n);

if b=0 then if test=x then erg:="ok": else erg:="Quark": end_if:

    else if test=modp(x*v,n) then erg:="ok": else erg:="Quark": end_if:

end_if:

erg;

math

math

imageMehrere Durchläufe, das Fiat-Shamir Verfahren ist ein "Challenge and response" verfahren (Anfrage und Antwort), das  bei k Anfragen, die zu "ok" führten, eine Irrtumswahrscheinlichkeit von

2^(-k) hat, für die Hypothese: Anton kennt das Geheimnis.

teste:=proc()

local rd,r,x,test,b,y,erg;

         begin

repeat 

  rd:= random(2..n): r:=rd(): 

  until gcd(n,r)=1 end_repeat:r;

x:=powermod(r,2,n); //A sendet x an B.

rd:= random(0..1): b:=rd():b;  //B sendet 0 oder 1 an A

y:=modp(r*s^b,n); // A sendet y an B

test:=powermod(y,2,n);

         if test=modp(x*v^b,n) then erg:="ok" else erg:="Quark": end_if:

        return ([b,test,modp(x*v^b,n),erg]);

   end_proc:

matrix([teste() $ i=1..10]);

math

testen:=proc(k)

         local i, rd,r,x,test,b,y,fehler;

begin

         fehler:=0;

         for i from 1 to k do

          repeat 

    rd:= random(2..n): r:=rd(): 

    until gcd(n,r)=1 end_repeat:r;

  x:=powermod(r,2,n); //A sendet x an B.

          rd:= random(0..1): b:=rd():b;  //B sendet 0 oder 1 an A

  y:=modp(r*s^b,n); // A sendet y an B

  test:=powermod(y,2,n);

          if test <> modp(x*v^b,n) then fehler:=fehler+1 end_if:

         end_for;

         return (k, " Anfragen, Fehlerzahl = ", fehler );

end_proc:

testen(300)

math