Paper 2020/065

A Performant, Misuse-Resistant API for Primality Testing

Jake Massimo and Kenneth G. Paterson

Abstract

Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least $1 - 2^{128}$. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17\%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. Minor revision.
Keywords
primality testingAPI design
Contact author(s)
kenny paterson @ inf ethz ch
jake massimo 2015 @ rhul ac uk
History
2020-01-21: received
Short URL
https://ia.cr/2020/065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/065,
      author = {Jake Massimo and Kenneth G.  Paterson},
      title = {A Performant, Misuse-Resistant API for Primality Testing},
      howpublished = {Cryptology ePrint Archive, Paper 2020/065},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/065}},
      url = {https://eprint.iacr.org/2020/065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.