Digital Signature - A Classical Introduction to Cryptography: Applications for Communications Security - page 257

Adversary

Message
M

M

M , e , s

e , s

M

e , s

M

k ∈ Z q
r

Signature Verification

g k mod p
e = H ( M || r )
s = ex + k mod q

=

compare e and
H ( M || g s y − e mod p )

Secret key
x

Public key
y y

AUTHENTICATED

y = g x

mod p Generator

Figure 10.6. Schnorr signature scheme.

10.3.3 Schnorr Signature

In 1989, Claus Schnorr presented a new variant of the ElGamal signature which over-
comes the drawbacks that we have seen: a long signature size and the Bleichenbacher
attack (but this attack was unknown at that time). (See Ref. [160, 161]). Here is a short
description of the Schnorr signature.

Public parameters : pick a (not-too-large, but large enough) prime number q , a large
prime number p 1, a generator of Z p whose a -th power is denoted g

= aq +

(an element of order q ).
Setup : pick x

g x

∈ Z q and compute y = mod p .

Secret key : K s = x .

Public key : K p = y .

Signature generation : pick a random k Z q , compute r g k

∈ = mod p , e =

H ( M || r ), and s = ex + k mod q , the signature is σ = ( e , s ).

g s y − e

Verification : check that e = H ( M || mod p ).

(See Fig. 10.6.) Here H is a hash function (whose output is smaller than the size of q )
and M

||

r denotes the concatenation of M and r .

r ) are pre-
computed. In addition, the size of the signature is a message digest size plus a modulo
q number which can be quite short. We can thus have signatures of size less than
300 bits.

We can see here that the signature complexity is very cheap when ( k ,