Cryptography Reference
In-Depth Information
Zunächst wird bewiesen, dass die Kongruenzen von (5.4-7) erfüllt sein müssen, indem (5.4-5)
und (5.4-3) in (5.4-6) eingesetzt werden:
2
2
2
fürdenF lb1:
y r ) xs x/v(modn)
(5.4-8)
2
2
für den Fall b
0 :
y
r
x
(mod n)
Das Ergebnis in (5.4-8) zeigt Übereinstimmung mit den Kongruenzen in (5.4-7).
In Abb. 5-5 ist der Ablauf für das Fiat-Shamir-Protokoll dargestellt. Oben im Bild steht der
Beitrag der Schlüsselbank und darunter der Kenntnisstand von Alice und Bob. Mit ihrem Ge-
heimnis s
A
kann Alice sich gegenüber Bob authentisieren, der ihren öffentlichen Schlüssel v
A
kennt. Der Protokollablauf zeigt eine Authentifikationsrunde.
Die Fiat-Shamir-Authentifikation wirkt tatsächlich etwas kompliziert. Der Zusammenstellung
in Abb. 5-5 ist jedoch zu entnehmen, dass in jeder Runde nur wenige Multiplikationen durch-
geführt werden müssen. Auch bei 20 oder 30 Runden ist der Rechenaufwand deutlich geringer
als eine Potenzierung mit Operanden, die z.B. 1024 Bit lang sind.
Schlüssel-Bank
wählt zwei ungleiche Primzahlen p und q, n=p*q, wählt Hashfunktion h(.),
p und q sind Geheimnis der Schlüsselbank, n ist öffentlich bekannt
wählt für jeden Teilnehmer (ID, z)
und berechnet s aus s*v=1(mod n) und v=h(ID, z),
s ist privater (geheimer) Schlüssel des Teilnehmers,
(ID, z) bzw. v=h(ID, z) ist öffentlicher Schlüssel eines Teilnehmers
2
kennt von A
öffentlichen Schlüssel v
A
besitzt ihren
privaten Schlüssel s
A
Alice
Bob
wählt Zufallszahl r,
r teilerfremd zu n,
berechnet x=(r)mod n
x
2
wählt Zufalls-Bit b
b
berechnet
b=1: y=(r*s)mod n
b=0: y=(r) mod n
prüft
b=1: y=x/v (mod n)
b=0: y=x (mod n)
y
2
2
Abb. 5-5: Fiat-Shamir-Protokoll. Alice authentisiert sich gegenüber dem verifizierenden Bob.
Das Bild zeigt eine Authentifikations-Runde.
