----- Original Message -----
From: "Andrew Berg" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tuesday, April 29, 2003 7:06 PM
Subject: BN_mod_exp with negative exponents
>
> I ran into a situation today that was not what I expected, and not what I
> consider to be "right".
>
> Calling BN_mod_exp with a negative value for p seems to be giving me the
> same value as calling BN_mod_exp with the absolute value of p.
>
> I don't have real convenient sample code, but it should be simple enough
to
> reproduce:
>
> BN_mod_exp(r, 17, -2, 47, ctx) gives me: 7 when I expect: 27.
>
I agree that 27 is the expected answer. Either it should produce 27 or, much
less desirably, produce an error for negative exponents.
> Looking at the code, it seems obvious enough that BN_mod_exp should
> (could?) start with a test for p being negative and then do something like
> "p <-p mod (m-1); if (p < 0) (p <-p + m-1);" if it is.
>
This method only works if m is a prime. The usual way to compute a^p mod m
for negative p is, compute (a^(-1)) ^ (-p) mod m using something like the
following
if (p<0) {
if (BN_mod_inverse(aInverse, a, m, ctx) != NULL) { // if GCD(a,m)=1
ptemp = -p; // just copy the bignum and set ptemp->neg = 0;
BN_mod_exp_positive(r, aInverse, ptemp, m, ctx);
return r;
} else {
return NULL;
}
}
======================
Greg Stark
[EMAIL PROTECTED]
======================
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
