Schnorr signature
|
|
A Schnorr signature is a digital signature scheme based on discrete logarithms. It is considered the simplest such scheme to be provably secure in a random oracle model. It is efficient and generates short signatures. It is covered by US patent #4,995,082, which expires in 2008 [1] (http://patft.uspto.gov/netacgi/nph-Parser?u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=1&l=50&f=G&d=PALL&s1=4995082.WKU.&OS=PN/4995082&RS=PN/4995082).
| Contents |
Choosing parameters
- All users of the signature scheme agree a group <math>G<math> with generator <math>g<math> of prime order <math>p<math> in which the discrete log problem is hard. Typically a Schnorr group is used.
- All users agree a cryptographic hash function H.
Key generation
- Choose a private key <math>x<math> such that <math>0
- The public key is <math>y<math> where <math>y=g^x<math>
Signing
To sign a message M:
- Choose a random <math>k<math> such that <math>0
- Let <math>r=g^k<math>
- Let <math>e=H(M||r)<math>
- Let <math>s=(k-xe) \quad\hbox{mod}\quad p<math>
The signature is the pair <math>(e,s)<math>. Note that <math>0 \le e < p<math> and <math>0 \le s < p<math>; if a Schnorr group is used and <math>p < 2^{160}<math>, this means that the signature can fit into 40 bytes.
Verifying
- Let <math>r_v=g^sy^e<math>
- Let <math>e_v=H(M||r_v)<math>
If <math>e_v=e<math> then the signature is verified.
Public elements: <math>G,g,p,y,s,e,r<math>. Private elements: <math>k,x<math>.
See also: Topics in cryptography
References
- Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, J. Cryptology 4(3), pp161–174 (1991) (PS) (http://www.mi.informatik.uni-frankfurt.de/research/papers/schnorr.smartcardsig.1991.ps).