selects a random number z, 1 < z < p  1, which she keeps secret. This is
her private key unknown to anybody. Alice computes the number
y=g"modp (4.5)
and publishes it as her public key. Due to the hardness of discrete logarithm
problem, it is assumed impossible to find x given p and g.
Now Alice is ready to sign messages. Suppose she wants to sign a
message ?i l , . . . ,m n . Describe the steps needed to create a signature.
i
=m
Alice begins with computing a hash function of the message h = h ( f f t ) ,
1 < h < p. Then Alice selects a random number lc (1 < k < p 1)relatively
prime to p  1, and computes
r = g k modp. (4.6)
Then Alice computes
u = ( h  X T ) mod (p  1),
s = k  l u mod (p  1 ) .
Digital Signatures 47
in (4.8) denotes a number satisfying the equality
(Remark that lc'
k  l k mod ( p  1) = 1. (4.9)
Such a k' exists since k and p  1 are coprime, and can be found with the

extended Euclidean algorithm.) Eventually, Alice forms the signed message
s).
( f i ; r, (4.10)
The receiver of the signed message (4.10), first of all, computes again the
hash function h = h ( f i ) . Then he verifies the signature using the equality
(4.11)
yrrs = gh mod p .
If the signature is authentic then (4.11) holds.
Proposition 4.3
Proof. Recall that in all computations the exponents are reduced modulo
p  1. Substitute y and r in Eq. (4.11) by their defining equations (4.5) and
(4.6), and then replace s by (4.8), (4.7):
yrrs = ( g z ) r (g')' = gIT g k ( k  ' ( h   z r ) )

= g I T ghg IT  g h modp.
0
The proof is complete.
Proposition 4.4 The described digital signature satisfies all the require
ments the signature must meet.
Proof. The proof is virtually the same as for RSA signature. First, a
secret number 3 is used in the process of signature generation, moreover,
:
the factor xr in (4.7) changes from message to message since k is selected
at random. Therefore nobody can forge the signature. Second, the hash
function protects from altering signed messages. Third, the author cannot
repudiate the signature as a consequence of the former items. Finally,
everybody who knows the public key y and common parameters p and g
can verify the signature. In case of contention, the court can reproduce all
0
computations.
Example 4.2 Let common parameters for a community of users be p =
23, g = 5. Alice chooses her private key x = 7 and computes her public key
y by (4.5):
y = 5? mod 23 = 17.
Let Alice create the document fii = baaaab and wish to sign it.
Basics of Contemporary Cryptography for IT Practitioners
48
Proceed to signature generation. First of all, Alice computes the hash
function of the message. Let h ( f i ) = 3. Then Alice selects a random
number k , e.g. k = 5. Computations by (4.6), (4.7) give
r = 55 mod 23 = 20,
u = (3  7.20) mod 22 = 17
Then Alice finds k™ mod 22:
k™ mod 22 = 5™ mod 22 = 9 .
Computations by (4.8) give
s = 9 . 1 7 mod 22 = 2 1 .
At last, Alice forms the signed message (4.10) that looks like
(baaaab, 20, 21).
The signed message is transmitted. Bob (or someone else) receives it
and verifies the signature. First, he computes the hash function
h(baaaab) = 3 ,
then he computes the left of (4.11)
1720.2021 mod 23 = 16.15 mod 23 = 10
and the right of (4.11)
53 mod 23 = 1 0 .
Since the results of both computations are the same, Bob concludes that
the signature is valid, i.e. the message is authentic.
The considered digital signature scheme is somewhat more complex than
RSA but its security is based on a different oneway function. It is impor
tant for cryptography because should one system be broken or compro
mised, the other may be used instead. Besides, ElGamal signature is a
basis for a more efficient algorithm in which computation time is substan
tially reduced due to the use of “short” exponents. Such an algorithm is
presented in the following section.
Digital Signatures 49
Digital Signature Standards
4.3
Today, digital signature standards exist in many countries. In this sec
tion, we describe the US standard [FIPS 1862 (2000)l and Russian GOST
R34.1094. Both standards are based on essentially the same algorithm
called DSA (Digital Signature Algorithm) which, in turn, is a variant of
ElGamal signature. We consider in detail an American version of the algo
rithm and then show the distinctive features of the Russian variant.
As a preliminary setup, for a community of users, common open param
eters are to be chosen. First, two prime numbers, q (of length 160 bits) and
p (of length up to 1024 bits) are chosen related by the equation
(4.12)
p=bq+l
for some integer b. The most significant bits in p and q must be 1. Second,
a number a > 1 is chosen such that
aq m o d p = 1 . (4.13)
As a result, we have the three common parameters p, q, and a.
Note that Eq. (4.13) means that, operating modulo p, the exponents of
a are reduced modulo q, i.e.
mod p for all c .
uc mod p = uc mod (4.14)
Indeed, if c = mqtr,where 0 5 r < g, then ac mod p = ( ˜ 9 .armod p =
)˜
lear mod p , see (4.13). This reduction will always be made during signature
generation and verification to ensure that the length of exponents will never
exceed 160 bit, which simplifies computations.
Every user then chooses a random number x satisfying the condition
0 < x < q and computes
y = az modp. (4.15)
The number x will be the private key of the user and the number y the
public key. It is assumed that the public keys for all users are collected in
a nonsecret but “certified” directory which is made available to the whole
community. Note that nowadays it is impossible to find x given y under the
length of p indicated above. This completes the setup stage of the scheme
and now all users are ready to generate and verify signatures.
Let there be given a message f i to be signed. Signature generation is
done as follows.
Basics of Contemporary Cryptography for IT Practitioners
50
1 Compute hash function h = h ( a ) for message m, the hash function value
should lie within the limits 0 < h < q (in American standard, SHA1
hash function [FIPS 1801 (1995)] must be used).
2 Select a random integer k , 0 < k < q.
3 Compute r = (ak mod p ) mod q. If r = 0, revert to Step 2.
4 Compute s = kl(h f xr) mod q. If s = 0, revert to Step 2.
5 Obtain the signed message (a; s).r,
To verify the signature do the following.
6 Compute hash function of the message h = h(m).
7 Verify that 0 < r < q and 0 < s < q.
8 Compute u1 = h . sl mod q, u = r . sl mod q.
2
9 Compute u = (aulyu*mod p ) mod q.
10 Verify that u = r.
If at least one test at Step 7 or 10 fails one should reject the signature.
And vice versa, if all the tests pass, the signature is declared valid.
Proposition 4.5 If the signature on the message was created by a legit
imate user, i.e. by the owner of private key x , then u = r .
Proof. Recall that Eq. (4.14) holds for all exponentials with base a. Since
y defined by Eq. (4.15) is a power of a, Eq. (4.14) also holds for all expo
nentials with y as a base. Now, using the definition of u (Step 9) and
substituting the defining equations for u1, u (Step 8 ) we obtain
2
( )
u = ahS'yrs' mod p mod q . (4.16)
Using the definition of s (Step 4) we can write
+ zr)l mod q .
sl mod q = k ( h (4.17)
Substituting the right of Eq. (4.17) for sl in Eq. (4.16) we obtain
= ( a l r b ( h + z r )  ' a 2 r k ( ˜ + z r )  ' modp modq
)
= (a(h+r"l(h+Zr)k mod p
) mod q
= (ak mod p ) mod q .
Taking into account the definition of r (Step 3) we conclude that =r
21
which completes the proof. 0
Digital Signatures 51
Remark To find an integer a satisfying (4.13) the following method is recom
mended. Select a random integer g > 1 and compute
a = g ( p  ' ) / q mod p . (4.18)
> 1 then it is what we need.
If a Indeed, by (4.18) and Fermat's theorem
= gPl m o d p = 1 ,
mod mod
= g((P')/4)Q
a4
i.e. (4.13) holds. If after computation by (4.18) we obtain a = 1 (extremely
improbable case) then we should try another value of g.
Example 4.3 Choose common parameters
select g = 10 and compute
a = lo6 mod 67 = 25.
Choose a private key x = 6 and compute the corresponding public key
y = 25' mod 67 = 62.
Generate a signature for the message rii = baaaab. Let hash function
h ( f i ) = 3. Select randomly an integer k = 8. Compute
= (258 mod 67) mod 11 = 24 mod 11 = 2 ,
T
mod q = 81 mod 11 = 7 ,
Icl
+ 6 . 2 ) mod 11 = 105 mod 11 = 6 .
s = (7(3
We obtain the signed message
(baaaab; 2, 6).
Now verify the signature. If the message is intact then h = 3. Compute
˜˜modq=6˜rnod11=2,
ul=3.2mod11=6,
= 2 . 2 mod 11 = 4,
'ZLZ
w = (25' . 624 mod 67) mod 11