Authenticating Communications Using Digital Signatures - Implementing SSL/TLS Using Cryptography and PKI - page 206

the secrecy of the parameter k — which, you'll recall, was generated randomly
in the signature stage. Since s depends on k and the private key x — and x and
y are of course mathematically related — v depends on s and y . The whole com-
plicated mess described in this section just repeats the computation
r ( g k % p ) % q

without having access to k .
In code, this can be implemented as in Listing 4-33.

Listing 4-33: “dsa.c” DSA signature verifi cation algorithm

int dsa_verify( dsa_params *params,
huge *public_key,
unsigned int *hash,
int hash_len,
dsa_signature *signature )
{
int match;
huge w, z, u1, u2, q, p;

set_huge( &q, 1 );
set_huge( &p, 1 );
set_huge( &w, 0 );

// w = inv(s) % q
copy_huge( &w, &signature->s );
inv( &w, &params->q );

// z = hash(message), truncated to sizeof(q)
load_huge( &z, ( unsigned char * ) hash,
( (hash_len * 4 ) < params->q.size ) ?
(hash_len * 4 ) : params->q.size );

// u1 = (zw) % q
multiply( &z, &w );
copy_huge( &q, &params->q );
divide( &z, &params->q, NULL ); // u1 = z

// u2 = (rw) % q
multiply( &w, &signature->r );
copy_huge( &q, &params->q );
divide( &w, &q, NULL ); // u2 = w

// v = ( ( ( g^u1) % p * (y^u2) %p ) % p ) % q
mod_pow( &params->g, &z, &params->p, &u1 );
mod_pow( public_key, &w, &params->p, &u2 );
multiply( &u1, &u2 );
copy_huge( &p, &params->p );
divide( &u1, &p, NULL );