PICSI

Algorithme à clé publique: GPS (logarithme discret)

Le schéma GPS [1], d'après M. Girault, G. Poupard et J. Stern, est une variante du schéma de Schnorr, qui généralise le domaine d'application de ce dernier à tout groupe mathématique dans lequel le logarithme discret est réputé difficile. De façon inattendue, cette généralisation facilite encore le calcul de la réponse du prouveur, car la réduction modulaire disparaît. Si cette différence n'a guère de conséquence dans la plupart des environnements, elle prend son importance dans les puces à simple logique câblée telles que celles dont sont pourvues les étiquettes radio-fréquence, où chaque porte logique économisée compte. Le schéma GPS a été labellisé en 1999 par le projet européen NESSIE [2]. Il figure également dans la norme ISO/IEC 9798-5 [3] en tant que protocole d'authentification et dans la future norme ISO/IEC 14888-2 en tant que schéma de signature numérique [4].

Les caractéristiques de GPS dépendent du groupe dans lequel on choisit d'effectuer les calculs. S'il s’agit des entiers non nuls modulo p, p premier, alors ce schéma est très proche de celui de Schnorr. En revanche, si l'on porte son choix sur les entiers inversibles modulo n, n composé, alors il se compare plutôt à GQ2 et à RSA. Il existe même une version, appelée GPS2 dans la norme citée ci-dessus, dans laquelle les clés sont semblables à celles de ces deux autres algorithmes : la clé publique est un nombre composé, produit de deux ou trois facteurs premiers qui doivent rester secrets. Enfin, si l'on décide de travailler sur une courbe elliptique, alors on obtient un schéma particulièrement compact, avec des clés de petite taille.





[1] Girault, G. Poupard and J. Stern. On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order. Journal of Cryptology, Vol. 19, N°4, Springer-Verlag ,pages 463 - 488, Autumn 2006.

[2] https://www.cosic.esat.kuleuven.be/nessie/

[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.