ANSI X9.80:2020 pdf free download – Prime Number Generation, Primality Testing, and Primality Certificates
1 Scope
In the current state of the art in public key cryptography, all methods require, in one way or another, the use of prime numbers as parameters to the various algorithms. This document presents a set of accepted techniques for generating prime numbers, often referred to as simply “primes”. It is intended that ASC X9 standards that require the use of primes will refer to this document rather than trying to define these techniques on a case-by-case basis. Standards, as they exist today, may differ in the methods they use for parameter generation from those specified in this document. It is anticipated that each existing ASC X9 standard will be modified to reference this document during its 5-year review instead of specifying its own techniques for generating primes. This Standard defines methods for generating large prime numbers as needed by public key cryptographic algorithms. It also provides testing methods for testing candidate primes presented by a third party. Furthermore, the use of prime generation schemes described in the Digital Signature Standard (DSS), FIPS 186-4 (or later versions) are permitted by this Standard.
NOTE The 2 −100 failure probability is selected to be sufficiently small that errors are extremely unlikely ever to occur in normal practice. Moreover, even if an error were to occur when one party tests a prime, subsequent tests by the same or other parties would detect the error with overwhelming probability. Furthermore, the 2 −100 probability is an upper bound on the worst-case probability that a test declares any non-prime candidate to be prime; not all non-primes may reach this bound, and the probability that a non-prime generated at random passes such a test is much lower. Accordingly, the 2 −100 bound is considered appropriate independent of the size of the prime being generated and the intended security strength of the cryptosystem in which the prime is to be employed. For high-assurance applications, however, the deterministic methods may nevertheless be preferable.
5.1 General Discussion
This section discusses prime generation by a first party (i.e., the generation of primes by the user of the primes) and by a second party (i.e., the generation of primes for use by others). Prime numbers may be generated using two methods. The first method generates candidate integers at random and then tests them for primality using a probabilistic algorithm. As the test is probabilistic, certificates of primality are not generated. 2 This method is discussed in Section 5.2. The second method actually constructs integers from smaller integers in such a way that the constructed integer is guaranteed to be prime. In addition, certificates of primality may be issued. The verification of primality via a certificate is very fast, and thus the guaranteed method may be better suited for second-party use. This method is discussed in Section 5.3. All random values shall be generated in conformance with ANS X9.82 using approved random bit generators.