6 Altersvergleich

Das folgende Protokoll von Yao beruht auf einem Public-Key-Kryptosystem. Es ermöglicht zwei Personen herauszufinden, wer von beiden älter ist, ohne ihr Alter zu verraten.
Alice sei i, Bob j Jahre alt, außerdem gelte 0 < i, j <= 100.
Alice muß zuvor ihren öffentlichen Schlüssel E_A veröffentlichen.

Das Protokoll lautet:

(i)	Bob wählt zufällig eine große Zahl x, deren Anzahl von Bits zuvor festgelegt wurde (1), und berechnet EA(x) = k. (2)
(ii)	Bob sendet Alice die Zahl k - j. (3)
(iii)	Alice berechnet yu = DA(k - j + u), u = 1,2,...,100. (4) Hierbei muß yu != 0 für alle u gelten; andernfalls muß das Protokoll mit einem neuen x von vorne beginnen. Alice wählt eine große Primzahl p (5), deren Anzahl von Bits ebenfalls vorher festgelegt wurde, und zwar etwas kleiner als die Anzahl der Bits von x. Daraus berechnet Alice zu = yu mod p, u = 1,2,...,100. (6) Es gilt zu < p für alle zu. Falls |zu-zu'| > 1 für u != u' und 0 < zu < p-1, hat Alice ein geeignetes p gewählt, andernfalls muß die Berechnung mit einem anderen p erneut durchgeführt werden.
(iv)	Alice sendet Bob die Folge der Zahlen z1, z2,..., zi, zi+1+1, zi+2+1,..., z100+1, p. (7)
(v)	Bob prüft, ob fj = x mod p für die j-te Zahl fj der Folge gilt. (8) Falls dies der Fall ist, schließt Bob, daß i >= j gilt. Andernfalls gilt i < j.
(vi)	Bob teilt Alice seinen Schluß mit. (9)

Die roten Zahlen geben die Schritte im Beispiel-Applet an. Zur vereinfachten Darstellung ist es nur für Leute zwischen 20 und 30 geeignet.
Als Public-Key-Verfahren wird RSA gewählt (die voreingestellten Parameter können überschrieben werden, werden aber nicht auf Korrektheit geprüft). x hat 12, p hat 11 Bits.

Applet in neuem Fenster starten

7 Das LFKN Protokoll