Guillou-Quisquater-Protokoll

Das Guillou-Quisquater-Protokoll (Abkürzung: 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 und dem RSA-Problem.

Funktionsweise

Peggy will sich gegenüber Victor authentisieren. Eine vertrauenswürdige dritte Partei stellt ihnen dazu eine Zahl <math>n</math> 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 <math>J</math> mit <math>0 \leq J < n</math> als öffentliches Zertifikat und bekommt ein privates Zertifikat <math>S_{\text{A}} = J^{-s} \mod n</math> von der vertrauenswürdigen dritten Partei zugeteilt. Peggy will Victor beweisen, dass sie das private Zertifikat besitzt, ohne dass Victor das Zertifikat erhält.

Das Verfahren verwendet folgende Parameter:

• Eine Zahl <math>v</math> als öffentlicher Schlüssel mit <math>\operatorname{ggT}(v, \varphi(n))=1~</math>
• Eine Zahl <math>s</math> als privater Schlüssel mit <math>sv = 1 \mod \varphi(n)~</math>

Protokollschritte

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

Literatur

• Douglas R. Stinson: Cryptography. Theory and Practice. 3. Auflage. Chapman & Hall/CRC, 2005, ISBN 1-58488-508-4, Seiten 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, Seiten 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 Volume 2442. Advances in Cryptology - CRYPTO 2002 Proceedings. Springer-Verlag, 2002, ISBN 978-3-540-44050-5, S. 149–162