Cryptography Reference
In-Depth Information
w
i
<
2
l
(for a suitable small value of
l
, they suggest
l
Laih choose 1
≤
=
15) and verify
the batch by testing
s
0
,i
∈
g
,0
≤
s
2
,i
<r
and
t
t
g
t
i
=
1
w
i
s
2
h
w
i
H
(
m
i
s
0
,i
)
i
s
w
i
0
,i
=
.
i
=
1
i
=
1
Give the verification algorithm when the public keys are all equal. Show that the cost is
roughly
l/
(3 log
2
(
r
)) times the cost of verifying
t
Elgamal signatures individually.
Explain why it seems impossible to verify batches of Schnorr signatures faster than
verifying each individually.
22.2.2 DSA
A slight variant of the Elgamal signature scheme was standardised by NIST
4
as a digital
signature standard. This is often called
DSA
.
5
In the case where the group
G
is an elliptic
curve then the scheme is often called
ECDSA
.
In brief, the scheme has the usual public key
h
g
a
where
g
is an element of prime order
=
r
in an algebraic group
G
and 1
≤
a<r
is chosen uniformly at random. As with Elgamal
signatures, a function
F
:
G
→ Z
/r
Z
is required. To sign a message with hash value
F
(
g
k
). If
s
1
=
0 then repeat
6
H
(
m
) one chooses a random 1
≤
k<r
and computes
s
1
=
k
−
1
(
H
(
m
)
for a different value of
k
. Then compute
s
2
=
0
then repeat for a different value of
k
. The signature on message
m
is (
s
1
,
s
2
). To verify
the signature one first checks that 1
+
a
s
1
)(mod
r
) and, if
s
2
=
H
(
m
)
s
−
1
2
≤
s
1
,
s
2
<r
, then computes
u
1
=
(mod
r
),
s
1
s
−
1
2
u
2
=
(mod
r
), then determines whether or not
F
(
g
u
1
h
u
2
)
.
s
1
=
(22.4)
Note that a DSA signature is a pair of integers modulo
r
so is shorter in general than an
Elgamal signature but longer in general than a Schnorr signature. Verification is performed
using multi-exponentiation.
Exercise 22.2.9
Show that Verify succeeds on values output by Sign.
Exercise 22.2.10
The case
s
1
=
0 is prohibited in DSA signatures. Show that if this check
was omitted and if an adversary could find an integer
k
such that
F
(
g
k
)
=
0 then the adver-
sary could forge DSA signatures for any message. Hence, show that, as in Exercise
22.2.6
,
an adversary who maliciously chooses the system parameters could forge signatures for
any message and any public key.
Exercise 22.2.11
The case
s
2
=
0 is prohibited in DSA signatures since the Verify algo-
rithm fails when
s
2
is not invertible. Show that if a signer outputs a signature (
s
1
,
s
2
)
4
NIST stands for “National Institute of Standards and Technology” and is an agency that develops technology standards for the
USA.
5
DSA stands for “digital signature algorithm”.
6
The events
s
1
=
0and
s
2
=
0 occur with negligible probability and so do not effect the performance of the signing algorithm.
