Message368140
Speaking of OpenSSL, a few years ago this paper came out about OpenSSL's
vulnerability to adversarial composites. Quote:
"As examples of our findings, weare able to construct 2048-bit
composites that are declared prime with probability 1/16 byOpenSSL’s
primality testing in its default configuration; the advertised
performance is 2^−80. We can also construct 1024-bit composites
that always pass the primality testing routine in GNU GMP when
configured with the recommended minimum number of rounds."
https://eprint.iacr.org/2018/749.pdf
The paper discusses various languages, libraries, crypto toolkits,
computer algebra systems, etc, including some Python libraries, and
shows how many of them are vulnerable to adversarial composites. With
some of them, the authors were able to defeat the isprime function 100%
of the time.
My take on this is as follows:
For 64-bit ints, a deterministic set of M-R bases is sufficient (since
it's deterministic there's no way to fool it into passing a composite as
prime).
For ints with more than 64-bits, the authors suggest either:
- a minimum of one M-R test with base 2, followed by 1 Lucas test (this
is equivalent to a Baillie-PSW test; there are currently no known
Baillie-PSW pseudoprimes and no known adversarily attacks against it;
(unless the NSA has some, but if so, they aren't saying)
- a default of 64 rounds with randomly choosen Miller-Rabin bases.
Presumably doing trial division on larger numbers to weed out the easy
cases is acceptable too :-) |
|
Date |
User |
Action |
Args |
2020-05-05 13:02:24 | steven.daprano | set | recipients:
+ steven.daprano, tim.peters, rhettinger, mark.dickinson, christian.heimes, serhiy.storchaka, remi.lapeyre, jfine2358, trrhodes |
2020-05-05 13:02:24 | steven.daprano | link | issue40028 messages |
2020-05-05 13:02:24 | steven.daprano | create | |
|