Guillou-Quisquater

Das Guillou-Quisquater-Protokoll (Abk.: GQ) ist ein Protokoll aus dem Gebiet der Kryptografie, mit dem man sich jemandem gegenüber authentisieren kann. Das Protokoll wurde von Louis Guillou und Jean-Jacques Quisquater entwickelt und basiert auf dem Problem der Primfaktorzerlegung.

Funktionsweise

Peggy will sich gegenüber Victor authentisieren. Eine vertrauenswürdige dritte Partei stellt ihnen dazu eine Zahl n bereit, die das Produkt zweier großer Primzahlen ist. Die beiden Primzahlen sind geheim und höchstens der dritten Partei selbst bekannt.

Peggy wählt sich eine Zahl J mit $0 \leq J < n$ als öffentliches Zertifikat sowie ein privates Zertifikat $S_{\textrm{A}} = J^{-s}~mod~n$. Peggy will Victor beweisen, dass sie das private Zertifikat besitzt, ohne dass Victor das Zertifikat erhält.

Das Verfahren verwendet folgende Parameter:

• Eine Zahl v als öffentlicher Schlüssel mit $\textrm{gcd}(v, \varphi(n))=1~$
• Eine Zahl s als privater Schlüssel mit $sv = 1~mod~\varphi(n)~$

Protokollschritte

1. Peggy wählt eine Zufallszahl r mit 1 < r < n − 1
2. Peggy berechnet $x=r^v~mod~n$
3. Peggy sendet x und J an Victor
4. Victor wählt eine Zufallszahl d mit 0 < d < v − 1
5. Victor schickt d an Peggy
6. Peggy berechnet einen Zeugen $t = r \cdot S_A^d~mod~n$
7. Peggy sendet den Zeugen t an Victor
8. Victor berechnet $J^d \cdot t^v$ und verifiziert ob das Resultat gleich x ist.

Literatur

• Douglas R. Stinson: Cryptography. Theory and Practice. 3. Auflage. Chapman & Hall/CRC, 2005, ISBN 1-58488-508-4, S. 383–387
• Louis Guillou, Jean-Jacques Quisquater: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Lecture Notes in Computer Science Vol. 330. Advances in Cryptology – EUROCRYPT'88 Proceedings. Springer-Verlag, 1998, ISBN 0-387-50251-3, S. 123–128
• Mihir Bellare, Adriana Palacio: GQ and Schnor identification schemes: proofs of security against impersonation under active and concurrent attacks. In: Lecture Notes in Computer Science Vol. 2442. Advances in Cryptology - CRYPTO 2002 Proceedings. Springer-Verlag, 2002, ISBN 978-3-540-44050-5, S. 149–162