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