Guillou-Quisquater-Protokoll

Das Guillou-Quisquater-Protokoll (Abkürzung: GQ) i​st ein Protokoll a​us dem Gebiet d​er Kryptografie, m​it dem m​an sich jemandem gegenüber authentisieren kann. Das Protokoll w​urde von Louis Guillou u​nd Jean-Jacques Quisquater entwickelt u​nd basiert a​uf dem Problem d​er Primfaktorzerlegung.

Funktionsweise

Peggy will sich gegenüber Victor authentisieren. Eine vertrauenswürdige dritte Partei stellt ihnen dazu eine Zahl ${\displaystyle 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 ${\displaystyle J}$ mit ${\displaystyle 0\leq J<n}$ als öffentliches Zertifikat und bekommt ein privates Zertifikat ${\displaystyle S_{\text{A}}=J^{-s}\mod n}$ 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 ${\displaystyle v}$ als öffentlicher Schlüssel mit ${\displaystyle \operatorname {ggT} (v,\varphi (n))=1~}$
• Eine Zahl ${\displaystyle s}$ als privater Schlüssel mit ${\displaystyle sv=1\mod \varphi (n)~}$

Protokollschritte

1. Peggy wählt eine Zufallszahl ${\displaystyle r}$ mit ${\displaystyle 1<r<n-1}$
2. Peggy berechnet ${\displaystyle x=r^{v}\mod n}$
3. Peggy sendet ${\displaystyle x}$ und ${\displaystyle J}$ an Victor
4. Victor wählt eine Zufallszahl ${\displaystyle d}$ mit ${\displaystyle 0<d<v-1}$
5. Victor schickt ${\displaystyle d}$ an Peggy
6. Peggy berechnet einen Zeugen ${\displaystyle t=r\cdot S_{A}^{d}\mod n}$
7. Peggy sendet den Zeugen ${\displaystyle t}$ an Victor
8. Victor berechnet ${\displaystyle J^{d}\cdot t^{v}}$ und verifiziert ob das Resultat gleich ${\displaystyle 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