________________________________________________________________________________
Inhalt....: Fiat-Shamir-Algorithmus
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2003-06-23
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: nextprime, random, powermod, igcd, is
________________________________________________________________________________
Das Fiat-Shamir-"Nullwissen"-Protokoll
Wenn man jemanden davon überzeugen will, dass man ein Geheimnis kennt, dieses aber
nicht preisgeben will, dann benutzt man Nullwissen-Protokolle. In diesem Notebook wird
die Methode von Fiat und Shamir vorgestellt.
Ein Nullwissen-Protokoll hat zwei bedeutende Eigenschaften. Erstens ist es
interaktiv und besteht aus mehreren Runden und zweitens hängt die Betrugs-
wahrscheinlichkeit von der Anzahl der durchgeführten Runden ab. Je mehr
Runden, desto kleiner ist die Wahrscheinlichkeit, betrügen zu können. Die
charakteristischste Eigenschaft ist jedoch die Nullwisseneigenschaft, d.h.
man kann bei Beobachtung des Protokollverlaufs nicht unterscheiden, ob
jemand das Geheimnis kennt oder nicht.
Aber nun genaueres zu dem Fiat-Shamir-Verfahren, welches sich insbesondere
zum Identitätsnachweis mittels Chipkarten eignet. Da der Algorithmus stark auf
RSA beruht, müssen erst einmal Schlüssel erzeugt werden. Dazu werden zwei
große Primzahlen gewählt und das Produkt dieser gebildet:
p := nextprime(2^512);
q := nextprime(p + 2^16);
N := p*q
Nun wird eine beliebige zu N teilerfremde Zahl s zwischen 1 und N gewählt:
s := random(1..N)():
while (igcd(s, N) > 1) do
s := random(1..N)()
end_while:
s
Würden wir hier einen Teiler von N finden, so hätten wir die Primfaktorzerle-
gung von N gefunden und könnten das Protokoll brechen. Die Wahrschein-
lichkeit dafür ist aber sehr gering. Die Zahl s ist das Geheimnis. Jetzt wird
eine Zahl v berechnet, die als eine Art Ausweis fungiert und daher öffentlich
ist.
v := powermod(s, 2, N)
Kommen wir zu der Anwendung: Eine andere Person will jetzt überprüfen,
ob wir das Geheimnis s kennen. Wir werden jedoch nichts von s preisgeben.
Zunächst wählen wir eine weitere zufällige Zahl r, teilerfremd zu N, und be-
stimmen eine Zahl x, die wir an die andere Person schicken:
r := random(1..N)():
while (igcd(r, N) > 1 ) do
r := random(1..N)()
end_while:
r;
x := powermod(r, 2, N)
Die andere Person wählt ein Zufallsbit, also 0 oder 1. Dazu kann sie z.B. eine
Münze werfen. Dieses Bit wird an uns geschickt.
b := random(0..1)()
Nun berechnen wir folgendes:
y := (r * powermod(s, b, N)) mod N
Ist b = 0, so folgt y = r mod N. Wir schicken y wieder zurück. Die andere
Partei muss nachprüfen, ob
Erg1 := powermod(y, 2, N):
Erg2 := (x * powermod(v, b, N)) mod N:
is (Erg1 - Erg2 = 0)
Es stimmt also. Aber warum? Dazu müssen wir uns nur überlegen, wie y, x
und v erzeugt wurden:
Stellen wir uns nun vor, jemand wollte betrügen und der anderen Person weis-
machen, dass er unser Geheimnis kennt. Wie soll dieser Betrüger vorgehen?
Es gibt zwei Möglichkeiten:
1) Wenn ihm das Bit 0 zu geschickt wird, hat er keine Probleme das korrekte y
sszurück zu schicken, da es sich in diesem Fall ja lediglich um das von ihm
ssselbstgewählte r handelt.
2) Ihm wird das Bit 1 zu geschickt. Dann muss er rs modulo N abschicken.
ssDies ist nicht so einfach möglich. Denn
aaEr müsste also die Quadratwurzel modulo N aus vx berechnen. Dies ist aller-
aadings und glücklicherweise bei so großen Zahlen sehr schwer. Was aber,
aawenn er vorher wüsste, dass der Herausforderer ihm eine 1 zuschickt? Dann
aakönnte er sich folgenderweise darauf vorbereiten. Er wählt
aaund
Demnach kann der Betrüger immer nur in einer der beiden Situation betrügen.
Allgemein sieht das Vorgehen folgenderweise aus:
Er wählt zufällig ein Bit c und setzt
Der Herausforderer verifiziert, dann so:
Falls folgende Gleichung gilt, hat der Betrüger es geschafft, zu betrügen:
Demnach kann man nur betrügen, wenn b = c gilt. Dies gilt aber schon mit einer
Wahrscheinlichkeit von 1/2. Daher muss das Protokoll mehrmals durchgeführt
werden, um die Wahrscheinlichkeit zu verringern. Bei t Durchführungen ergibt
sich eine Wahrscheinlichkeit von
_____________________________________________________________________________________
Anmerkungen:
1. Unter www.schule.mupad.de/material/ befinden sich Notebooks, die sich ebenfalls mit Kryptographie
ssbeschäftigen.
2. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe wird eine Vielzahl
ssunterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die Bücher können unter
sswww.schule.mupad.de/literatur kostenfrei kopiert werden.
_____________________________________________________________________________________