GPS (cryptographie)

GPS, abréviation de Girault - Poupard - Stern, est un algorithme d’authentification et de signature numérique à clé publique, basé sur le problème du logarithme discret dans n’importe quel groupe, même d'ordre inconnu. Il a été conçu en 1991 par Marc Girault, et analysé et prouvé sûr en 1998 par Guillaume Poupard et Jacques Stern.

La rapidité de ce protocole le rend accessible à des composants à faible coût, comme une carte à puce sans cryptoprocesseur, qui peuvent s'authentifier/signer en quelques millisecondes, avec une sécurité qui peut être équivalente ou supérieure à celle de RSA.

Lors de la phase d’authentification proprement dite, le calcul se limite à une opération extrêmement simple : $y=a\cdot x-b~$ (opération non modulaire).

Cette prouesse tient dans le fait que la plus grosse partie des calculs peut être effectuée à l’avance et stockée sous forme de coupons. Ainsi même un composant de faible coût peut prouver qu’il n’est ni une contrefaçon, ni un clone, et cela en quelques millisecondes.

Standardisation

• GPS a reçu la labellisation NESSIE (Projet européen d’évaluation de primitives cryptographiques).
• Le schéma d'authentification est normalisé à l'ISO sous ISO/IEC 9798-5 : « Entity authentication – Mechanisms using zero-knowledge techniques »
• Le schéma de signature est normalisé à l'ISO sous ISO/IEC 14888-2 : « Integer factorization based mechanisms »

GPS se décline en plusieurs variantes. L'une d'elles, dont Jean-Claude Paillès^[Qui ?] est co-auteur, permet d'utiliser des clefs de type RSA tout en offrant la même sécurité. Une autre variante fonctionne sur les courbes elliptiques.

Voir aussi

• Digital Signature Algorithm
• Elliptic curve digital signature algorithm