Guillou-Quisquater-Protokoll
# 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\leq J<n$ als öffentliches Zertifikat und bekommt ein privates Zertifikat $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 $v$ als öffentlicher Schlüssel mit $\operatorname {ggT} (v,\varphi (n))=1~$
* Eine Zahl $s$ als privater Schlüssel mit $sv=1\mod \varphi (n)~$

### Protokollschritte

* Peggy wählt eine Zufallszahl $r$ mit $1<r<n-1$
* Peggy berechnet $x=r^{v}\mod n$
* Peggy sendet $x$ und $J$ an Victor
* Victor wählt eine Zufallszahl $d$ mit $0<d<v-1$
* Victor schickt $d$ an Peggy
* Peggy berechnet einen Zeugen $t=r\cdot S_{A}^{d}\mod n$
* Peggy sendet den Zeugen $t$ an Victor
* Victor berechnet $J^{d}\cdot t^{v}$ und verifiziert ob das Resultat gleich $x$ ist.
