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.
AlgorithmEdit
Choosing parametersEdit
 All users of the signature scheme agree on a group with generator of prime order in which the discrete log problem is hard. Typically a Schnorr group is used.
 All users agree on a cryptographic hash function H.
Key generationEdit
 Choose a private key such that .
 The public key is where y = g^{x}.
SigningEdit
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.
VerifyingEdit
 Let
 Let
If then the signature is verified.
Public elements: . Private elements: .
See alsoEdit
ReferencesEdit
 C.P. Schnorr, Efficient identification and signatures for smart cards, in G. Brassard, ed. Advances in Cryptology—Crypto '89, 239252, SpringerVerlag, 1990. Lecture Notes in Computer Science, nr 435
 ClausPeter 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.
