title: Guillou-Quisquater
text: # Guillou-Quisquater
  
  Le protocole de Guillou-Quisquater ou GQ est une preuve à divulgation nulle de connaissance proposée par Louis Guillou et Jean-Jacques Quisquater pour prouver la connaissance d'un message clair RSA pour un chiffré public. Cette preuve peut-être dérivée en protocole d'authentification par l'heuristique de Fiat-Shamir.
  
  ## Fonctionnement
  
  Alice veut s'authentifier auprès de Bob. Elle est en possession d'un certificat public $J_{\textrm {A}}~$ ainsi que d'un certificat privé $S_{\textrm {A}}=J_{\textrm {A}}^{-s}~mod~n$. Le but est de prouver la possession du certificat privé.
  
  La signature se fait grâce aux paramètres suivants :
  
  * $n=pq~$, de la même manière que dans RSA
  * un nombre $v~$ qui sert de clé publique tel que ${\textrm {gcd}}(v,\varphi (n))=1~$
  * un nombre $s~$ qui sert de clé privée tel que $sv=1~mod~\varphi (n)~$
  
  ### Étapes
  
  Le schéma d'identification est construit comme un protocole Σ en trois parties :
  
  * L'engagement :
     * Alice choisit un nombre aléatoire $r~$
     * Alice calcule $x=r^{v}~mod~n$
     * Alice envoie $x~$ et $J_{\textrm {A}}~$ à Bob
  * Le défi :
     * Bob choisit un nombre aléatoire $e~$ tel que $1\leq e\leq v$
     * Bob envoie $e~$ à Alice
  * La réponse :
     * Alice calcule $y=rS_{\textrm {A}}^{e}~mod~n$ et l'envoie à Bob
     * Bob calcule $J_{\textrm {A}}^{e}y^{v}$ et vérifie que le résultat est égal à $x~$ et différent de 0.
  