Cryptography Reference
In-Depth Information
In this example, the subgroup has a prime order of
q
= 29, whereas the “large”
cyclic group modulo
p
has 58 elements. We note that 58 = 2
29. We replaced the
function
SHA
(
x
) by
h
(
x
) since the SHA hash function has an output of length 160
bit.
·
10.4.2 Computational Aspects
We discuss now the computations involved in the DSA scheme. The most demand-
ing part is the key-generation phase. However, this phase only has to be executed
once at set-up time.
Key Generation
Z
p
with a bit
length of 1024, and which has a prime subgroup in the range of 2
160
. This condi-
tion is fulfilled if
p
The challenge in the key-generation phase is to find a cyclic group
1 has a prime factor
q
of 160 bit. The general approach to
generating such parameters is to first find the 160-bit prime
q
and then to construct
the larger prime
p
from it. Below is the prime-generating algorithm. Note that the
NIST-specified scheme is slightly different.
−
Prime Generation for DSA
Output
: two primes (
p
,
q
), where 2
1023
<
p
<
2
1024
and 2
159
<
q
<
2
160
,
such that
p
1 is a multiple of
q
.
Initialization
:
i
= 1
Algorithm
:
−
1 find prime
q
with 2
159
<
q
<
2
160
using the Miller-Rabin algorithm
2
R
i
= 1 TO 4096
generate random integer
M
with 2
1023
<
M
<
2
1024
2.1
2.2
M
r
≡
M
mod 2
q
2.3
p
−
1
≡
M
−
M
r
(note that
p
−
1 is a multiple of 2
q
.)
IF
p
is prime
(use Miller-Rabin primality test)
2.4 RETURN (
p
,
q
)
2.5 i=i+1
3
O t p1
The choice of 2
q
as modulus in step 2.3 assures that the prime candidates gener-
ated in step 2.3 are odd numbers. Since
p
−
1 is divisible by 2
q
, it is also divisible
Z
p
thus has a subgroup of order
q
.
by
q
.If
p
is a prime,
