- Schnorr signature
In
cryptography , a Schnorr signature is adigital signature produced by the Schnorr signature algorithm. Its security is based on the intractability of certaindiscrete logarithm problems. It is considered the simplest digital signature scheme to be provably secure in arandom oracle model. It is efficient and generates short signatures. It is covered by US patent|4995082, which expired in February 2008.Algorithm
Choosing parameters
*All users of the signature scheme agree on a group G with generator g of prime order q in which the
discrete log problem is hard. Typically aSchnorr group is used.
*All users agree on acryptographic hash function H.Key generation
*Choose a private key x such that 0
.
*The public key is y where "y" = "g"x.igning
To sign a message M:
*Choose a random k such that 0
*Let r=g^k
*Let e=H(M||r)
*Let s=(k-xe) quadhbox{mod}quad qThe signature is the pair e,s). Note that 0 le e < q and 0 le s < q; if a Schnorr group is used and q < 2^{160}, this means that the signature can fit into 40 bytes.
Verifying
*Let r_v=g^sy^e
*Let e_v=H(M||r_v)If e_v=e then the signature is verified.
Public elements: G,g,q,y,s,e,r.Private elements: k,x.
"See also:"
Topics in cryptography References
* 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) [http://www.mi.informatik.uni-frankfurt.de/research/papers/schnorr.smartcardsig.1991.ps (PS)] .
Wikimedia Foundation. 2010.