Schnorr
Le schéma de Schnorr (du mathématicien allemand Claus-Peter Schnorr) est un protocole d'authentification de type zero-knowledge à trois passes, dont la sécurité repose sur le problème du logarithme discret. Une particularité importante de ce schéma est que les tailles de la clé privée et des valeurs transmises par le prouveur sont réduites à leur minimum. L'astuce utilisée pour y parvenir sera reprise par le NIST, lorsqu'il spécifiera le standard fédéral DSA (Digital Signature Algorithm). Le schéma de Schnorr est décrit dans la norme ISO/IEC 9798-5, tandis que le DSA est en cours de normalisation [3].
Dans le schéma de Schnorr, la clé privée est le logarithme discret de la clé publique, et ne peut donc en être déduite si les paramètres sont assez grands. A priori, il ne s'agit pas de cryptographie à bas coût, car le prouveur doit calculer une nouvelle exponentielle à chaque authentification. Cependant, ce calcul ayant lieu au tout début du protocole, il peut être effectué à l'avance et son résultat stocké en mémoire en attendant l'interaction. On parle alors de “précalcul” ou de “coupon”. Quand vient l'authentification proprement dite, le prouveur n'a plus qu'à transmettre un coupon non encore utilisé, recevoir le défi du vérificateur, calculer la réponse et le lui transmettre. Le calcul de la réponse est, lui, élémentaire.
Comme GQ2 et tous les protocoles d'authentification de cette nature, le schéma de Schnorr peut facilement être converti en schéma de signature numérique à l'aide de l'heuristique de Fiat-Shamir. Si le temps d'exécution global du protocole s'en ressent, le recours aux coupons permet néanmoins au signataire de produire sa signature en un temps défiant (presque) toute concurrence.
Généralités:
- C.P. Schnorr. Efficient signature generation by smart cards. In Journal of Cryptology, Vol. 4, n° 3, pages 161-174, 1991.
- ISO/IEC 9798-5. Information technology – Security techniques – Entity authentication – Part 5 : Mechanisms using zero-knowledge techniques. Publiée le 6 décembre 2004.
- ISO/IEC 14888-2. Information technology – Security techniques – Digital signatures with appendix – Part 3 : Discrete logarithm based mechanisms.
Signature Schnorr:
- Patent: Method for identifying subscribers and for generating and verifying … Claus P. Schnorr: http://www.google.com/patents?vid=4995082
- Review of Schnorr Signature: http://www.cs.utexas.edu/~rashid/395Tcrypt/6_2.pdf