Cryptography Reference
In-Depth Information
5.4
Fiat-Shamir-Authentifikation
Ziel dieses Protokolls ist, dass eine Partei, z.B. A (Alice) gegenüber einer anderen Partei, z.B.
B (Bob) ihre Identität nachweist. Die Initiative geht hier von Alice aus. Bob nimmt die Rolle
eines Verifizierenden ein. Das Verfahren arbeitet mit
Protokoll-Runden
. In jeder Runde wird
die Authentizität von Alice nur mit Wahrscheinlichkeit geprüft. Mit zunehmender Zahl von
Runden gewinnt der verifizierende Bob zunehmende Sicherheit über die Authentizität von
Alice.
Das Protokoll wurde 1986 von A. Fiat und A. Shamir vorgeschlagen [FS86]. Auf den ersten
Blick erscheint das Protokoll kompliziert und durch Mangel an Sicherheit behaftet. Bei einer
Anzahl von 20 bis 30 Runden ist die Wahrscheinlichkeit, dass der Verifizierende sich täuscht,
jedoch vernachlässigbar klein. Der Vorteil des Fiat-Shamir-Protokolls liegt in dem geringen
Rechenaufwand je Runde. Deshalb wird es praktisch eingesetzt, wenn einfache Chipkarten an
dem Protokoll beteiligt sind.
Mathematisch basiert das Fiat-Shamir-Protokoll auf der Schwierigkeit, Quadratwurzeln mod n
zu lösen, wenn der Modul n=p·q aus zwei Primfaktoren besteht, die einem Angreifer nicht
bekannt sind (Kap. 4.1.5).
5.4.1
Vertrauenswürdige Schlüsselbank
Die Schlüsselbank wählt zufallsmäßig zwei verschiedene Primzahlen p und q und berechnet
den Modul n. Für die Stellenlänge von n gelten die gleichen Gesichtspunkte wie für RSA.
npq
pq
(5.4-1)
Der Modul n gilt für viele Teilnehmer und ist öffentlich. Die Primfaktoren sind Geheimnis der
Bank. Sie können so festgelegt werden, dass die Berechnung von Quadratwurzeln für die Bank
besonders einfach ist.
Für jeden Teilnehmer (z.B. A) und seine Identitätsbeschreibung ID
A
wählt die Bank eine Zu-
fallszahl z
A
und berechnet einen Hash-Wert.
v (ID, z)
(5.4-2)
A
A
A
Aus dem Hash-Wert v
A
berechnet die Bank den geheimen und privaten Schlüssel s
A
mittels
sv1(m d )
2
w.
s (
v) m dn
1
(5.4-3)
AA
A
A
Nicht zu jedem Wert von v
A
gibt es ein multiplikativ inverses Element und insbesondere exis-
tieren nicht zu jedem Wert von v
A
1
Quadratwurzeln. Durch die Wahl der Zufallszahl z
A
kön-
nen die Bedingungen jedoch erfüllt werden. Die Berechnung der Quadratwurzel kann die Bank
leicht durchführen, weil sie die Primfaktoren von n kennt (Kap. 4.1.5).
Der private und der zugehörige öffentliche Schlüssel sind dann:
privater (geheimer) Schlüssel :
s
A
(5.4-4)
öffentlicher Schlüssel :
n, ID
, z
, v
h(ID
, z
)
AA A
AA
