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.

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\le J<n$ als öffentliches Zertifikat und bekommt ein privates Zertifikat $S_{\text{A}}=J^{-s}modn$ 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 $v$ als öffentlicher Schlüssel mit $\mathrm{ggT}(v,\phi (n))=1$
• Eine Zahl $s$ als privater Schlüssel mit $sv=1mod\phi (n)$

Protokollschritte

1. Peggy wählt eine Zufallszahl $r$ mit $1<r<n-1$
2. Peggy berechnet $x=r^{v}modn$
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}modn$
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, 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