"Paulo S. L. M. Barreto" wrote:
>
> Greetings.
>
> I'm implementing elliptic curve software on top of OpenSSL Bignum
> library. When testing it on NIST's standard curves, I found a problem that
> seems not to be in my code: Bignum reports that NIST's 384-bit prime is not
> prime! I've checked the value with MIRACL and Java (which in turn uses
> Colin Plumb's Bnlib), and both say that P384 is indeed prime, as expected.
>
> If anyone would like to check it, here's a test program that reveals the error:
The short answer, amazingly, is that BN_div() is broken! A quick fix is
to set the "#if 0" to "#if 1" at the top of crypto/bn/bn_div.c.
In a way, I'm glad this bug was there, coz it made me (finally) figure
out the prime testing. It uses Fermat's test, which seems a little
strange to me, since it is known to fail to diagnose some composite
numbers.
It also uses a home-brewed mod_exp function (essentially, that's what
witness() is) which is, presumably, slower than the "real" thing.
Anyway, I'm too tired now to diagnose BN_div(), I'm going back to bed.
I suspect we should switch to Miller-Rabin or some other popular prime
tester, though. Not that that will fix this bug.
Cheers,
Ben.
--
SECURE HOSTING AT THE BUNKER! http://www.thebunker.net/hosting.htm
http://www.apache-ssl.org/ben.html
Y19100 no-prize winner!
http://www.ntk.net/index.cgi?back=2000/now0121.txt
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
