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.

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 session key or nonce $k$ such that $0<k<p$
• Let $r=g^{k}$
• Let $e=H(M||r)$
• Let $s=k-xe{\hbox{mod}}p$

The signature is the pair $(e,s)$. Note that $0\leq e<p$ and $0\leq s<p$; if a Schnorr group is used and $p<2^{160}$, this means that the signature can fit into 40 bytes.

Verifying

• Let $r_{v}=g^{s}y^{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