Implement the Baillie-PSW primality test
authortb <tb@openbsd.org>
Wed, 13 Jul 2022 06:32:15 +0000 (06:32 +0000)
committertb <tb@openbsd.org>
Wed, 13 Jul 2022 06:32:15 +0000 (06:32 +0000)
commit1567c04afe0f462e73fec3091331aa3af4e215ad
treeb5968cefe8a35c7b5a7730df5e15c2a6a53d1715
parent63dd1c57ed6c6ef170ff0a885419704bb8cc2bba
Implement the Baillie-PSW primality test

It has long been known that pure Miller-Rabin primality tests are
insufficient. "Prime and Prejudice: Primality Testing Under Adversarial
Conditions" https://eprint.iacr.org/2018/749 points out severe flaws
in many widely used libraries. In particular, they exhibited a method to
generate 2048-bit composites that bypass the default OpenSSL (and hence
LibreSSL) primality test with a probability of 1/16 (!).

As a remedy, the authors recommend switching to using BPSW wherever
possible. This possibility has always been there, but someone had to
sit down and actually implement a properly licensed piece of code.

Fortunately, espie suggested to Martin Grenouilloux to do precisely this
after asking us whether we would be interested. Of course we were!
After a good first implementation from Martin and a lot of back and
forth, we came up with the present version.

This implementation is ~50% slower than the current default Miller-Rabin
test, but that is a small price to pay given the improvements.

Thanks to Martin Grenouilloux <martin.grenouilloux () lse ! epita ! fr>
for this awesome work, to espie without whom it wouldn't have happened,
and to djm for pointing us at this problem a long time back.

ok jsing
lib/libcrypto/bn/bn_bpsw.c [new file with mode: 0644]
lib/libcrypto/bn/bn_lcl.h