Digital Signatures - Introduction to Cryptography with Maple - page 545

H of output length greater than N requires an explicit agreement between the
participating entities and, on the other hand, the use of a hash function with
output length less than N reduces the security strength of the algorithm and is
not recommended. Thus the definition above reflects typical usage and we shall
follow it in the Maple implementation that follows.

The next proposition shows that signatures generated by Sign DSA are accepted
by Ve r DSA :

Proposition 9.1 Let ( x , y ) be a DSA private key/public key pair and ( r , s ) the sig-

nature output by Sign DSA on input x and a message m. Then Ve r DSA ( y , m , r , s ) = 1 .

k − 1 Proof Letting z = H ( m ) we have that s = ( z + xr ) mod q and hence k =

s − 1 mod q . Thus we have: w ( z + xr ) mod q , where w =

g wz mod q y wr mod q mod p g wz mod q g wxr mod q mod p v = ( ) mod q = ( ) mod q

g w ( z + xr ) mod q mod p g k mod p

= ( ) = ( ) = .

mod q mod q r

9.4.2 DSA Security

Let us now briefly review the security aspects of DSA. The initial proposal was
criticized, among other things, because the selection process by NIST was not public
and the standard was developed in collaboration with the NSA in a too-secretive way.
This is reminiscent of the criticism against DES and, also in this case, there was a
serious security concern related to parameter size, specifically concerning the size of
the prime p that initially was set to 512 bits and considered insufficient. This size was
later revised and, as indicated above, several modulus sizes are now available, the
least of them being 1024 bits. It is clear that with a 512-bit size the scheme would be
easily broken today. Indeed, as we have mentioned in Chap. 6 , a discrete logarithm
in Z p , for a 530-bit prime p was already computed in 2007 by means of the NFS

algorithm [112]. Being able to compute discrete logarithms in the subgroup of order q
of

Z p gives a total break of the scheme as it allows the adversary to compute the
private key x from the public key y , so it is clear that a 1024-bit size for p is the
minimum required to have a reasonable security margin in relation to this attack.
When trying to evaluate the security of DSA against attacks based on comput-
ing discrete logarithms, the size of p is not the only thing that should be taken into
account. Indeed, all DSA operations take place in the subgroup of order q of Z p and

so, if we want to solve a discrete logarithm in this subgroup we have, in principle, two
approaches available. The first of them is to compute the discrete logarithm in

Z p ,
a group for which the index calculus methods are available (and were used, for exam-
ple, in the 530-bit record mentioned above). For a 1024-bit prime p it is estimated
that solving discrete logarithms in Z p requires a number of operations of the order of

2 80 which is still regarded as infeasible although not by a wide margin. The second
approach is to compute the discrete logarithm working directly in the subgroup of