Cryptography Reference
In-Depth Information
=
k
−
1
(
h
(
m
2
)
s
2
−
xr
)) (mod(
p
−
1))
If
k
is the same, then
r
≡
g
k
(mod
p
) is also the same for both signatures.
Consequently, one has
(
k
−
1
(
h
(
m
1
)
k
−
1
(
h
(
m
2
)
s
1
−
s
2
≡
−
xr
)
−
−
xr
)) (mod(
p
−
1))
(
k
−
1
h
(
m
1
)
k
−
1
xr
k
−
1
h
(
m
2
)+
k
−
1
xr
)(mod(
p
≡
−
−
−
1))
(
k
−
1
h
(
m
1
)
k
−
1
h
(
m
2
)) (mod(
p
≡
−
−
1))
(
k
−
1
(
h
(
m
1
)
≡
−
h
(
m
2
))) (mod(
p
−
1))
.
1, then one can compute
k
.
Furthermore, given
k
,
s
1
,
r
,and
h
(
m
1
), one can retrieve the private key
x
.Note
that
s
1
≡
If
h
(
m
1
)
−
h
(
m
2
) is invertible modulo
p
−
(
k
−
1
(
h
(
m
1
)
−
xr
)) (mod (
p
−
1)), and hence
(
r
−
1
(
h
(
m
1
)
x
≡
−
ks
1
)) (mod (
p
−
1))
.
This is unfortunate, and we stress the requirement that a fresh and unique
k
is
randomly chosen from
Z
p
for every ElGamal signature that is generated.
15.2.3
DSA
In the early 1990s, Claus-Peter Schnorr proposed a modification of the basic El-
Gamal DSS that can be used to optimize the signature generation and signature
verification algorithms considerably [12]. The idea is to do the modular arithmetic
not in a group of order
p
−
Z
p
), but in a much smaller subgroup of prime order
1 (e.g.,
q
with
q
|
p
−
1. As a consequence, the computations can be done more efficiently
and the resulting digital signatures can be made much shorter (as compared to the
basic ElGamal DSS).
Based on the ElGamal DSS and the proposed modification of Schnorr, the
NIST developed the
digital signature algorithm
(DSA) and specified a correspond-
ing
digital signature standard
in FIPS PUB 186 [13]. Since its publication in 1994,
FIPS PUB 186 has been revised twice.
5
The acronym ECDSA refers to the elliptic
curve analog of the DSA. That is, instead of working in a subgroup of
Z
p
, one
works in a group of points on an elliptic curve over a finite field (see Section 7.6).
5
The first revision was made in December 1998 and led to the publication of FIPS PUB 186-
1. The second and latest revision was made in January 2000 and led to the publication of FIPS
PUB 186-2. It is electronically available at http://csrc.nist.gov/publications/fips/fips186-2/fips186-
2-change1.pdf.
