Schnorr signature

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

Schnorr signature is a digital signature produced by the Schnorr signature algorithm. Its security is based on the intractibility 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 {{US patent|4,995,082} which expires in 2008.

1 Choosing parameters
2 Key generation
3 Signing
4 Verifying
5 References
6 External Links

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 a Schnorr group is used.
All users agree on a cryptographic hash function H.

Key generation

Choose a private key $x\,$ such that $0<x<q\,$
The public key is $y\,$ where $y=g^x\,$

Signing

To sign a message M:

Choose a random $k\,$ such that $0<k<q\,$
Let $r=g^k\,$
Let $e=H(M||r)\,$
Let $s=(k-xe) \quad\hbox{mod}\quad q\,$

The 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\,$ .

References

C P Schnoor, 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).