Cryptography Reference
In-Depth Information
Adversary
Message
M
M
M
,
r
,
s
r
,
s
M
r
,
s
M
Signature
Verification
k
∈
Z
q
r
=
g
k
mod
p
mod
q
s
=
compare
r
and
g
H
(
M
)
s
y
s
mod
p
mod
q
H
(
M
)+
xr
mod
q
k
Secret key
x
Public key
y
y
AUTHENTICATED
g
x
y
=
mod
p
Generator
Figure 10.7.
DSA.
10.3.4 The Digital Signature Standard (DSS)
DSS (as for Digital Signature Standard) was published as Ref. [7] by NIST, a branch
of the American department of commerce, in 1994. It includes a Digital Signature
Algorithm (DSA) which is very similar to the Schnorr signature, which led to a juridical
controversy.
Public parameters
: pick a 160-bit prime number
q
, a large prime number
p
=
1, a generator of
Z
p
aq
+
whose
a
-th power is denoted
g
(an element of
order
q
).
Setup
: pick
x
g
x
∈
Z
q
and compute
y
=
mod
p
.
Secret key
:
K
s
=
x
.
Public key
:
K
p
=
y
.
Signature generation
: pick a random
k
Z
q
, compute
r
(
g
k
∈
=
mod
p
) mod
q
,
H
(
M
)
+
xr
k
and
s
=
mod
q
, the signature is
σ
=
(
r
,
s
).
g
H
(
M
)
mod
p
mod
q
.
mod
q
y
s
mod
q
Verification
: check that
r
=
s
(See Fig. 10.7.) Here
H
is the standardized hash function SHA-1 which hashes onto
160 bits.
The signature is still quite short: 320 bits in total. The main difference with the
Schnorr signature is the removal of the
r
in the message to be hashed. This leads to
a security problem when we know two messages
M
and
M
such that
q
=
H
(
M
)
−
H
(
M
). (See Ref. [180]).
10.3.5
ECDSA
ECDSA (as for Elliptic Curve Digital Signature Algorithm) is yet another variant
of the ElGamal signature. It is dedicated to elliptic curves and is directly adapted
Search WWH ::
Custom Search