Cryptography Reference
In-Depth Information
Algorithm 15.1
The ElGamal
Sign
algorithm.
(
p, g, x, m
)
k ∈
R
Z
p
r
g
k
(mod
p
)
≡
≡
(
k
−
1
(
h
(
m
)
−
s
xr
)) (mod (
p
−
1))
(
r, s
)
The ElGamal
Sign
algorithm is specified in Algorithm 15.1. It takes as input
a private ElGamal signing key
x
(together with the system parameters
p
and
g
)and
a message
m
, and it generates as output the digital signature for
m
. The digital
signature, in turn, consists of two numbers—
r
and
s
—that are both elements of
Z
p
.
The algorithm consists of three steps:
Z
p
such that
gcd
(
k, p
•
First, a number
k
must be randomly selected from
−
1) =
1.
3
This suggests that
k
has an inverse element
k
−
1
Z
p
(i.e.,
kk
−
1
in
≡
1)), and hence that
k
−
1
1(mod
p
1 can be determined using
the extended Euclid algorithm (i.e., Algorithm 3.2).
−
modulo
p
−
g
k
(mod
p
).
•
Second,
k
must be used to compute
r
≡
•
Third, the message
m
must be hashed with
h
, and the result
h
(
m
) must be
used to compute
s
≡
(
k
−
1
(
h
(
m
)
−
xr
)) (mod (
p
−
1)).
Note that the algorithm can be sped up considerably by using precomputation.
In fact, it is possible to select
k
∈
R
Z
p
and precompute
g
k
(mod
p
)
r
≡
and
k
−
1
(mod
p
−
1)
.
Both values do not depend on a particular message
m
. If one has precomputed
k
,
r
,and
k
−
1
, then one can digitally sign a message
m
by hashing it and computing
s
1)). This can be done very efficiently.
In either case, the ElGamal digital signature for
m
consists of the pair (
r, s
).
Because
m
,
r
,and
s
are all numbers smaller than
p
, an ElGamal digital signature
≡
(
k
−
1
(
h
(
m
)
−
xr
)) (mod (
p
−
As already mentioned in Section 14.2.3.4 and further explained in Section 15.2.2.4, a value
k
must
never be used more than once (otherwise, the system is insecure).
3
