In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm. Its security is based on the intractability of certain discrete logarithm problems. It is considered the simplest digital signature scheme to be provably secure in a random oracle model. It is efficient and generates short signatures. It is covered by Template:US patent, which expired in February 2008.

Algorithm[edit | edit source]

Choosing parameters[edit | edit source]

Key generation[edit | edit source]

  • Choose a private key such that .
  • The public key is where y = gx.

Signing[edit | edit source]

To sign a message M:

  • Choose a random such that
  • Let
  • Let (where || denotes concatenation)
  • Let

The signature is the pair . Note that and ; if a Schnorr group is used and , then the signature can fit into 40 bytes.

Verifying[edit | edit source]

  • Let
  • Let

If then the signature is verified.

Public elements: . Private elements: .

See also[edit | edit source]

References[edit | edit source]

  • C.P. Schnorr, Efficient identification and signatures for smart cards, in G. Brassard, ed. Advances in Cryptology—Crypto '89, 239-252, Springer-Verlag, 1990. Lecture Notes in Computer Science, nr 435
  • Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, J. Cryptology 4(3), pp161–174 (1991) (PS).
  • Menezes, Alfred J. et al. Handbook of Applied Cryptography CRC Press. 1996.

de:Schnorr-Signatur fr:Protocole d'authentification de Schnorr ru:Схема Шнорра

Community content is available under CC-BY-SA unless otherwise noted.