> > BN_mod_mult_montgomery() first does a full multiplication, then a
> > Montgomery reduction. Would the speedup for RSA etc be significant
> > if we changed that?
>
> I think you are misinterpreting the code!
Hm, I haven't read the paper cited in the source, but if you have a
look at Algorithm 14.36 in the Handbook of Applied Cryptography,
that combined algorithm should be faster than multiplying everything
first and reducing later. And that clearly is what OpenSSL does
(I don't think I'm misinterpreting that):
int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
BN_MONT_CTX *mont, BN_CTX *ctx)
{
BIGNUM *tmp,*tmp2;
// ...
if (a == b)
{
if (!BN_sqr(tmp,a,ctx)) goto err;
}
else
{
if (!BN_mul(tmp,a,b,ctx)) goto err;
}
/* reduce from aRR to aR */
if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err;
// ...
}
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
