Kimmo writes:
I need to verify the DSA signature in my application, and the verifier has
to compute these parameters, which are defined in the DSS (Digital Signature
Standard).
w = (s')^-1 mod q
u1 = ((SHA(M')w) mod q
u2 = ((r')w) mod q
v = (((g)^u1 * (y^u2) mod p) mod q
I'm using PGP math library in calculation. The problem is how to calculate
parameter v.
The parameters g (power to u1) and y (power to u2) should be calculated
first and then these factors should be calculated together and so on. But
there isn't a function in the math library to calculate powers. The
calculation could be done with mp_mult, but it is very slow way to do it.
If you are using the math library I think, the one that came with the
old, old version 2.x of PGP, you can look at a web page I wrote back in
1993 that describes the math library,
http://www.finney.org/~hal/pgp_math_lib.html. There you will see that
there is in fact a function to calculate powers, mp_modexp. This does
a modular exponentiation, so you would use p as the modulus to calculate
g^u1 and y^u2, then multiply them together using mp_modmult. Note that
mp_modmult does not take a modulus parameter, rather you have to call
stage_modulus with p before calling mp_modmult. Then you can use mp_mod
to take v mod q.
I have to say that I think there are better choices for math libraries
these days than that old code. gmp, crypto++ and openssl are three
that I have used and are good quality. I've also heard good things
about libtommath. You can find more about any of these via google.
Hal Finney