Subject: Re: Power function PGP math library?

From: [email-masked] ("Hal Finney")
Date: Thu, 16 Jun 2005 23:25:28 -0700 (PDT)

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

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 17 Jun 2005 23:24:35 +1200

[email-masked] ("Hal Finney") writes:

>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.

Some thoughts:

>gmp,

Needs GNU-everything-else in order to build, a problem if you're targetting
multiple platforms and need to use non-GNU tools (e.g. VC++).

>crypto++

Extreme C++, both in the code style and the requirements it places on
compilers.

>openssl

The code is the crypto equivalent of Heathrow Airport.

>libtommath

Very nice, although it suffers the no-visible-means-of-support problem that
killed the earlier (and equally nice) bnlib: What happens if the author gets
tired of maintaining it?

Peter.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 21 Jun 2005 16:55:35 +0100

> The code is the crypto equivalent of Heathrow Airport.

The bignum code is reasonably OK :-)

-- 
 >>>ApacheCon Europe<<<                   http://www.apachecon.com/

http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 22 Jun 2005 13:16:28 +1200

>The bignum code is reasonably OK :-)

I'd always seen that as the bit with all the excavators :-).

Peter.