PICSI

Algorithme à clé publique: GQ2 (factorisation)

Le schéma GQ2 [1], dû à L. Guillou et J.-J. Quisquater, est un protocole d'authentification de type zero-knowledge à trois passes, dont la sécurité repose sur le problème de la factorisation. Il fait suite au protocole GQ [2], des mêmes inventeurs, qui présente l'avantage d'être basé sur l'identité, mais l'inconvénient de nécessiter des calculs plus lents. Les deux schémas sont décrits dans la norme ISO/IEC 9798-5 [3].

Outre qu'il repose sur le même problème difficile, GQ2 se compare naturellement à RSA en ce que les clés sont semblables. En effet, une clé publique GQ2 est un nombre composé, produit de deux ou trois facteurs premiers qui doivent rester secrets. D'autres entiers entrent en jeu dans ce schéma, mais ils sont de petite taille et peuvent par ailleurs être fixés comme des paramètres du système.

La sécurité de GQ2 est difficile à étudier et est encore aujourd'hui une question partiellement ouverte. Mais pour certains choix de clés et de paramètres, elle peut être réduite au problème de la factorisation, ce qui est un peu mieux que RSA lui-même. Dans ce cas, les facteurs premiers d'un module composé n sont a priori mieux protégés s'ils sont mis en oeuvre dans un protocole GQ2 que dans un protocole RSA.

Par ailleurs, une authentification GQ2 est entre 10 et 40 fois plus rapide qu'une authentification RSA. C'est le grand avantage de cette méthode : elle permet d'authentifier une carte à microprocesseur simple (sans cryptoprocesseur) en moins d'une seconde, sans partager de clé avec cette carte. Et il semble bien qu'elle soit la seule à permettre cela, sauf à recourir à une technique de coupons ou à des mathématiques moins maîtrisées (voir fiches suivantes).

Notons enfin que, comme tous les protocoles d'authentification de cette nature, GQ2 peut facilement être converti en schéma de signature numérique à l'aide de l'heuristique dite de Fiat-Shamir, consistant à simuler les aléas du vérifieur par une fonction de hachage pseudo-aléatoire. Cependant, le temps d'exécution du protocole s'en ressent, car il est très sensible à la taille des (pseudo-)aléas utilisés, laquelle doit être d'au moins 80 bits, sinon 160, dans le cas d'une signature numérique. Les signatures GQ et GQ2 sont sur le point d'être normalisées à l'ISO/IEC [4].





[1] L.C. Guillou and J.-J. Quisquater. Technical report on dynamic authentication comparison of RSA, GQ1 and GQ2. Technical report, France Telecom R&D / University of Louvain, 2001.

[2] L.C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In Proc. of Eurocrypt‘88, LNCS 330, pages 123-128, Springer-Verlag, 1989.

[3] ISO/IEC 9798-5. Information technology – Security techniques – Entity authentication – Part 5 : Mechanisms using zero-knowledge techniques. Publiée le 6 décembre 2004.

[4] ISO/IEC 14888-2. Information technology – Security techniques – Digital signatures with appendix – Part 2 : Integer factorisation based mechanisms. A paraître.