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;
p:=11; q:=17; n:=p*q;
r:= random(p+1..n-1): s:=r(); // s wird zufällig kleiner n gewählt.
v:=powermod(s,2,n);
Er teilt v und n öffentlich mit und behält s als sein Geheimnis.
v;n; //Antons öffentliche Schlüssel
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
x:=powermod(r,2,n); //A Csendet x an B.
rd:= random(0..1): b:=rd():b; //B sendet 0 oder 1 an A
if b=0 then y:=r else y:=modp(r*s,n)end_if; // A sendet y an B
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;
Mehrere 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]);
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)
