Schnorr signature

From Free net encyclopedia

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].

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

[edit]

Choosing parameters

All users of the signature scheme agree on 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 on a cryptographic hash function H.

[edit]

Key generation

Choose a private key <math>x</math> such that <math>0<x<p</math>
The public key is <math>y</math> where <math>y=g^x</math>

The public key should be mod p.

[edit]

Signing

To sign a message M:

Choose a random <math>k</math> such that <math>0<k<p</math>
Let <math>r=g^k \quad\hbox{mod}\quad p</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.

[edit]