Ein einfaches Protokoll basierend auf einer Hashfunktion f wäre:
Challenge-Response Protokoll ≘ Herausforderung- und Antwortprotokoll
Alice |
unsicherer Kanal |
Bob |
|---|---|---|
Gibt Benutzerkennung ID ein |
→ sendet ID |
sucht zu ID Schlüssel K in der Datenbank |
↓ |
||
Gibt Passwort K' ein |
sendet r ← |
wählt zufällige Zahl r |
↓ |
||
berechnet: \(Res'=f(K',r)\) |
→ sendet Res' |
\(f(K,r) ?= Res'\) |
Die Idee ist, dass man jemanden davon überzeugen möchte, dass man eine bestimmte Information hat, ohne diese Information zu offenbaren.
Viele Zero-Knowledge Protokolle basieren darauf, dass man im Prinzip ein Spiel spielt, das man auch zufällig gewinnen kann. Durch die Wiederholung des Spiels wird die Wahrscheinlichkeit jedoch für permanentes zufälliges Gewinnen sehr schnell sehr klein (exponentiell). Somit kann man für praktische Zwecke hinreichend sicher sein, dass der Beweisführende (im Beispiel Peggy) über das Wissen verfügt, das er vorgibt zu besitzen, wenn er immer gewinnt.
Nach 20 Runden ist die Wahreinschlichkeit nur noch \(1/2^{20} = 1/1 048 576\).
Mit 128 Runden erreicht man ein Sicherheitsniveau, das vergleichbar ist mit anderen kryptographischen Verfahren (AES-128, SHA-256, ...).
Voraussetzungen
gegeben zwei zufällige Primzahlen p und q und \(n = p \cdot q\)
Peggys geheimer Schlüssel s wird dann zufällig bestimmt; \(s \in \mathbb{Z}_n^*\) und s coprimal zu n.
Der öffentliche Schlüssel wird dann wie folgt berechnet: \(v = s^{-2} \bmod n\). Der öffentlichen Schlüssel besteht dann aus den zwei Zahlen \(v\) und \(n\).
Protokoll
Peggy berechnet \(x\) unter Verwendung einer beliebigen Zufallszahlen \(r \in \mathbb{Z}_n^*\):
\(x = r^2 \bmod n\)
Peggy sendet die Zahl an Victor.
Victor wählt zufällig ein Bit \(b \in \{0, 1\}\)
Peggy berechnet \(y = r \cdot s^b \bmod n\)
Peggy sendet y an Victor.
Victor testet: \(x \cdot v^{-b} \bmod n \stackrel{?}{=} y^2 \bmod n\)
Beispiel: Fiat-Shamir-Protokoll mit kleinen Zahlen
Zwei Parteien, Peggy (die sich authentifizieren möchte) und Victor (der Prüfer), führen das Fiat-Shamir-Protokoll durch. Verwenden Sie die folgenden Werte:
\(p = 3\), \(q = 7\) → \(n = p \cdot q = 21\)
Peggys geheimer Schlüssel ist \(s = 2\)
Peggy wählt die Zufallszahl \(r = 4\)
Victor wählt die Herausforderung \(b = 1\)
Beantworten Sie folgende Fragen:
Berechnen Sie den öffentlichen Schlüssel v.
Berechnen Sie den Wert x, den Peggy an Victor sendet.
Berechnen Sie die Antwort y, die Peggy an Victor sendet.
Führen Sie die Verifikation als Victor durch