Cryptography Reference
In-Depth Information
·
(
)
q
a 160-bit prime. Signatures have size 2
, which is 320 bits in the case we
have mentioned, and computations are carried out in the subgroup of order
q
of
len
q
Z
p
consisting of the identity and the elements of order
q
; all of the latter are generators of
this subgroup. Thus the scheme is much more efficient than Elgamal since modular
exponentiations with a 160-bit exponent are much faster than those with a 1024-bit
exponent. On top of all this, attacks like Bleichenbacher's smoothness-based one are
no longer effective against this scheme.
Exercise 9.7
Obtain an estimate of the average ratio between the time required by
an exponentiation modulo (a 1024-bit prime)
p
with a 1024-bit exponent and another
one with a 160-bit exponent. Use Maple to perform an experiment that computes the
average ratio for a number of exponentiations of this kind, with pseudo-randomly
chosen exponents and bases, and compare the result to the previous estimate.
9.4.1 The DSA Signature Scheme
Schnorr's signatures were the precursor of the very similar
Digital Signature Algo-
rithm
(DSA) that, after being first proposed in 1991, was adopted by NIST in the
Digital Signature Standard
[75] and, because of this, became very popular. The DSA
uses as “domain parameters” (or system parameters) two primes
p
,
q
, which describe
the group used by the scheme, as well as a generator of this group. Thus the domain
parameters are defined by a triple
(
p
,
q
,
g
)
, where
p
is an
L
-bit prime,
q
an
N
-bit
Z
p
of order
q
(so that
g
is a generator
prime such that
q
|
p
−
1, and
g
an element of
Z
p
). The values of
L
and
N
must correspond
of the unique subgroup of order
q
of
to one of the following pairs:
⎧
⎨
(
1024
,
160
)
(
2048
,
224
)
(
L
,
N
)
=
(9.3)
⎩
(
2048
,
256
)
(
3072
,
256
)
The scheme also makes use of a hash function which must be one of the NIST-
approved functions specified in [74], namely, either SHA-1 or one of the SHA-2
variants, SHA-224, SHA-256, SHA-384 or SHA-512. If a pair
(
L
,
N
)
as above is
chosen, then either SHA-1 if
N
=
160 or some SHA-
xyz
, where
xyz
≥
N
(often
=
>
xyz
N
, then
the output of
H
will be truncated to include only the leftmost
N
bits and reduced
modulo
q
. This way,
H
can be regarded as a function from
N
) will be used (see [74] for more detail and alternatives). If
xyz
}
∗
to
Z
q
.
In [75], methods to choose the domain parameters are also specified. We will give
more details in our Maple implementation below but, for now, we just remark that
the prime
q
is generated first and then appropriately sized pseudo-random integers
p
such that
q
{
0
,
1
1 are generated with the help of the hash function
H
, until one
is found which is prime. The generator
g
is obtained from an element of
|
p
−
Z
p
which
