Cryptography Reference
In-Depth Information
q
th power. Since
g
q
(
−
)/
=
is raised to the
1, the order of the element
g
thus
obtained divides
q
by Proposition 2.4 and one only has to ensure that
g
p
1
=
1for
g
to
have order
q
.
Given these parameters, the DSA algorithm may be described as follows:
Definition 9.6
The digital signature algorithm is defined as the signature scheme
DSA
=
(
Gen
DSA
,
Sign
DSA
,
Ve r
DSA
),
with the following algorithms:
•
Gen
DSA
: On input the system parameters
(
p
,
q
,
g
)
, pick a (pseudo-) random
g
x
mod
p
∈ Z
p
. Output
x
← Z
q
and compute
y
:=
(
x
,
y
)
, where
x
is the
private key and
y
is the public key.
}
∗
, proceed as follows:
•
Sign
DSA
: On input a private key
x
∈ Z
q
and
m
∈{
0
,
1
- Choose
k
←[
1
,
q
−
1
]
.
g
k
mod
p
- Compute
r
:=
(
)
mod
q
.
- Compute
z
:=
H
(
m
)
.
k
−
1
- Compute
s
:=
(
z
+
xr
)
mod
q
.
(
,
)
=
=
The signature of
m
is the pair
0, a new value
of
k
is generated and the signature is recalculated (this occurs with very small
probability).
r
s
. If either
r
0or
s
∈ Z
p
and a signed message
•
Ve r
DSA
: On input a public key
y
(
m
,
r
,
s
)
, proceed as
follows:
- Check that 0
<
r
<
q
and 0
<
s
<
q
. If either of these conditions does not
hold then output 0.
- If the previous conditions hold, compute:
w
s
−
1
mod
q
.
:=
z
:=
H
(
m
)
.
s
−
1
u
1
:=
wz
mod
q
=
·
z
mod
q
.
u
2
:=
wr
mod
q
.
g
u
1
y
u
2
mod
p
v
:=
(
)
mod
q
.
-If
v
=
r
then output 1, otherwise output 0.
Remarks 9.2
1. In our definition of digital signature scheme (Definition 9.1) there were no
domain parameters (or, rather, they were regarded as belonging to the public
key). For Definition 9.6 to conform to the more general Definition 9.1, these
parameters should be generated by the key generation algorithm and included
in the public key.
2. In [75] the output length of the hash function
H
is allowed to be different from
N
and, if this length is greater than
N
, then the value
z
in the above definition is
the one defined by the
N
leftmost bits of
H
(
m
)
. However, using a hash function
