Cryptography Reference
In-Depth Information
{
printf( “Verificiation failed\n” );
}
free_huge( &x );
free_huge( &y );
return 0;
}
#endif
The output of this function isn't too interesting.
jdavies@localhost$ ./dsa
DSA signature of abc123 is:
r: 14297f2522458d809b6c5752d3975a00bb0d89e0
s: 2f6e24ed330faf27700470cc6074552e58cbea3a
Verifying:
Verified
But it illustrates how DSA signatures are generated. You can see a noticeable
pause when this example runs; public-key cryptography strikes again.
NOTE
DSA keys consist of the parameters
p
,
q
, and
g
, a private key
x
, and a
public key
y
.
q
must be a (random) prime number;
p
- 1 must be a multiple of
q
; and
g
is a small number (usually 2).
x
, the private key, is random, and
y
=
g
x
%p
. In general, rather than compute their own
p
,
q
, and
g
, most implementa-
tions use standardized DSA parameters. As long as
x
is random, the security of
the algorithm isn't weakened by the sharing of parameters.
How to Make DSA Effi cient
As you can imagine, it takes a bit longer to compute or verify a DSA signature
than it does to compute or verify an RSA signature. The parameters
p
and
y
need to be at least 512 bits to be secure (2,048 bits is common).
q
and
x
can be
a bit shorter; typically these are 160 bits, to match the output from an SHA-1
hash, and can still be secure as long as
p
and
y
are long. Still, this requires a lot
of computation and a lot of memory compared to RSA.
However, if you look at the signature algorithm, you notice that the only
part that depends on the message is
s
—
r
can actually be precomputed before
the message is known, as long as
q
is known because the secret parameter
k
depends on it. Because
p
,
g
, and
q
are part of the public key, a very speed-
conscious implementation could create a table of
r
and
k
values and speed up
the signature process quite a bit.
Also, notice that RSA verifi cation involves a modular exponentiation of an
enormous parameter
d
, which is 1,024 bits for reasonable security. This takes
Search WWH ::
Custom Search