Cryptography Reference
In-Depth Information
The ECDSA is being standardized within the ANSI X9F1 and IEEE P1363. Also,
in the latest revision of FIPS PUB 186, a couple of elliptic curves are recommended
for governmental use.
15.2.3.1
Key Generation Algorithm
The DSA
Generate
algorithm takes as input a security parameter and generates as
output a private DSA signing key and a corresponding public DSA verification key.
In a first step, the algorithm determines two prime moduli:
•
A prime modulus
p
that is 512 + 64
t
bits long (for
t
∈{
0
,...,
8
}
);
•
A prime modulus
q
that divides
p
−
1 and that is 160 bits long (i.e., 2
159
<
q<
2
160
).
Z
p
has a subgroup
Note that the requirement that
q
divides
p
−
1 implies that
of order
q
(i.e., the subgroup has approximately 2
160
elements). Such a subgroup
Z
p
can be determined by using a positive integer
h
with 1
<h<p
of
−
1 and
h
(
p−
1)
/q
(mod
p
)
>
1, and computing a generator
g
of a subgroup of order
q
as
follows:
h
(
p−
1)
/q
(mod
p
)
g
≡
The numbers
p
,
q
,and
g
can then be considered as system parameters that are
shared and can be the same for all users (or at least a specific subset of all users).
For every user, the DSA
Generate
algorithm must then randomly select a
private DSA signing key
x
∈
Z
q
and compute the corresponding public DSA
g
x
(mod
p
). If they are not system parameters, then
p
,
q
,and
g
are also part of the verification key.
We consider a toy example to illustrate the DSA. Let
p
=23,
q
=11,and
g
=2be system parameters. Note that
q
=11is prime and divides
p
verification key
y
≡
1=22.For
a particular user, the DSA
Generate
algorithm randomly selects
x
=3and computes
y
−
2
3
(mod 23) = 8. So the private DSA signing key is 3 and the corresponding
public DSA verification key is 8.
≡
15.2.3.2
Signature Generation Algorithm
The DSA
Sign
algorithm is illustrated in Algorithm 15.2. It requires and makes use
of a cryptographic hash function
h
. In the current version of the DSA, it is intended
to use SHA-1 (see Section 8.3.3) as
h
. The algorithm consists of three steps:
