# Schnorr signature

566pages on
this wiki

In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm. Its security is based on the intractability 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 Template:US patent, which expired in February 2008.

## AlgorithmEdit

### Choosing parametersEdit

• 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 generationEdit

• Choose a private key $x$ such that $0.
• The public key is $y$ where y = gx.

### SigningEdit

To sign a message M:

• Choose a random $k$ such that $0
• Let $r=g^k\,$
• Let $e=H(M||r),\,$ (where || denotes concatenation)
• Let $s=(k-xe) \;\text{mod } 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}$, then the signature can fit into 40 bytes.

### VerifyingEdit

• 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$.