Steven D'Aprano <steve+pyt...@pearwood.info> added the comment: 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 :-) ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue40028> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
