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

Contents

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

Choosing parameters

• All users of the signature scheme agree a group G with generator g of prime order p 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 x such that 0 < x < p
• The public key is y where y = g^x

Signing

To sign a message M:

• Choose a random k such that 0 < k < p
• Let r = g^k
• Let e = H(M | | r)
• Let

The signature is the pair (e,s). Note that and ; if a Schnorr group is used and p < 2¹⁶⁰, 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,p,y,s,e,r. Private elements: k,x.

See also: Topics in cryptography

References

• Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, J. Cryptology 4(3), pp161–174 (1991) (PS).