Re: Bug report: primality testing algorithm.
Paulo S. L. M. Barreto wrote: Greetings. I'm implementing elliptic curve software on top of OpenSSL Bignum library. Interesting. Will you be making the code public? 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! Do you have a URL referencing these NIST standard curves? 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. I'll have a look if I have time. Steve. -- Dr Stephen N. Henson. http://www.drh-consultancy.demon.co.uk/ Personal Email: [EMAIL PROTECTED] Senior crypto engineer, Celo Communications: http://www.celocom.com/ Core developer of the OpenSSL project: http://www.openssl.org/ Business Email: [EMAIL PROTECTED] PGP key: via homepage. __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: Bug report: primality testing algorithm.
Dr Stephen Henson wrote: 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! Do you have a URL referencing these NIST standard curves? Ignore that. I've found the URL. On NISTs site oddly enough :-) -- Dr Stephen N. Henson. http://www.drh-consultancy.demon.co.uk/ Personal Email: [EMAIL PROTECTED] Senior crypto engineer, Celo Communications: http://www.celocom.com/ Core developer of the OpenSSL project: http://www.openssl.org/ Business Email: [EMAIL PROTECTED] PGP key: via homepage. __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: Bug report: primality testing algorithm.
"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]