Cryptography Reference
In-Depth Information
(
g
u
1
y
u
2
(mod
p
)) (mod
q
)
v
≡
The signature is valid if and only if
v
equals
r
. To see why this signature
verification equation works, we start with
s
(
k
−
1
(
h
(
m
)+
xr
)) (mod
q
),and
≡
hence
h
(
m
)
xr
)(mod
q
). If we multiply both sides by
w
and rearrange
the congruence, then we get
wh
(
m
)+
xrw
≡
(
ks
−
≡
k
(mod
q
). This congruence is the
same as
u
1
+
xu
2
≡
k
(mod
q
).Raising
g
to both sides of this congruence yields
(
g
u
1
y
u
2
(mod
p
)) (mod
q
)=(
g
k
(mod
p
)) (mod
q
), and hence,
v
=
r
.
Obviously, it is also possible to represent the verification check in one line. In
this case, the algorithm must verify that the following equation holds:
r
=(
g
h
(
m
)
s
−
1
(mod
q
)
y
rs
−
1
(mod
q
)
(mod
p
)) (mod
q
)
In our toy example, the DSA
Verify
algorithm must first verify 0
<
2
<
11
and 0
<
8
<
11, and then compute
8
−
1
(mod 11) = 7
w
≡
u
1
≡
6
·
7 (mod 11)
≡
42 (mod 11) = 9
u
2
≡
2
·
7 (mod 11)
≡
14 (mod 11) = 3
2
9
8
3
(mod 23) (mod 11)
v
≡
≡
512
·
512 (mod 23) (mod 11) = 2
Consequently, this value of
v
equals
r
, and hence the signature is considered
to be valid.
15.2.3.4
Security Analysis
Because the DSA is a modified version of the ElGamal DSS, most things we said in
Section 15.2.2.4 also apply for the DSA. Similar to the ElGamal DSS, the security of
the DSA relies on the DLA and the DLP in a cyclic group. Contrary to the ElGamal
DSS, however, the DSA relies on the DLP in a cyclic subgroup of
Z
p
with prime
order
q
. This problem can only be solved by using a generic algorithm. As mentioned
in Section 7.4, the best we can expect from such a generic algorithm is a running time
that is of the order of the square root of the order of the subgroup. If, for example,
the subgroup has the order 2
160
(as in the case of the DSA), then the best we can
expect from an algorithm to compute discrete logarithms is a running time that is of
the order of
√
2
160
=2
160
/
2
=2
80
.
