Schnorr signature

The Schnorr signature is a 1989/91 by the German Mathematics Professor Claus -Peter Schnorr designed cryptographic digital signature scheme. It is derived from the Schnorr identification by the interaction is replaced by the use of a cryptographic hash function as in the Fiat-Shamir identification. The security is based on the complexity of the discrete logarithm in finite groups.

The process is patented by Schnorr, the term of protection, however, is now expired. It is exclusive to BSA licensed (Siemens but has a non-exclusive license). Schnorr accused in the IEEE P1363 standardization of NIST, short- DSA to hurt with the developed her signature process Digital Signature Algorithm his patent.

Parameter

System -wide parameters

All users can use this parameter in common:

• A group of prime order. This is cyclical, is a generator
• A cryptographic hash function with range of values.

Schnorr proposes to select a subset of primes for a. He argues that key and signature lengths relate to the safety level on the other hand is based on the larger ones.

Private key

The private key is a random number:

• With

Public key

The public key is the corresponding group element:

Signing

To sign a message, proceed as follows:

The signature of the message is the tuple.

Verify

To verify a signature of a message, proceed as follows:

Security discussion ( informal)

The security of the Schnorr signature must be reduced in the random oracle model, provably on the complexity of the discrete logarithm in the group used, that is, who breaks the Schnorr signature scheme efficient, can also efficiently compute the discrete logarithm. There is no known method by which the discrete logarithm in multiplicative groups of finite fields can be calculated efficiently with today's computers. ( Although there is for the calculation of quantum computers (theoretically) efficient Shor algorithm, the necessary quantum computers but not with the required bit length in the foreseeable future realizable. ) This demonstrable reduction to known, classified as difficult problems is typical of security proofs in cryptographic public key systems.

In the random oracle model one assumes that the hash function as a random function, and an attacker can behave the function values ​​are calculated only on an oracle for the function values ​​. Using a proof by contradiction we now show the correctness of the procedure. Suppose there were a successful signature forgery for the signature scheme. This possibility can be used to determine from the public key the secret key, ie to compute the discrete logarithm of - in contradiction to the assumption that the discrete logarithm is difficult.

The division by is possible: Since is prime, there exists at any number other than 0 also has an inverse modulo.