A Performant, Misuse-Resistant API for Primality Testing. / Massimo, Jake; Kenneth G. Paterson.

Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. 2020. p. 195-210.

Research output: Chapter in Book/Report/Conference proceedingConference contribution



  • Accepted Manuscript

    Rights statement: Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

    Accepted author manuscript, 1 MB, PDF document



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.
Original languageEnglish
Title of host publicationProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020
Number of pages16
Publication statusPublished - Oct 2020
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 37935594