CVSROOT: /cvs
Module name: src
Changes by: t...@cvs.openbsd.org 2022/07/13 00:32:15
Modified files:
lib/libcrypto/bn: bn_lcl.h
Added files:
lib/libcrypto/bn: bn_bpsw.c
Log message:
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
