This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author steven.daprano
Recipients christian.heimes, jfine2358, mark.dickinson, remi.lapeyre, rhettinger, serhiy.storchaka, steven.daprano, tim.peters, trrhodes
Date 2020-05-05.13:02:24
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <20200505125755.GG16433@ando.pearwood.info>
In-reply-to <1588678245.76.0.351822793813.issue40028@roundup.psfhosted.org>
Content
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 :-)
History
Date User Action Args
2020-05-05 13:02:24steven.dapranosetrecipients: + steven.daprano, tim.peters, rhettinger, mark.dickinson, christian.heimes, serhiy.storchaka, remi.lapeyre, jfine2358, trrhodes
2020-05-05 13:02:24steven.dapranolinkissue40028 messages
2020-05-05 13:02:24steven.dapranocreate