A Performant, Misuse-Resistant API for Primality Testing
Loading...
Author / Producer
Date
2020-10
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
Journal / series
Volume
Pages / Article No.
195 - 210
Publisher
Association for Computing Machinery
Event
27th ACM SIGSAC Conference on Computer and Communications Security (CCS 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Primality testing; Prime generation; Miller-Rabin test; Lucas test; Baillie-PSW test; API design
Organisational unit
09653 - Paterson, Kenneth / Paterson, Kenneth
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.