Prime and Prejudice: Primality Testing Under Adversarial
Conditions
Martin R. Albrecht1
, Jake Massimo1
, Kenneth G. Paterson1
, and Juraj Somorovsky2
1 Royal Holloway, University of London
2 Ruhr University Bochum, Germany
martin.albrecht@rhul.ac.uk, jake.massimo.2015@rhul.ac.uk, kenny.paterson@rhul.ac.uk,
juraj.somorovsky@rub.de
Abstract. This work provides a systematic analysis of primality testing under adversarial
conditions, where the numbers being tested for primality are not generated randomly, but
instead provided by a possibly malicious party. Such a situation can arise in secure messaging
protocols where a server supplies Diffie-Hellman parameters to the peers, or in a secure
communications protocol like TLS where a developer can insert such a number to be able to
later passively spy on client-server data. We study a broad range of cryptographic libraries
and assess their performance in this adversarial setting. As examples of our findings, we
are able to construct 2048-bit composites that are declared prime with probability 1/16 by
OpenSSL’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. And,
for a number of libraries (Cryptlib, LibTomCrypt, JavaScript Big Number, WolfSSL), we
can construct composites that always pass the supplied primality tests. We explore the
implications of these security failures in applications, focusing on the construction of malicious
Diffie-Hellman parameters. We show that, unless careful primality testing is performed, an
adversary can supply parameters (p, q, g) which on the surface look secure, but where the
discrete logarithm problem in the subgroup of order q generated by g is easy. We close by
making recommendations for users and developers. In particular, we promote the Baillie-PSW
primality test which is both efficient and conjectured to be robust even in the adversarial
setting for numbers up to a few thousand bits.
1 Introduction
Many cryptographic primitives rely on prime numbers, with RSA being the most famous example.
However, even in constructions that do not rely on the difficulty of factoring integers into prime
factors, primality is often relied upon to prevent an adversary from applying a divide-and-conquer
approach (e.g. in the Pohlig-Hellman algorithm or in a Lim-Lee small subgroup attack [VAS+17])
or to prevent the existence of degenerate cases such as zero divisors (which may complicate security
proofs or reduce output entropy).
One approach to obtaining prime numbers in instantiations of these cryptographic primitives is
to produce such numbers as they are needed on whatever device requires them. This is accomplished
by sampling random integers and checking for primality. This process can be computationally
intensive to the point of being prohibitively so. The high cost of producing prime numbers
led implementations to seek ways to reduce this cost and, as demonstrated in [NSS+17], these
performance improvements may then lead to devastating attacks.
If the required prime numbers are public, an alternative approach is possible: (low-power)
devices are provisioned with prime numbers from a server or a standard. For example, the popular
Telegram messenger [LLC18] uses Diffie-Hellman (DH) parameters provided by the server to
establish end-to-end encryption between peers. If the peers do not validate the correctness of
the supplied DH parameters,3
the Telegram server can provide malicious DH parameters with
composite group orders and thereby passively obtain the established secrets. As a concrete and
3 We stress that they do perform validation in the default implementation.
closely related example, Bleichenbacher [Ble05] showed how the reliance on a small and fixed set
of bases in Miller-Rabin primality testing in GNU Crypto 1.1.0 could be exploited to fool GNU
Crypto into accepting malicious DH parameters. In particular, this led to an attack on the GNU
Crypto implementation of SRP enabling users’ passwords to be recovered.
Another example is the Transport Layer Security protocol [DR08] which can use Diffie-Hellman
key exchange to establish master secrets in the handshake protocol. The DH parameters are
generated by the TLS server and sent to the client during each TLS handshake.4
It is clear that the
TLS server provider does not gain any advantage by sending malicious DH parameters to the client
since it knows the established master key. However, we can consider an adversarial developer who
implements a malicious sever with backdoored DH parameter generation, cf. [Won16,FGHT17]. If
such parameters are accepted by TLS clients and used in the DH key exchange, a passive adversary
can observe the traffic and obtain the master key. Here, weak DH parameters that still pass tests by
trusted tools offer a sense of plausible deniability. Moreover, if an application simply silently rejects
bad parameters then any countermeasures could be overcome by repeatedly sending malicious
parameter sets having a reasonable probability of fooling those countermeasures, until the target
client accepts them.
In recent years we have seen several backdoors in cryptographic implementations. For example,
NIST standardised the Dual EC pseudorandom number generator (PRNG) which allows an
adversary to predict generated random values if it can select a generator point Q whose discrete
logarithm is known and collect enough PRNG output [CNE+14]. In 2016 it was shown that Juniper
had implemented this PRNG in such a way as to enable an adversary to passively decrypt VPN
sessions [CMG+16].
A notable example of a potential backdoor involving a composite number is the security
advisory [Rie16] pushed by command-line data transfer utility socat, which is popular with
security professionals such as penetration testers. There, the DH prime p parameter was replaced
with a new 2048 bit value because “the hard coded 1024 bit DH p parameter was not prime’’. The
advisory goes on to state “since there is no indication of how these parameters were chosen, the
existence of a trapdoor that makes possible for an eavesdropper to recover the shared secret from a key
exchange that uses them cannot be ruled out”, which highlights a real world application of this attack
model. Similarly, the prime group parameter p given by Group 23 of RFC5114 [LK08] for use in DH
key exchanges has been found to be partially vulnerable to small subgroup attacks [VAS+17]. It
might seem that code reviews and the availability of rigorous primality testing (in, say, mathematical
software packages, cf. Appendix L) impose high rates of detectability for malicious parameter sets
in code or standards, but as these examples highlight, such sets still occur in practice.
Given these incidents we can assume a motivated adversary who is able to implement software
serving maliciously generated primes and/or DH parameters. Thus, there is a need for cryptographic
applications that rely on third-party primes to perform primality testing. Indeed, many
cryptographic libraries incorporate primality testing facilities and thus it appears this requirement
is easy to satisfy. However, the primary application of these tests is to check primality (or, more
precisely, compositeness) for locally-generated, random inputs during prime generation. Thus, it is
a natural question to ask whether these libraries are robust against malicious inputs, i.e. inputs
designed to fool the library into accepting a composite number as prime. We refer to this setting
as primality testing under adversarial conditions.
1.1 Overview of Primality Testing
One of the most widely used primality tests is the Miller-Rabin [Mil75,Rab80] test. Based upon
modular exponentiation by repeated squaring, Miller-Rabin is an efficient polynomial-time algorithm
with complexity O(tlog3 n) where t is the number of trials performed. Yet due to its probabilistic
nature, it is well known that a t-trial Miller-Rabin test is only accurate in declaring a given composite
number to be composite with probability at least 1 − (1/4)t
. Arnualt [Arn95], Pomerance [PSW80]
and Narayanan [Nar14] all explore methods of producing Miller-Rabin pseudoprimes, that is,
4 Up to version 1.2 (inclusive) of the protocol.
2
Table 1. Results of our analysis of cryptographic libraries. This shows how the number of rounds of
Miller-Rabin used is determined, whether a Baillie-PSW test is implemented, the documented failure rate
of the primality test (that is, the probability that it wrongly declares a composite to be prime), and our
highest achieved failure rate for composite input.
Library Rounds of MR testing Baillie-PSW? Documented Our Highest
Failure Rate Failure Rate
OpenSSL 1.1.1-pre6 Default bit-size based No < 2
−80 1/16
GNU GMP 6.1.2 User-defined t No (1/4)t
100% for t ≤ 15
GNU Mini-GMP 6.1.2 User-defined t No (1/4)t
100% for t ≤ 101
Java 10 User-defined t Yes (≥ 100 bits) < (1/2)t
0% for ≥ 100 bits
JSBN 1.4 User-defined t No < (1/2)t
100%
Libgcrypt 1.8.2 User-defined t No Not given 1/1024†
Cryptlib 3.4.4 User-defined t ≤ 100 No Not given 100%
Apple corecrypto User-defined t ≤ 256 No (1/4)t
100%
Apple CommonCrypto 16 No < 2
−32 100%
LibTomMath 1.0.1 User-defined t ≤ 256 No (1/4)t
100%
LibTomCrypt 1.18.1 User-defined t ≤ 256 No (1/4)t
100%
WolfSSL 3.13.0 User-defined t ≤ 256 No (1/4)t
100%
Bouncy Castle C# 1.8.2 User-defined t No (1/4)t
(1/4)t
Botan 2.6.0 User-defined t No ≤ (1/2)t
(1/4)t
Crypto++ 7.0 2 or 12 Yes Not given 0%
GoLang 1.10.3 User-defined t Yes < (1/4)t
0%
GoLang pre-1.8 User-defined t No < (1/4)t
100% for t ≤ 13
† When calling the check prime function as opposed to gcry prime check (or calling gcry prime check
in versions prior to 1.3.0).
composite numbers that when tested by Miller-Rabin, achieve the highest probability of (1/4)t
of
being wrongly classified as “probably prime”.
Another common choice is the Lucas test [BW80], and its more stringent variant the strong
Lucas probable prime test. Similarly to the Miller-Rabin test, t trials of a strong Lucas test will
declare a given composite number as being composite with probability at least 1 − (4/15)t
and
as being prime with probability at most (4/15)t
[Arn97]. As with the Miller-Rabin test, there are
known methods for constructing strong Lucas pseudoprimes [Arn95].
The Lucas test (strong or standard) can be combined with a single Miller-Rabin test (on base 2)
to form what is known as the Baillie-PSW test [Pom84]. Due to slightly longer running times, this
test is often only adopted for use in mathematical software packages and seen less in cryptographic
libraries. Unlike the Miller-Rabin and Lucas tests when performed alone, there are no known
pseudoprimes for the Baillie-PSW test (yet there is no proof that they cannot exist).
Clearly, when conducting a Miller-Rabin or Lucas test, the choice of the parameter t (the number
of trials) is critical. Many cryptographic libraries, for example OpenSSL [OP18b], use test parameters
originating from [DLP93] as popularised in the Handbook of Applied Cryptography [MVOV96].
These give the number of iterations of Miller-Rabin needed for an error rate less than 2−80, when
testing a random input n. A main result of [DLP93] is that if n is a randomly selected b-bit odd
integer, then t independent rounds of Miller-Rabin testing to give an error probability:
P(X|Yt) < b3/2
2
t
t
−1/2
4
2−
√
tb for 3 ≤ t ≤ b/9 and b ≥ 21,
where X denotes the event that n is composite, and Yt the event that t rounds of Miller-Rabin
declares n to be prime. This bound enables the computation of the minimum value t needed to
obtain P(X|Yt) ≤ 2
−80 for a range of bit-sizes b; see Table 2.
However, these error estimates are for primality testing with Miller-Rabin on randomly generated
n. In the adversarial setting, we are actually concerned with the probability that t trials of MillerRabin
(or some other test) declare a given n to be prime, given that it is composite. This probability
3
is independent of bit-size, and is at most (1/4)t
if random bases are used in Miller-Rabin tests.
Similar remarks apply for both variants of the Lucas test.
Technical guideline documents such as Cryptographic Mechanisms BSI TR–02102–1 [fSidI17]
and publicly announced standards such as the Digital Signature Standard (DSS) FIPS 186–4
C.3.2 [Pub13] and the International Standard for Prime Number Generation ISO/IEC 18032 [Sta05]
provide formal guidance and suggestions on parameter choices. BSI TR–02102–1 suggests that
in the worst case, 50 rounds of random base selection Miller-Rabin must be performed, and in
the average case it, like ISO/IEC 18032, references the method proposed by Damg˙ard [DLP93]
and the Handbook of Applied Cryptography [MVOV96] as described above. BSI TR–02102–1 also
references the guidance given in FIPS 186–4, who give much more conservative rounds of iterations
(t = 40 for 1024 and t = 56 for 2048 bit n) for DSA parameter generation, as well as a detailed
justification. FIPS 186–4 advocates the use of an additional Lucas primality test (cf. Section 2.3)
and also gives an elaboration of the distinction between the two conditional probabilities described
above, in its Appendix F.2. The standard ISO/IEC 18032 correctly states that the worst case
failure probability is indeed (1/4)t
, but does not make the distinction between the two conditional
probabilities as clear.
Many libraries, for example GNU GMP [Gt18], provide primality testing functions to be
deployed in applications such as mathematical software packages that require arbitrary precision
arithmetic. These functions often obligate the user to choose the ‘certainty’ or accuracy of the
primality test performed. Since these parameters are often hidden from the end user, this then
forces the responsibility of choosing suitable parameters on the developer of the application using
the library. The only resulting guidance that is filtered through from the standards are then found
in the documentation of the library, which are often brief and informal.
1.2 Contributions & Outline
We investigate the implementation landscape of primality testing in both cryptographic libraries
and mathematical software packages, and measure the security impact of the widespread failure of
implementations to achieve robust primality testing in the adversarial setting.
We review primality testing in Section 2. In Section 3, we then review known techniques for
constructing pseudoprimes and extend them with our target applications in mind. In Section 4,
we then survey primality testing in cryptographic libraries and mathematical software, evaluating
their performance in the adversarial setting. We propose techniques to defeat their tests where we
can. Overall, our finding is that most libraries are not robust in the adversarial setting. Our main
results in this direction are summarised in Table 1.
As one highlight of our results, we find that OpenSSL with its default primality testing routine
will declare certain composites n of cryptographic size to be prime with probability 1/16, while
the documented failure rate is 2−80. This arises from OpenSSL’s reliance on Table 2 to compute
the number of rounds of Miller-Rabin testing required, and this number decreases as the size of
n increases. As another highlight, we construct a 1024-bit composite that is guaranteed to be
declared prime by the GNU GMP library [Gt18] for anything up to and including 15 rounds of
testing (the recommended minimum by GMP). This is as a result of GNU GMP initialising its
PRNG to a static state and consequently using bases in its Miller-Rabin testing that depend only
on n, the number being tested. We also show how base selection by randomly sampling from a fixed
list of primes, as in Apple’s corecrypto library, Cryptlib, LibTomCrypt, JavaScript Big Number
(JSBN) and WolfSSL, can be subverted: we construct composites n of cryptographic size that are
guaranteed to be declared prime by these libraries regardless of how many rounds of testing are
performed.
We go on to examine the implications of our findings for applications, focussing on DH parameter
testing. The good news is that OpenSSL is not impacted because of its insistence on safe primes
for use in DH; that is, it requires DH parameters (p, q, g) for which q = (p − 1)/2 and both p, q are
tested for primality. Our current techniques cannot produce malicious parameters in this case. On
the other hand, when more liberal choices of parameter are permitted, as is the case in Bouncy
4
Castle and Botan, we are able to construct malicious DH parameter sets which pass the libraries’
testing but for which the discrete logarithm problem in the subgroup generated by g is easy.
We close by discussing avenues for improving the robustness of primality testing in the adversarial
setting in Section 6.
1.3 Disclosure and Mitigations
We reported our findings and suggested suitable mitigations based on the outcome of our analysis
to OpenSSL, GMP, Apple, JSBN, Cryptlib, LibTomMath, LibTomCrypt, WolfSSL, Bouncy Castle
and Botan. We give a short review of the outcome of these discussions.
– When we reached out to the OpenSSL developers, they were in the process of amending
their primality testing code to make it FIPS-complaint [OP18a]. These changes were included
in OpenSSL versions 1.0.2p and 1.1.0i (released 14/08/2018).5 However, these changes do
not consider the adversarial scenario on which our paper focuses, and the default settings in
OpenSSL remain weak in that scenario.
– Apple changed their corecrypto library from using fixed bases in Miller-Rabin testing to using
pseudorandom bases. This vulnerability was assigned CVE-2018-4398.6
– LibTomMath and LibTomCrypt developers are in the process of adjusting the primality testing
functions within their library. They plan to remove the fixed base Miller-Rabin testing and
replace the function with a Baillie-PSW test in accordance with our recommendations [Lib18].
– WolfSSL have made several adaptations in an upcoming release [Wol18a] to their primality
testing in response to our findings. This includes now performing Miller-Rabin with pseudorandom
bases, not overriding the user’s choice of iterations, and increasing the number of rounds
performed on prime parameters in DH and DSA check functions.
– Bouncy Castle have also made changes based upon our findings, by removing the DH verification
function and replacing it with a whitelisting approach in upcoming release 1.8.3. They are also
looking into performing Baillie-PSW in future versions as per our suggestion.
– Botan version 2.7.0 [Llo18b] has increased the number of rounds of Miller-Rabin performed in
DH verification and includes the addition of the Lucas test to perform Baillie-PSW as per our
suggestions.
– GNU GMP, Mini-GMP and Cryptlib all remain unchanged, but the authors of Cryptlib pointed
out a code comment that indicates the limitations of their primality test.
– We received no response from JSBN.
2 Background on Primality Testing
A primality test is an algorithm used to determine whether or not a given number is prime.
These primality tests come in two different varieties; deterministic and probabilistic. Deterministic
primality testing algorithms prove conclusively that a number is prime, but they tend to be slow
and are not widely used in practice. A famous example is the AKS test [AKS04]. We do not discuss
such tests further in this paper, except where they arise in certain mathematical software.
Probabilistic primality tests make use of arithmetic conditions that all primes must satisfy, and
test these conditions for the number n of interest. If the condition does not hold, we learn that n
must be composite. However, if it does hold we may only infer that n is probably prime, since some
composite numbers may also pass the test. By making repeated tests, the probability that n is
composite conditioned on it having passed some number t of tests can be made sufficiently small
for cryptographic applications. A typical target probability is 2−80, cf. [MVOV96, 4.49]. A critical
consideration here is whether n was generated adversarially or not, since the bounds that can be
inferred on probability may be radically different in the two cases; more on this below.
We now discuss three widely-used tests: the Fermat, Miller-Rabin, and Lucas tests.
5 See https://www.openssl.org/news/changelog.html.
6 See https://nvd.nist.gov/vuln/detail/CVE-2018-4398 and https://support.apple.com/en-gb/
HT201222.
5
2.1 Fermat Test
The Fermat primality test is based upon the following theorem.
Theorem 1 (Fermat’s Little Theorem). If p is prime and a is not divisible by p, then
a
p−1 ≡ 1 (mod p).
To test n for primality, one simply chooses a base a and computes a
n−1
(mod n). If a
n−1 6≡ 1
(mod n), then we can be certain that n is composite. If after testing a variety of bases ai
, we find
that that they all satisfy a
n−1
i ≡ 1 (mod n), we may conclude that n is probably prime.
It is well known that there exists composite numbers that satisfy a
n−1 ≡ 1 (mod n) for all
integers a that are not divisible by n. These numbers completely thwart the Fermat test, and are
known as Carmichael numbers. These will be of relevance in the sequel. The following result is
fundamental in the construction of Carmichael numbers.
Theorem 2 (Korselt’s Criterion). A positive composite integer n is a Carmic-hael number if
and only if n is square-free, and p − 1 | n − 1 for all prime divisors p of n.
2.2 Miller-Rabin Test
The Miller-Rabin [Mil75,Rab80] primality test is based upon the fact that there are no non-trivial
roots of unity modulo a prime. Let n > 1 be an odd integer to be tested and write n = 2ed + 1
where d is odd. If n is prime, then for any integer a with 1 ≤ a < n, we have:
a
d ≡ 1 mod n or a
2
id ≡ −1 mod n for some 0 ≤ i < e.
The Miller-Rabin test then consists of checking the above conditions, declaring a number to be
(probably) prime if one of the two conditions holds, and to be composite if both fail. If one condition
holds, then we say n is a pseudoprime to base a, or that a is a non-witness to the compositeness of
n (since n may be composite, but a does not demonstrate this fact).
For a composite n, let S(n) denote the number of non-witnesses a ∈ [1, n − 1]. An upper-bound
on S(n) is given by results of [Mon80,Rab80]:
Theorem 3 (Monier-Rabin Bound). Let n 6= 9 be odd and composite. Then
S(n) ≤
ϕ(n)
4
where ϕ denotes the Euler totient function.
This bound will be critical in determining the probability that an adversarially generated n
passes the Miller-Rabin test. Since for large n, we have ϕ(n) ≈ n, it indicates that no composite
n can pass the Miller-Rabin test for t random bases with probability greater than (1/4)t
. Hence
achieving a target probability of 2−80 requires t ≥ 40. The test is commonly implemented using
either (a) a set of fixed bases (e.g. JSBN) or (b) randomly chosen bases (e.g. OpenSSL). Of course,
the (1/4)t
bound only holds in the case of randomly chosen bases.
2.3 Lucas Test
The Lucas primality test [BW80] makes use of Lucas sequences, defined as follows:
Definition 1 (Lucas sequence [Arn97]). Let P and Q be integers and D = P
2 − 4Q. Then the
Lucas sequences (Uk) and (Vk) (with k ≥ 0) are defined recursively by:
Uk+2 = P Uk+1 − QUk where, U0 = 0, U1 = 1,
Vk+2 = P Vk+1 − QVk V0 = 2, V1 = P.
6
The Lucas probable prime test then relies on the following theorem (in which 
x
p

denotes the
Legendre symbol, with value 1 if x is a square modulo p and value -1 otherwise):
Theorem 4 ([CP06]). Let P, Q and D and the Lucas sequences (Uk),(Vk) be defined as above.
If p is a prime with gcd(p, 2QD) = 1, then
Up−(
x
p )
≡ 0 (mod p). (1)
The Lucas probable prime test repeatedly tests property (1) for different pairs (P, Q). This
leads to the notion of a Lucas pseudoprime with respect to such a pair.
Definition 2 (Lucas pseudoprime). Let n be a composite number such that gcd(n, 2QD) = 1.
If Un−(
x
n )
≡ 0 (mod n), then n is called a Lucas pseudoprime with respect to parameters (P, Q).
We can now introduce the notion of a strong Lucas probable prime and strong Lucas pseudoprime
with respect to parameters (P, Q) by the following theorem.
Theorem 5 ([Arn97]). Let p be a prime number not dividing 2QD. Set p −

D
p

= 2k
q with q
odd. Then one of the following conditions is satisfied:
p | Uq or ∃i such that 0 ≤ i < k and p | V2
iq
. (2)
The strong Lucas probable prime test repeatedly tests property (2) for different pairs (P, Q).
This leads to the definition of a strong Lucas pseudoprime with respect to parameters (P, Q) as
follows.
Definition 3 (strong Lucas pseudoprime). Let n be a composite number such that gcd(n, 2QD) =
1. Set n −

D
n


= 2k
q with q odd. Suppose that:
n | Uq or ∃i such that 0 ≤ i < k and n | V2
iq
.
Then n is called a strong Lucas pseudoprime with respect to parameters (P, Q).
A strong Lucas pseudoprime is also a Lucas pseudoprime (for the same (P, Q) pair), but the
converse is not necessarily true. The strong version of the test is therefore seen as the more stringent
option.
Remark 1. The Lucas pseudoprime and strong Lucas pseudoprime tests are also known as a
Lucas-Selfridge test and a strong Lucas-Selfridge test respectively, specifically when used with
Selfridge’s parameters P = 1, Q = −1.
Analogously to the Monier-Rabin theorem for pseudoprimes for the Miller-Rabin primality test,
Arnault [Arn97] showed that for an integer D and n a composite with gcd(D, n) = 1 and n 6= 9,
the number of pairs (P, Q) with 0 ≤ P, Q < n, gcd(Q, n) = 1, P
2 − 4Q ≡ D (mod n) such that n
is strong Lucas pseudoprime with respect to (P, Q) is at most 4n/15. There is an exception to this
result for certain forms of twin primes (we omit the details here), but Arnualt goes on to prove that
even these particular forms of twin prime n have at most n/2 pairs (P, Q) such that n is a strong
Lucas pseudoprime with respect to (P, Q). From this, we can infer that t applications of the strong
Lucas test would declare a composite n to be probably prime with a probability at most (4/15)t
.
2.4 Baillie-PSW
The Baillie-PSW [Pom84] test is a probabilistic primality test formed by combining a single MillerRabin
test with base 2 with either a Lucas or strong Lucas pseudoprime test. The idea of this test is
that the two components are “orthogonal” and so it is very unlikely that a number n will pass both
parts. Indeed, there are no known composite n that pass the Baillie-PSW test. Gilchrist [Gil13]
7
confirmed that there are no Baillie-PSW pseudoprimes less than 264. PRIMO [Mar16] is an elliptic
curve based primality proving program that uses the Baillie-PSW test to check all intermediate
probable primes. If any of these values were indeed composite, the final certification would necessarily
have failed. Since this has never occurred during its use, PRIMO’s author Martin estimates [Wei18]
that there are no Baillie-PSW pseudoprimes with less than about 10000 digits. This empirical
evidence suggests that numbers of cryptographic size for use in Diffie-Hellman and RSA are unlikely
to be Baillie-PSW pseudoprimes. However, Pomerance gives a heuristic argument in [Pom84] that
there are in-fact infinitely many Baillie-PSW pseudoprimes. The construction of a single example
is a significant open problem in number theory.
3 Constructing Pseudoprimes
In this section, we review known methods of constructing pseudoprimes for the Miller-Rabin and
Lucas tests. We also provide variations on these methods. We will use the results of this section in
the next one, where we study the robustness of cryptographic libraries for primality testing in the
adversarial setting.
3.1 Miller-Rabin Pseudoprimes
The exact number of non-witnesses S(n) for any composite number n can be computed given the
factorisation of n [CP06]. Generating composites n that have large numbers of non-witnesses is
not so straightforward. In empirical work, Pomerance et al. [PSW80] showed that many composite
numbers that pass a Miller-Rabin primality test have the form n = (k + 1)(rk + 1) where r is small
and both k + 1 and rk + 1 are prime. More recently, H¨oglund [H¨o16] and Nicely [Nic16] used the
Miller-Rabin primality test as implemented in GNU GMP to test randomly generated numbers
of this form for various values of r and for various different sizes of k. Their results support the
claims made by [PSW80].
We now consider existing methods for producing composites which have many non-witnesses,
for two forms of the Miller-Rabin test: firstly where the bases are chosen randomly and secondly
where a fixed set of bases is used.
3.1.1 Random Bases. For random bases, we are interested in constructing composite n that
have large numbers of non-witnesses, i.e. for which S(n) is large. Such numbers will pass the
Miller-Rabin test with probability S(n)/n per trial; of course, this probability is bounded by
ϕ(n)/4n ≈ 1/4 by the Monier-Rabin theorem, but we are interested in how close to this bound we
can get. We rely on the following:
Theorem 6 ([Mon80]). Consider an odd composite integer n with m distinct prime factors
p1, . . . , pm. Suppose that n = 2e
· d + 1 where d is odd. Also suppose that n =
Qm
i=1 p
ti
i where each
pi can be expressed as 2
ei
· di + 1 with each di odd. Then
S(n) = Ym
i=1
gcd(d, di) ·

2
min(ei)·m − 1
2m − 1
+ 1
. (3)
Note how the bound in this theorem does not depend on the exponents ti
, indicating that squarefree
numbers will have relatively large S(n). Also note the dependence on the terms gcd(d, di),
indicating that ensuring that the odd part of each prime factor pi has a large gcd with the odd part
of n is necessary to achieve a large value for S(n). As an easy corollary of this theorem, we obtain:
Corollary 1 ([Mon80]). Let x be an odd integer such that 2x + 1 and 4x + 1 are both prime.
Then n = (2x + 1)(4x + 1) has ϕ(n) = 8x
2 and achieves the Monier-Rabin bound, i.e. it satisfies
S(n) = ϕ(n)/4.
8
The proof of this corollary follows easily on observing that we may take m = 2 and d = d1 =
d2 = x in the preceding theorem. Narayanan [Nar14] also showed that if n is a Carmichael number
of the form p1p2p3, where each pi
is a distinct prime with pi ≡ 3 (mod 4), then S(n) achieves the
Monier-Rabin bound. He also gave further results showing that these two forms for n are the only
ones achieving the Monier-Rabin bound, with all other n satisfying S(n) ≤ ϕ(n)/6.
3.1.2 Fixed Bases. Some implementations of the Miller-Rabin primality test select bases from
a fixed list (often of primes), rather than choosing them at random. For example, until 2010, the
PyCrypto 2.1.0 (2009) [Lit09] primality test isPrime() performed 7 rounds of Miller-Rabin using
the first 7 primes as bases, while LibTomMath chooses the first t entries from a hard-coded list of
primes as bases.
Arnault [Arn95] presented a method for producing composite numbers n = p1p2 · · · ph that are
guaranteed to be declared prime by Miller-Rabin for any fixed set of prime bases A = {a1, a2, . . . , at}.
We give an overview and examples of Arnault’s method in Appendix A.
Since fixed base Miller-Rabin tests are relatively uncommon in implementations, it might
seem that Arnault’s method would not be very useful. We shall however see that this method
is particularly helpful when an implementation chooses bases randomly from a large fixed list of
possibilities. For example, an implementation might select prime bases randomly from a list of
primes below 1000; since Arnault’s method scales well (we simply need to solve more congruences
simultaneously with the CRT) we can use this method to produce a composite n such that all
primes below 1000 are non-witnesses for n. We shall see applications of this approach for different
libraries in Sections 4.3, 4.5, 4.7, 4.9, 4.10 and 4.11.
3.1.3 Hybrid Technique. The method above produces composites that are in fact always
Carmichael numbers. We know from Section 3.1.1 that if n is a Carmichael number with 3 distinct
prime factors all congruent to 3 (mod 4), then n has the maximum number of non-witnesses,
ϕ(n)/4. We can set h = 3 in Arnault’s method and tweak it slightly to ensure that, as well as
producing n with a specified set A of non-witnesses, it produces an n meeting the Monier-Rabin
bound, so that random base Miller-Rabin tests will also pass with the maximum probability. The
tweak is very simple: we ensure that 2 ∈ A; this forces p1 ≡ 3 or 5 (mod 8); we then select p1 ≡ 3
(mod 8) so that p1 ≡ 3 (mod 4). Arnault’s method sets pi = ki(p1 − 1) + 1 where the ki are
co-prime to all the elements of A. Since 2 ∈ A, the ki must all be odd; it is easy to see that this
forces pi ≡ 3 (mod 4) too.
We will give an application of this technique in Section 4.6.
3.1.4 Extension For Composite Fixed Bases. The method of Arnault [Arn95] works
(as presented) only for prime bases, and not for composite bases. Although less common, some
implementations use both prime and composite bases in their Miller-Rabin testing. By setting
n ≡ 3 (mod 4), we know that e = 1 when writing n = 2e
· d + 1 for d odd. In this case, the
conditions to pass the Miller-Rabin test simply become a
(n−1)/2 ≡ ±1 (mod n). Hence, if n ≡ 3
(mod 4) is pseudoprime to some set of bases {a1, a2, . . . at}, then n is also pseudoprime for any
base b arising as a product b = a
e1
1
· a
e2
2
· · · · · a
et
t
(mod n) (for any set of indices ei ∈ Z). Therefore
we can construct a composite n that is pseudoprime with respect to any list of bases {b1, . . . , bt}
(of which any number can be composite) by using the hybrid method described in Section 3.1.3,
but with set A in that method being the complete set of prime factors arising in the bi
. Note that
in this method, n is of the form n = p1p2p3 where each pi ≡ 3 (mod 4), so we have n ≡ 3 (mod 4)
as needed. Moreover, because of the form of n, the composites generated in this manner will also
meet the Monier-Rabin bound.
We will give an application of this technique in Section 4.3, where we study Mini-GMP [Gt18]
which uses Euler’s polynomial to generate Miller-Rabin bases.
9
3.2 Lucas Pseudoprimes
Like Miller-Rabin pseudoprimes, Lucas pseudoprimes are with respect to some choice of test
parameters. Throughout this work we follow Selfridge’s Method A [BW80] of parameter selection,
which is summarised as follows:
Definition 4 (Selfridge’s Method A [BW80]). Let D be the first element of the sequence
5, −7, 9, −11, 13, . . . for which
D
n


= −1. Then set P = 1 and Q = (1 − D)/4.
There are two reasons for studying this particular method for setting parameters. The first
is that it is the parameter choice used when performing the Lucas part of the Baillie-PSW
primality test [PSW80,BW80]. The second is that this is the method that both Java [Cor18] and
Crypto++ [Dai18] libraries that we study use in their implementation of the Lucas test.
The Lucas and strong Lucas-probable prime tests with this parameter choice are commonly
referred to in the literature as Lucas and strong Lucas-Selfridge probable prime tests. Pseudoprimes
for this parameter choice are well-documented. The OEIS sequence A217120 [Bai13a] presents a
small list of them, referring to a table of all Lucas pseudoprimes below 1014 ≈ 2
47 compiled by
Jacobsen [Jac15]. There is an equivalent sequence A217255 [Bai13b] for strong Lucas pseudoprimes.
Any pseudoprime for the strong Lucas probable prime test with respect to some parameter set
(P, Q), is also a pseudoprime for the Lucas probable prime test.
Arnault [Arn95] also presented a scalable method that takes as input a set of parameter choices
{(P1, Q1, D1),(P2, Q2, D2), . . . , (Pt, Qt, Dt)} and returns a composite n of the form n = p1p2 · · · ph
that is a strong Lucas pseudoprime to the parameters (Pi
, Qi
, Di) for all 1 ≤ i ≤ t. The method is
similar to that for constructing Miller-Rabin pseudoprimes for fixed bases, but differs in its details.
In particular, the two construction methods are sufficiently different that it seems hard to derive a
single method producing n that are pseudoprimes for both the Miller-Rabin and Lucas tests.
3.2.1 A specialisation of Arnault [Arn95] for Selfridge’s Method A For Selfridge’s
Method A, we know that if we take an n such that
5
n


= −1, then a single test on n with
parameter set (P, Q, D) = (1, −1, 5) will be performed. We next show how to specialise Arnault’s
construction [Arn95] so that it will produce composites n that are guaranteed to be declared prime
by a strong Lucas test for this parameter set.
Following Arnault’s construction, we consider n of the form n = p1p2p3 where pi = ki(p1 + 1)−1
for i ∈ {2, 3}, with k2 and k3 odd integers.
We first note that the pi must satisfy certain conditions with respect to Legendre symbols
(see [Arn95, Lemmas 6.1 and 6.2]):

D
pi

=

Q
pi

= −1 for all i such that 1 ≤ i ≤ 3.
With our single parameter set (P, Q, D) = (1, −1, 5), this becomes:

−1
pi

=

5
pi

= −1 for all i such that 1 ≤ i ≤ 3. (4)
Now 
−1
pi

= −1 ⇔ pi ≡ 3 (mod 4). Since pi = ki(p1 + 1) − 1 for i ∈ {2, 3}, and the ki are odd,
then it is easy to show that if p1 ≡ 3 (mod 4) then it follows that pi ≡ 3 (mod 4) for i = 2, 3 as
well. We also have that 
5
pi

= −1 ⇔ pi ≡ 2 or 3 (mod 5). Therefore condition (4) is satisfied
when p1 ≡ 3 or 7 (mod 20) (by the CRT) and pi ≡ 2 or 3 (mod 5) for i ≥ 2.
At this point we must choose k2, k3 and add conditions that ensure the coefficients in [Arn95,
Lemma 6.1] are indeed integers. These conditions are simple:
p1 ≡ k
−1
3
(mod k2) and p1 ≡ k
−1
2
(mod k3).
10
We choose to fix p1 ≡ 7 (mod 20) and select (k2, k3) = (31, 43). This produces our final
congruence that prime p1 must satisfy: p1 ≡ 6647 (mod 26660). We now search for a prime p1 that
satisfies this congruence, and such that p2 and p3 satisfying pi = ki(p1 + 1) − 1 for i = 2, 3 are also
primes with p2 ≡ p3 ≡ 2 or 3 (mod 5).
The smallest solution is the following:
p1 = 486527, p2 = 15082367, p3 = 20920703
This yields a 68-bit n = 153515674455111174527 which indeed does pass the strong Lucas test using
Selfridge’s Method A for parameter selection. Of course, we can take any (p1, p2, p3) satisfying the
above conditions (which are not too onerous to satisfy), and in this sense the method scales well
to numbers n of cryptographically interesting size. For example, Appendix B shows a 2050-bit
example generated using the above procedure.
This generation technique is also versatile, as we can simply include additional parameters in
our set dependent on which parameter selection methods a particular test uses. This allows us to
generate composites that are declared prime by a variety of strong Lucas tests, at the small cost of
solving a few more simultaneous congruences with the CRT.
4 Cryptographic Libraries and Mathematics Packages
Many cryptographic libraries offering implementations of common cryptographic protocols also
provide a toolkit for handling arbitrary-precision integer arithmetic, including primality testing.
These functions would be used, for example, for testing the primality of Diffie-Hellman parameters.
This section provides a survey of primality testing in a broad and representative range of
cryptographic libraries (OpenSSL, GNU GMP and Mini-GMP, Java, JavaScript Big Number
(JSBN), Libgcrypt, Cryptlib, Apple corecrypto and CommonCrypto, LibTomMath, LibTomCrypt,
WolfSSL, Bouncy Castle, Botan, Crypto++ and GoLang). For each library, we first describe how
it implements primality testing. We then tailor a composite likely to be declared prime by each
particular library, and quantify the probability that our composite passes the library’s primality
test (so that the primality test fails). Our findings are summarised in Table 1. Throughout, we will
refer to the number of rounds of Miller-Rabin testing as t.
4.1 OpenSSL
OpenSSL is the most widely used open source cryptographic library and TLS implementation.
Throughout, we consider OpenSSL 1.1.1-pre6 [OP18b], although the components studied are largely
stable across releases and remain similar to that of the early releases (version 0.9.6 of Sept. 2000).
Analysis. The primality tests in OpenSSL reside in the crypto library, which also houses a wide
range of implementations of cryptographic algorithms. The services provided by the crypto library
are used by the OpenSSL implementations of SSL, TLS and S/MIME, and have also been used to
implement SSH, OpenPGP, and other cryptographic standards.
The functions called upon to perform primality testing in the OpenSSL BIGNUM library are
BN is prime ex and BN is prime fasttest ex found in bn prime.c. The bulk of the primality
testing algorithm is done in BN is prime fasttest ex where t =checks rounds of Miller-Rabin
are performed, each with a randomly chosen base. The checks variable is provided as a parameter
to the primality verification function. The function BN is prime ex simply calls BN is primefasttest
ex without doing any trial divisions. The composites n that we produce have factors
much larger than those in the trial divisions that OpenSSL performs. This means that, for our
purposes, the result of calling either function is equivalent. Therefore we will focus only on
BN is prime fasttest ex.
11
Number of Miller-Rabin rounds. Both primality testing functions allow the user to determine
the rounds of Miller-Rabin performed. The documentation indicates that if the user sets the
value of checks to the variable BN prime checks, then the number of Miller-Rabin iterations t
is chosen such that the probability of a Miller-Rabin test declaring a random composite number
n as prime is less than 2−80. The number of rounds performed is then based on the bit-size b
of the number n being tested. The relationship between these two values is shown in Table 2.
The entries here are based on average case error estimates taken from the Handbook of Applied
Cryptography [MVOV96], which in turn references [DLP93].
Table 2. The rounds t of Miller-Rabin performed chosen by OpenSSL when testing b-bit integers with
checks = BN prime checks.
b t b t
b ≥ 1300 2 400 > b ≥ 350 8
1300 > b ≥ 850 3 350 > b ≥ 300 9
850 > b ≥ 650 4 300 > b ≥ 250 12
650 > b ≥ 550 5 250 > b ≥ 200 15
550 > b ≥ 450 6 200 > b ≥ 150 18
450 > b ≥ 400 7 150 > b 27
Base Selection. OpenSSL chooses the Miller-Rabin bases it uses in a pseudorandom manner, by
using OpenSSL’s function BN rand range() with an optional flag set to PRIVATE. This then calls
bnrand to generate a pseudorandom base a in the range 1 ≤ a < n using a cryptographically
strong pseudorandom number generator with entropy inputs gathered from the operating system,
cf. [Str16] for details on OpenSSL’s random number generation.
Pseudoprimes. As mentioned in Section 1, the average case estimates from [DLP93] are designed
only to be used on testing numbers during prime generation. Indeed, OpenSSL correctly applies
primality testing as outlined above in this situation. However, we found nothing in the documentation
to warn about the adversarial setting. Instead it appears to be left up to the user to decide how
many rounds of testing are needed, and if they set checks = BN prime checks then Table 2
would dictate how many rounds are applied. In this setting, we are able to undermine OpenSSL’s
guarantees by producing composite numbers using the methods described in Section 3.1.1. That is,
we can easily construct numbers of the form n = (2x + 1)(4x + 1) with x odd and 2x + 1, 4x + 1
prime, and be sure that n will pass random-base Miller-Rabin tests with probability roughly 1/4
per test. For example, for n having b = 2048 bits, OpenSSL will apply t = 2 tests, and we have a
1/16 chance of our composite n deceiving OpenSSL.
4.2 GNU GMP
The GNU Multiple Precision Arithmetic Library [Gt18], GNU GMP or simply GMP, is a popular
open source arbitrary precision integer library that is widely deployed in mathematical software
packages. We consider the latest version GMP 6.1.2 throughout.
Analysis. GMP provides its own datatype to handle big integers known as mpz t. GMP’s
primality test is implemented in mpz probab prime p(mpz t n, int reps). On input n, this
function performs some trial divisions, then a fixed-base Fermat test with base 210 = 2 · 3 · 5 · 7, and
finally t = reps rounds of Miller-Rabin; the latter is implemented in function mpz millerrabin.
The value of reps is selected by the caller. The documentation gives assurance that a composite
number will be identified as being prime with a probability of less than (1/4)reps and states that
“reasonable values of reps are between 15 and 50”.
12
Base Selection. GMP uses a pseudorandom number generator (PRNG) to choose the base used
for each Miller-Rabin test. The PRNG’s state is initialised in the function mpz millerrabin by
calling gmp randinit default(rstate), which uses the Mersenne Twister algorithm. This initial
seed state is then used as a source of randomness in mpz urandomm(a, rstate, n) to generate a
uniform random integer base a between 2 and n − 2 inclusive.
While GMP offers to seed PRNGs and to explicitly pass them to functions requiring access
to pseudorandom numbers, this option is not available for primality testing, i.e. each call to
mpz millerrabin will work with an identical PRNG state. Thus, since the initial seed state is
constant, the resulting sequence of a values chosen by mpz urandomm for a fixed n is also constant.
Note, though, that different a may be chosen for different n, since the bases a are sampled uniformly
in a range depending on n. This, in effect, means that the bases chosen when testing n are defined
as a function of n. Therefore the result of mpz probab prime p(mpz t n, int reps) for fixed
values of n and t is deterministic.7
Pseudoprimes. For integers n, t, let (a1, a2, . . . , at) denote the deterministic list of bases used by
GMP, where t = reps. By setting n = (2x + 1)(4x + 1) with x odd and 2x + 1, 4x + 1 both prime,
we will obtain a number for which random base MR tests will pass with probability roughly 1/4.
Since (a1, a2, . . . , at) is pseudorandom, we may expect that an n constructed in this way would pass
the MR tests in GMP with probability (1/4)t
. Thus, for example, for the minimum recommended
value of t = 15, it might be feasible to construct a suitable n which would always be declared prime
by just trying sufficiently many random values of x.
However, recall that we need 2x + 1 and 4x + 1 to be simultaneously prime, and we must
also pass the base 210 Fermat test. This makes the cost of constructing n prohibitively high with
this direct approach, since the probability that random x will give prime pairs (2x + 1, 4x + 1)
is approximately (2/ ln x)
2
, and the special form of n means that a Fermat test will pass with
probability roughly 1/2 (see Appendix C), while passing t rounds of MR testing will happen
with probability only (1/4)t
. Putting this together, each x would pass with probability about
1/2
2t−1
(ln x)
2
; for a 99% chance of success in finding a good x with ln x = s, we would need about
5 · 2
2t−1
s
2
trials, each trial involving at least a primality test on 2x + 1. For a 1024-bit n and t = 15
trials (the minimum recommended by GMP), roughly 247 trials would be needed, each involving at
least a 512-bit primality test.
Instead, and partly inspired by the ROCA attack [NSS+17] and the form of the primes exploited
there [JPV00,JP06], we consider x of the special form x = kM + 189 where M is a product of the
first ` primes from in the set P = {2, 3, . . . , 373} and k is a randomly chosen integer of a size to
make n = (2x + 1)(4x + 1) have a desired target size (say, 1024 bits). The selection of x of this
form ensures that 2x + 1 = 2kM + 379 and 4x + 1 = 4kM + 757 are not divisible by the first `
primes in P, boosting the chances that 2x + 1 and 4x + 1 are both prime (the form of x essentially
ensures that 2x + 1, 4x + 1 pass trial divisions for the first ` primes in P; here we rely on the fact
that 379 and 757 are both prime and larger than 373). The offset of 189 is specially chosen so that
the Fermat test on n to base 210 will always pass for n of the chosen form. This follows from a
bespoke mathematical analysis that is deferred to Appendix C.
Our code for constructing x (and n) of this special form first picks a target bit-size for n, then
selects ` as large as possible so that there are enough choices for k for there to be sufficiently many
candidates that one suitable x will result. For each resulting x, our code tests 2x + 1 and then
4x + 1 for primality, and (if these tests pass) applies the GMP primality test for the desired number
of t rounds of MR testing.
For n of 1024 bits, we set ` = 69, taking M as the product of the primes up to 349, and leaving
a 51-bit value for k. The choice of M increases the probability that both of 2x + 1 and 4x + 1 are
prime by a factor of roughly 25, and the form of x ensures that the Fermat test always passes,
giving another factor of 2 improvement. Using a total of 33,885 core-hours (3.87 core-years) of
7 We note that the same sequence of ai may still be produced even for different n when n is only slightly
smaller than a power of two. This is due to the application of rejection sampling by comparison with n
to sample in a range up to n.
13
computation in parallel on 872 cores running at 2.4GHz (kindly donated by CloudFlare), we found
the following 1024-bit example passing GMP’s primality test with t = 15 rounds of MR testing:
n = 2960
· 0x0000000000000000000000000000000081d564fbdd20b406
+ 2768
· 0x750af7bd334dcf547b131a1d8f8235fd603dba44e22e0775
+ 2576
· 0x0ecf755051d33cb8895413f5d69f5a3df701889e3a69f92e
+ 2384
· 0xdd3f5f36662521877231ba4753a3e7185a89ddb0b2d73a35
+ 2192
· 0x9e976a9bcfeae1a7c026d74bc7515a5010f3cd62c69fa9ad
+ 20
· 0x7b699f40e7a85192e1a4aa95537363fcb93d789aee32bbbf.
We recall that this n will always pass GMP’s primality testing for 15 MR rounds because the
generation of the MR bases depends deterministically on n.
4.3 Mini-GMP
Mini-GMP is a small implementation of a subset of GMP’s mpn and mpz interfaces included within
GMP 6.1.2 [Gt18]. This library includes its own miniature implementation of mpz probab primep(n,
reps). The most significant change compared to GMP is that Miller-Rabin is performed
explicitly with a deterministic sequence of t bases obtained by evaluating Euler’s polynomial
a(x) = x
2 + x + 41 at x = 0, 1, 2, . . . , t − 1. It also omits GMP’s Fermat test.
Pseudoprimes. The use of a sequence of deterministic bases in Mini-GMP enables us to predict
the bases that will be chosen for any particular value t of reps. The bases are not all prime (though
Euler’s polynomial famously does produce many primes), so we cannot directly use Arnault’s
method from Section 3.1.2. Instead, we use our extension for composite, fixed bases method in
Section 3.1.4.
Using this approach, we constructed a 2960-bit composite n = p1p2p3 that passes up to t = 101
rounds of Mini-GMP’s Miller-Rabin testing. Of the 101 bases produced by Euler’s polynomial, 86
were already primes and the remaining 15 bases all factorised into various combinations of the
four primes 163, 167, 179 and 199. The combined list of 90 unique primes was then used with the
method described in Section 3.1.4 to produce n. This n is given in Appendix D. We note that the
documentation for Mini-GMP is shared with the main GMP library, implying to a user that 15 to
50 rounds of MR testing would be reasonable.
4.4 Java
Java implementations provide their own methods for arbitrary precision arithmetic, including
primality tests, as seen in java.math.BigInteger. We consider OpenJDK10 [Cor18], although
there seems to be no significant changes to this section of the code in older versions such as JDK8.
Analysis. The primality testing function isProbablePrime is passed a single parameter certainty.
This is a value chosen by the user and is described in the documentation as: “a measure of the
uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger
is prime exceeds (1−1/2
certainty).” The certainty parameter is then used to determine how
many rounds of testing will be performed. This is done by calling the function primeToCertainty
which is shown in Appendix E. This function first sets a variable n as (certainty + 1)/2. This
would produce a non-integer result when certainty is even, yet the result is cast to an integer,
implicitly flooring the result.8
8 Because of the role that n plays in determining the number of rounds of Miller-Rabin to be performed,
the result is that there is no difference in testing isProbablePrime(k) and isProbablePrime(k+1) when
k is odd. This has an effect on the assurance given to the user — the guarantee of 1 − 1/2
certainty is no
longer accurate for half of the values of certainty.
14
This function also takes into consideration the bit-size of the number being tested; if it is less
than 100, then Miller-Rabin is performed with at most 50 rounds; if it is greater than 100, then
both Miller-Rabin and a Lucas probable prime test with Selfridge’s parameters are performed, as
described in Section 3.2. In the latter case, the maximum number of rounds of Miller-Rabin is
determined based on the bit-size of the tested number, similarly to OpenSSL. In both cases, the
user’s choice of certainty will determine the actual number of rounds of Miller-Rabin performed
only if it is less than the internally-specified number for that bit-size.
Pseudoprimes. For numbers of cryptographically interesting size, Java performs both MillerRabin
and Lucas probable prime tests. Using the method outlined in Section 3.2 we could produce
composites that are guaranteed to be declared prime by the Lucas test. However, the resulting
forms do not fit into any of the known families of composites having high numbers of Miller-Rabin
non-witnesses. Hence, we are unable to construct any numbers passing Java’s primality test with
high probability using our current techniques.
4.5 JavaScript Big Number (JSBN)
The Java Script Big Number (JSBN) library written by Tom Wu [Wu17] provides a small cryptographic
toolkit for Java Script applications. Here we study the most recent release JSBN 1.4 from
2013. According to its homepage the library has been used in a variety of applications, including:
Forge (a pure JavaScript implementation of SSL/TLS), Google’s V8 benchmark suite version 6,
the JavaScript Cryptography Toolkit and the RSA-Sign JavaScript library.
Analysis. The library offers the primality test bnIsProbablePrime(t) where the parameter t
defines the number of rounds of Miller-Rabin the user wishes to perform. The code documentation
states that this function will “test primality with certainty ≥ 1−.5
t”. The function pseudorandomly
chooses a base a for each round of Miller-Rabin from a hard-coded list of all primes below 1000
called lowprimes.
Pseudoprimes. We can consider this implementation as performing tests with fixed bases, where
the bases chosen are all primes between 2 and 1000. We can then use Arnault’s method (Section 3.1.2)
to construct composite numbers n that pass JSBN’s primality test no matter how many rounds
of testing t the user wishes to perform. For example, we used SageMath 7.6 [S
+17] to obtain a
4279-bit composite n having 3 prime factors, see Appendix F for the details.
4.6 Libgcrypt
Libgcrypt [Koc18] is a general purpose cryptographic library originally based on code from GnuPG.
The library provides various cryptographic functions, including public key algorithms, large integer
functions and primality testing. We analyse the current stable version 1.8.2, released in December
2017
Analysis. The documentation for Libgcrypt states that the function used for checking the primality
of primes is gcry prime check which is found in primegen.c. This function then calls check prime
in which the actual testing performed. This function check prime performs three testing steps.
The first step is trial division with all primes up to 4999. The second step is a Fermat test with base
a = 2. The last step comprises t rounds of Miller-Rabin where the bases are pseudorandomly chosen.
We note that t is user defined, but cannot be set to less than 5. The default for checking the numbers
produced in the prime generation algorithm is set to 5, but when a user calls gcry prime check
the choice of t is hard-coded to 64.
15
Pseudoprimes. Following Section 3.1, beating steps 1 and 2 of the testing performed in
check prime is trivial if we choose n as a Carmichael number of the form n = pqr where
p, q, r > 4999. By using the hybrid technique in Section 3.1.3, we can create a Carmichael number
that also has the maximum number of randomly distributed non-witnesses. We then need only to
overcome the t Miller-Rabin tests with pseudorandom bases. This happens with probability (1/4)t
.
If the user calls gcry prime check then the probability with which we can fool this test would be
only 2−128. Yet performing 64 rounds of Miller-Rabin is quite time consuming, and a user may be
tempted to bypass gcry prime check and call check prime with fewer rounds. In this hypothetical
situation, or in versions of Libgcrypt prior to 1.3.0 (2007) [Koc05] (where gcry prime check would
call t = 5 rounds by default) the best we could achieve is passing the test with probability 1/1024
(for t = 5).
4.7 Cryptlib
Cryptlib 3.4.3 [Gut18] is an open source security toolkit library developed by Peter Gutmann. It
provides a variety of services including: public key algorithms, various cryptographic functions and
primality testing.
Analysis. The primalty test in Cryptlib is the function primeProbable found in kg prime.c
and is composed of t rounds of Miller-Rabin, where the value of t must be between 1 and 100
(inclusive) and is chosen by the user upon calling. The function then chooses the base for each
test incrementally from the start of a fixed list of primes. This is either a list of the first 54
primes (2 to 251) or the first 2048 primes (2 to 17863), depending on the preprocessor directive
CONFIG CONSERVE MEMORY.
Pseudoprimes. Since t ≤ 100, we will at most only ever test using the primes between 2 and
541 (the hundredth prime) as bases. We can therefore generate numbers that are guaranteed to be
declared prime by this test for any valid input t, simply by using Arnault’s method to generate a
composite n that has the first 100 primes as non-witnesses. Indeed, using the method described in
Section 3.1.2 we can produce a 2329-bit composite that is pseudoprime to all prime bases up to
and including 541. See Appendix G for details.
4.8 Apple corecrypto and CommonCrypto Libraries
Apple’s CommonCrypto [App18a] library provides iOS and OS X cryptographic services. CommonCrypto
relies upon Apple’s corecrypto library [App18b] to provide implementations of low-level
cryptographic primitives.
Analysis Apple’s primality test can be found in corecrypto file ccz is prime.c, which contains
function ccz is prime. This function takes as input a number n to be tested and the number of
rounds of testing chosen by the user, t. This function then calls the function ccprime rabin miller
found in ccprime rabin miller.c. This in turn optionally checks that the number being tested
is odd, is not one of the first 256 primes, and not divisible by one of the first 119 primes (via a
gcd computation). It then performs min{t, 256} rounds of Miller-Rabin testing, selecting the bases
incrementally from a hard-coded list of the first 256 primes. The code documentation states that
when performing t = 32 rounds of testing, the probability of a false prime classification is estimated
as 2−64
.
CommonCrypto provides the primailty test CCBigNumIsPrime which calls ccz is prime provided
by corecrypto. However, the user has no choice over the number of rounds of testing t in this
case, as it is hard-coded to 16.
16
Pseudoprimes Since the bases are chosen deterministically based on the value of t, we can achieve
a failure rate of 100% with respect to that value t, simply by using the method of Section 3.1.2 to
produce a composite n that has the first t primes as non-witnesses. Such an n is in fact guaranteed
to be declared prime by ccz is prime, for any user input ≤ t. We give examples of composites n
that will be declared prime by corecrypto for t ≤ 256 and t ≤ 40 in Appendix I.
Since CommonCrypto forces ccz is prime to perform 16 rounds of testing, we can achieve a
100% success rate even more easily in this case. Indeed, both examples in Appendix I are guaranteed
to be declared prime in this case, as are the supplementary examples for a variety of bit-sizes
provided in Appendix H.
4.9 LibTomMath
LibTomMath v1.0.1 [Den18b] is an open source multiple-precision integer library with a number
theoretic toolkit.
Analysis. LibTomMath includes several methods for primality testing in the form of trial division,
Fermat tests, and Miller-Rabin tests. The latter two take a single base a and a number n to test as
arguments and return whether or not a is a witness or non-witness. The main primality test is
defined by the function mp prime is prime, which takes arguments n (the number to be tested),
and integer t with 1 ≤ t ≤ 256. It then performs some trial divisions (on a default of the first 256
primes) and then t rounds of Miller-Rabin. The selection of bases to be used is made similarly as
in Cryptlib: it simply picks incrementally from a list of hard-coded primes (but this time a list of
256 primes up to 1619 are used).
The documentation of LibTomMath (bn.pdf) discusses the number of rounds of Miller-Rabin
required with the statement: “Generally to ensure a number is very likely to be prime you have to
perform the Miller-Rabin with at least a half-dozen or so unique bases.” This is complemented with
a function mp prime rabin miller trials that gives the number of rounds needed to achieve an
error rate less than 2−96 based on the bit-size of the number tested (similar to that in OpenSSL
and [DLP93]) and a comment in the header file tommath.h above mp prime rabin miller trials
that states the probability of a false classification is no more than (1/4)t
.
Pseudoprimes. Since the bases are chosen deterministically based on the value of t, we can
achieve a failure rate of 100% simply by using the method of Section 3.1.2 to produce a composite
n that has the first 256 primes as non-witnesses; such an n is guaranteed to be declared prime by
mp prime is prime, for any value of t (including the t chosen by mp prime rabin miller trials
that describes an error rate less than 2−96). Appendix I provides a 7023-bit example of such an
n. Much smaller examples can be obtained if smaller values of t are guaranteed to be used; in
particular, we can easily obtain a 1024-bit example for t ≤ 40 (see also Appendix I).
4.10 LibTomCrypt
LibTomCrypt v1.18.1 [Den18a] is an additional cryptographic toolkit that shares many resources
with LibTomMath.
Analysis. The primality test in LibTomCrypt is called as isprime(n,t,result). It takes as
arguments an n to test and carries out t rounds of Miller-Rabin. The documentation of LibTomCrypt
advises that each round of Miller-Rabin reduces the probability of n being a pseudoprime by a
factor of 4, and therefore deduces that the overall error is at most (1/4)t
. LibTomCrypt supports
selection from three different big integer libraries at runtime.
If LibTomMath is chosen then isprime will call mp prime is prime as described in Section
4.9, passing on parameters n and t. If TomsFastMath [Den18c] is chosen then isprime will
call fp isprime ex, a function defined in the math library TomsFastMath that performs equivalent
testing as LibTomMath’s mp prime is prime. If GMP is selected then isprime will call
17
mpz probab prime p as described in Section 4.2. The value of t used by any of the three choices is
inherited from the original call to isprime, however if t = 0 the value is overwritten to t = 40.
Pseudoprimes. If either LibTomMath or TomsFastMath are selected, the pseudoprimes described
in Section 4.9 (see Appendix I) will always be declared prime by the primality test. If GMP is
selected we can apply the analysis in Section 4.2 to generate pseudoprimes (see Appendix C).
4.11 WolfSSL
WolfSSL 3.13.0 [Wol18b] (formerly CyaSSL) is a small SSL/TLS library targeted for use in
embedded systems. WolfSSL provides primality testing tools based on public domain TomsFastMath
0.10 [Den18c] and LibTomMath 0.38 [Den18b] functions.
Analysis. The primality test in WolfSSL is the function mp prime is prime which takes a number
n to be tested and the rounds of testing t as parameters. This function is directly taken from an
older version of LibTomMath, namely 0.38 [Den18b]. WolfSSL will use LibTomMath by default,
but can optionally be compiled to use TomsFastMath 0.10 [Den18c] at runtime. The primality
test in LibTomMath 0.38 is unchanged from that analysed in version 1.0.1 in Section 4.9. When
using TomsFastMath, mp prime is prime calls fp isprime which strips the user’s choice of t and
simply calls fp isprime ex with the hard-coded value of t = 8. The function fp isprime ex then
performs trial division (on a default of the first 256 primes) and then does 8 rounds of Miller-Rabin
using the first 8 primes as bases. It thus acts equivalently to mp prime is prime in LibTomMath,
but with t = 8.
Pseudoprimes. Since the testing in WolfSSL is in effect the same as that performed in LibTomMath
(but using only 8 rounds of Miller-Rabin when using TomsFastMath), the composite examples
given in Appendix I are also declared prime with 100% success.
4.12 Bouncy Castle
Bouncy Castle is a cryptographic library written in Java and C# [otBCI18]. The primality test
in Bouncy Castle Java is based on the BigInteger class from JDK as described in Section 4.4.
Bouncy Castle C# implements its own primality tests. We analyse Bouncy Castle C# version
1.8.2.
Analysis. The relevant function responsible for primality tests is located in the class BigInteger.
This class provides method IsProbablePrime which accepts certainty as a parameter. The method
then uses Miller-Rabin tests with t rounds, where t is computed as t = ((certainty − 1)/2) + 1.
In each round the base is selected using a secure random number generator (SecureRandom) which
is provided by the Bouncy Castle library.
The certainty parameter must always be provided to invocation of the IsProbablePrime
method. Therefore, a user choice completely determines how many Miller-Rabin rounds are
performed. For example, this method is directly used in the TlsDHUtilities class, which provides
Diffie-Hellman operations for TLS. When validating the incoming DH parameters, the
ValidateDHParameters method invokes isProbablePrime with certainty = 2. This results in
only a single Miller-Rabin test being carried out.
Pseudoprimes. We can produce composites n using any of the methods in Section 3.1; such n
meet the Monier-Rabin bound and so will pass Bouncy Castle’s primality testing with probability
(1/4)t with t as derived from certainty. Although there is no formal documentation, a comment
above the primality testing code indicates that the failure rate of this testing function should be
(1/2)certainty, and so the user’s choice of certainty is achieved.
18
4.13 Botan
Botan is a cryptographic library written in C++11 [Llo18a]. In addition to the crypto functionality
it offers a TLS client and server implementation. We analyse Botan 2.6.0.
Analysis. The relevant primality test implementation can be found in numthry.cpp, which
contains function is prime. This function first evaluates whether a tested number is divisible by
small primes up to 65521. It then performs Miller-Rabin primality tests with randomly chosen bases.
The source of randomness and the number of Miller-Rabin rounds are based on parameters passed
to the is prime function. The number of rounds is computed based on parameter prob and t is set
as (prob + 2)/2. Botan’s documentation is very clear on the distinction between testing numbers of
random and possibly adversarial origin. To distinguish the source, the function is prime contains
a boolean flag is random. If set, then the code uses [DLP93] to assign t based on the bit-size of
the number being tested, with a target failure rate less than 2−80
.
Pseudoprimes. As with Bouncy Castle, we can produce composite n using any of the methods
in Section 3.1; such n meet the Monier-Rabin bound and will pass Botan’s primality test with the
highest probability of (1/4)t where t is from the user’s choice of prob via t = (prob + 2)/2. In this
sense, the test’s guarantees match the user’s expectations.
4.14 Crypto++
Crypto++ 7.0 is an open source C++ cryptography library originally written by Wei Dai [Dai18].
Crypto++ has a variety of primality testing algorithms in nbtheory.cpp. These consist of trial division,
Fermat, Miller-Rabin and both strong and standard Lucas probable prime tests. Crypto++’s
primality testing function isprime is performing both Miller-Rabin and strong Lucas tests. Thus,
to fool it, we would need to find Baillie-PSW pseudoprimes (though the Miller-Rabin test is a
random base test, unlike that performed in Baillie-PSW). We do not currently know any such
pseudoprimes.
4.15 GoLang
The Go programming language (GoLang) 1.10.3 [Goo18] created at Google in 2009 is an open
source project including arbitrary-precision arithmetic and cryptographic functionality.
Analysis The relevant primality test implementation can be found in int.go, which contains
function ProbablyPrime(t). The parameter t defines the number of rounds of Miller-Rabin the
user wishes to perform. The function first performs trial division with a series of small primes,
then t rounds of Miller-Rabin (where one base is forced to be 2 and all other bases are chosen
pseudorandomly), and finally a Lucas probable prime test. Therefore the function is performing
a Baillie-PSW test. Before version 1.8, Go’s ProbablyPrime(t) function applied only the MillerRabin
tests. The documentation provided by GoLang makes it clear that the probability of the
function declaring a randomly chosen composite input to be prime is at most (1/4)t
. It also states
that “ProbablyPrime(t) is not suitable for judging primes that an adversary may have crafted to
fool the test”.
From an attack perspective it is interesting that the pseudorandom number generator used in
this primality test is seeded with the tested number n. Thus, an attacker can reliably predict the
pseudorandomly generated Miller-Rabin bases.
19
Pseudoprimes Since a Baillie-PSW test is being performed, we know of no composites that are
incorrectly declared prime by GoLang. However, for versions prior to 1.8 released in 2017, we
are able to exploit the insecure nature of the Miller-Rabin base selection to produce composite
numbers that are guaranteed to be declared prime with respect to a parameter t. Since this is the
same method GNU GMP uses to choose bases for Miller-Rabin, we can use the method described
in Section 4.2 to produce such composites. We give an example of a composite n that is always
declared prime for t ≤ 13 in Appendix J.
4.16 Mathematics Software Packages
We have also examined primality tests found in popular mathematics software packages and
computer algebra systems, namely: Magma, Maple, Maxima, SageMath, SymPy and Wolfram
Mathematica. We include these in our analysis since they might be relied upon by developers when
manually checking values in standards or code. Some of the libraries use deterministic tests for
proving primality, though most still rely on probabilistic methods when testing candidates larger
than 64 bits in size. Maple, Maxima and SymPy have dependencies on GMP and therefore inherit
the same issues with its primality test as discussed in Section 4.2; however they all also perform
Lucas tests in their latest versions, so this “cross contamination” does not result in exploitable
weaknesses. Full details are provided in Appendix L.
5 Application to Diffie-Hellman
Validating the correctness of Diffie-Hellman (DH) parameters is a vital step for verifying the
integrity of the key exchange. As mentioned in the introduction, since the DH parameter set
(p, q, g), with g ∈ Zp generating a group of order q, is public, they can originate from third-party
sources such as a server or a standard. An adept DH parameter validation function should check
that p, q are both prime and that p = kq + 1 for some integer k. It would also test that the given
generator g generates the subgroup of order q and that any received DH values lie in the correct
subgroup. A common choice is to set k = 2, and thus p is a safe-prime. For p that are not safe
primes, the group order q can be much smaller than p, offering performance improvements. The
security level is then based upon the bit-size of q, which must still be large enough to thwart the
Pohlig-Hellman algorithm for solving the Discrete Logarithm Problem (DLP), which for prime q
runs in time O(
√q). A common parameter choice is a 160-bit q with a 1024-bit p or a 256-bit q
with a 2048-bit p.
More precisely, the Pohlig-Hellman algorithm runs in time O(
√
t) where t is the largest prime
factor of q. Thus, an attacker armed with the ability to fool a primality test can supply a sufficiently
smooth composite q such that p = kq+1 is still prime. For example, if q is of the form (2x+1)(4x+1)
this leads to an attack on DLP with complexity 240 resp. 264 for the sizes mentioned above.
We stress, though, that none of the constructions for malicious composites in this work pose a
risk to protocols such as Telegram that insist on k = 2, i.e. which check both q = (p−1)/2 and p for
compositeness. For example, the construction of Section 3.1.1 would set q = (2x + 1)(4x + 1) and
yield p that is always divisible by 3; moreover q would not be smooth enough for Pohlig-Hellman to
pose a threat for parameters of cryptographically appropriate size. It is an interesting open question
to find a large, sufficiently smooth composite q passing a primality test with high probability such
that p = 2q + 1 is prime or passes a primality test, too.
We now discuss DH verification functions in various libraries. For each library, we apply the
analysis from Section 4 to check how robust these libraries are to attack. We note that the other
libraries discussed in Section 4 do not implement a higher-level function for verification of DH
parameters. Of course, this does not prevent an application from using these libraries to realise its
own verification function. Such an application would inherit the weaknesses and strengths of the
underlying library (when k 6= 2 is permitted). We give an example of this scenario for the GMP
library below. We close with a discussion of the important use case of SSL/TLS.
20
OpenSSL The file dh check.c contains the functions DH check params and DH check. The former
is a lightweight check that just confirms that p and g are ‘likely enough’ to be valid, by testing to
see if p is odd and 1 < g < p − 1. The latter function is more thorough and calls BN is prime ex
to test the primality of both p and q = (p − 1)/2. These primality tests are called with checks =
BN prime checks, therefore the rounds of Miller-Rabin are determined by Table 2. This means for
example that they will declare as prime with probability 1/16 composites n of the special form
n = (2x + 1)(4x + 1), for x odd and 2x + 1, 4x + 1 prime, when n has more than 1300 bits. Since
no private data is required, this testing function’s most likely use-case is checking Diffie-Hellman
parameters that have been generated by someone else (perhaps from an untrusted server or an
unknown origin) and therefore clearly misuses OpenSSL’s own primality testing functions.
However, since OpenSSL restricts parameter sets (p, q, g) to safe-primes p, efficient attacks are
not feasible. Using our current techniques, we cannot generate a set that will, with high probability,
pass primality testing on both p and q simultaneously and allow efficient solving of the DLP.
Bouncy Castle The validation of DH parameters in ValidateDHParameters extracts p, g from a
DH parameter set and then only checks the primality of p with 1 round of Miller-Rabin. We can
therefore produce composites that are accepted as DH moduli with probability 1/4. More seriously,
q is not given to the check function, so even with a prime p, the value of g can be chosen so that
it has small order, making Pohlig-Hellman as easy as desired. Even if g had large prime order,
the flexibility in choosing parameters would allow Lim-Lee small subgroup attacks, as explored
in [VAS+17].
Botan The Botan function is prime is used in the class DL Group (located in dl group.cpp) which
is also used for verifying DH parameters. This class contains the verify group function, which
can be invoked with boolean parameter strong. If strong is set to true, the is prime function
is invoked with prob=128. This results in t = 65 Miller-Rabin computations. Otherwise, prob=10
and 6 Miller-Rabin computations are performed. This test is performed for both p and q; the code
also checks that q|(p − 1) but does not insist on p being a safe prime.
Using the methods described in Section 3.1 we can find a q of 160-bits that passes 6 rounds of
MR testing with probability 1/4096 such that q has 2 or 3 prime factors. Then we can construct
1024-bit prime p as p = kq + 1 by using the flexibility in k, and a g that generates the subgroup
of size q. Since this p is indeed prime and q|(p − 1), all of Botan’s tests on the parameter set
(p, q, g) will pass with probability 1/4096 if strong is set to false. We can subsequently use the
Pohlig-Hellman algorithm to solve the DLP in the subgroup generated by g and break DH with
about 228 effort. See Appendix K for an example of such a parameter set.
GNU GMP The 256-bit integer q = (2x + 1)(4x + 1) with
x = 0x400286bac15132db85b1c936709f369b
passes 15 rounds of GMP’s primality test mpz is probab prime p; picking k = 21792 + 1254
produces the 2048 bit prime p = kq + 1. The resulting parameter set (p, q, g) would pass even fully
adept DH validation with certainty if the underlying primality testing was based on GNU GMP’s
code with the minimum recommended number of rounds of Miller-Rabin.
SSL/TLS We close by commenting on the situation for DH parameter testing in SSL/TLS. Here,
the server chooses parameters but only sends (p, g) to the client. There is no requirement that
p be a safe prime. This makes it difficult for clients to validate the DH parameters (they would
need to factor p − 1 and then try different divisors to determine the order of q) or to perform
group membership tests on received DH values. Consequently most clients perform only simple
sanity checks, e.g. checking that g /∈ {0, ±1}. This makes SSL/TLS vulnerable to a variety of
malicious DH parameter attacks, cf. [Won16,VAS+17], and in view of these, exhibiting composite
primes p that fool primality tests would be overkill for the SSL/TLS standards in their present
form. However, our work shows that even if clients tried to validate DH parameters by factoring
21
p − 1, finding the order of g and then testing it for primality, they could still fall foul of malicious
DH parameters. And if the SSL/TLS protocol were amended so that the server provides full DH
parameters, careful checks would still be needed. Finally we note that only a small number of fixed,
safe prime DH parameter sets are permitted in TLS 1.3. These were recently standardised in RFC
7919 [Gil16], alleviating these issues for future versions of the protocol.
6 Conclusion and Recommendations
Our work has explored primality testing in the adversarial setting and its impact for Diffie-Hellman
parameter testing. Our main finding is that leading libraries are not designed for this setting, and
therefore often vulnerable to accepting as prime composite inputs that are maliciously chosen, see
Table 1.
The need for careful distinction between non-adversarial (or random) and adversarial primality
testing is of course well understood in the cryptographic research community. However, this distinction
is not necessarily reflected and implemented in cryptographic libraries and their documentation.
As such, we can generally classify the underlying cause of the failure in prime classification accuracy
as non-consideration of the adversarial setting. More explicitly, we can categorise most failures in
terms of how the bases for Miller-Rabin are chosen, i.e. fixed base, predictable bases, insufficient
number of bases. Mini-GMP, JSBN, Cryptlib, LibTomMath, LibTomCrypt and WolfSSL all fail
due to the selection of bases from a fixed list, whereas GNU GMP and GoLang pre 1.8 both suffer
from predictable bases. OpenSSL, Libgcrypt, Botan and Bouncy Castle C# all have options to run
as many rounds of Miller-Rabin as the user desires, but either default to, or call the test (elsewhere
in the library) with too few rounds.
Based on our analysis, we make the following recommendations:
– In the absence of known pseudoprimes, we recommend that libraries switch to using the BailliePSW
primality test wherever possible. The negative impact on performance is moderate, and the
positive impact on security is significant. An existing benchmark for such a trade-off is found in
the documentation of the computer algebra system PARI/GP [The18b] (on which Sage bases its
primality testing functions). PARI/GP implements both a Miller-Rabin test with user-defined t
and a Baillie-PSW test and indicate [The18a] that their Baillie-PSW test is about as fast as
their Miller-Rabin test with t = 3.
– Libraries that wish to continue to use Miller-Rabin only (for example, to maintain a small
codebase) should use pseudorandom bases, cf. Cryptlib, LibTomCrypt, JavaScript Big Number,
WolfSSL. In particular, the bases should not depend only on n, cf. GNU GMP.
– We also recommend to default to worst-case bounds when picking the number of iterations and
only assume average-case behaviour when explicitly instructed to by the user. Specifically, we
recommend using 64 iterations to ensure that composite numbers are wrongly identified as being
prime with probability at most 2−128. The impact on performance of defaulting to worst-case
bounds should be minimal in the non-adversarial setting since testing can be aborted as soon as
a Miller-Rabin witness for compositeness is identified, and these are exceedingly common (as the
bounds of [DLP93] show). On the other hand, it’s precisely in the adversarial setting that the
worst-case bounds are needed. Adopting this recommendation may require changes to interfaces
to primality testing code.
– Designers of new protocols should avoid the pitfalls made in SSL/TLS, where DH parameter
validation is made impractical for clients. TLS 1.3 does so by fixing and requiring use of a small
collection of parameter sets.
Definitions in the cryptographic literature routinely start with “Let p be a prime . . . ” whereas
our work highlights that many implementations do not necessarily provide strong guarantees for
this assumption to hold. It is thus an interesting open question which other seemingly innocuous
assumptions concerning domain parameters in the literature can be undermined in a similar fashion.
22
Acknowledgements
Albrecht was supported by EPSRC grant EP/P009417/1. Massimo was supported by the EPSRC
and the UK government as part of the Centre for Doctoral Training in Cyber Security at Royal
Holloway, University of London (EP/K035584/1). Paterson was supported by EPSRC grants
EP/M013472/1, EP/K035584/1, and EP/P009301/1. Somorovsky was supported by the Horizon
2020 program under project number 700542 (FutureTrust).
We thank Christian Elsholtz for initial guidance on the mathematical literature and Ian Miers
for assistance with our analysis of OpenSSL. We are grateful to Brendan McMillion and Nick
Sullivan from Cloudflare for their generous provision of computing resources which enabled us to
find the examples in Section 4.2.
References
AKS04. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of mathematics,
pages 781–793, 2004.
AM93. A Oliver L Atkin and Fran¸cois Morain. Elliptic curves and primality proving. Mathematics of
computation, 61(203):29–68, 1993.
App18a. Apple Inc. Common crypto - Security Apple Developer. https://opensource.apple.com/
/source/CommonCrypto/, August 2018.
App18b. Apple Inc. corecrypto - Security Apple Developer. https://developer.apple.com/security/,
August 2018.
Arn95. Fran¸cois Arnault. Constructing Carmichael numbers which are strong pseudoprimes to several
bases. Journal of Symbolic Computation, 20(2):151–161, 1995.
Arn97. Fran¸cois Arnault. The Rabin-Monier theorem for Lucas pseudoprimes. Mathematics of Computation
of the American Mathematical Society, 66(218):869–881, 1997.
Bai13a. Robert Baillie. OEIS A217120: Lucas pseudoprimes. https://oeis.org/A217120, March 2013.
Bai13b. Robert Baillie. OEIS A217255: Strong Lucas pseudoprimes. https://oeis.org/A217255, March
2013.
BCP97. Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. J. Symbolic
Comput., 24, 1997. Computational algebra and number theory (London, 1993).
Ble05. Daniel Bleichenbacher. Breaking a cryptographic protocol with pseudoprimes. In Serge Vaudenay,
editor, PKC 2005, volume 3386 of LNCS, pages 9–15. Springer, Heidelberg, January 2005.
BW80. Robert Baillie and Samuel S Wagstaff. Lucas pseudoprimes. Mathematics of Computation,
35(152):1391–1417, 1980.
CMG+16. Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney,
Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham. A
systematic analysis of the juniper dual EC incident. In Edgar R. Weippl, Stefan Katzenbeisser,
Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 16, pages 468–479.
ACM Press, October 2016.
CNE+14. Stephen Checkoway, Ruben Niederhagen, Adam Everspaugh, Matthew Green, Tanja Lange,
Thomas Ristenpart, Daniel J. Bernstein, Jake Maskiewicz, Hovav Shacham, and Matthew
Fredrikson. On the practical exploitability of dual EC in TLS implementations. In 23rd USENIX
Security Symposium (USENIX Security 14), pages 319–335, San Diego, CA, 2014. USENIX
Association.
Cor18. Oracle Corporation. OpenJDK 10 Open Java Development Kit, 2018. openjdk.java.net.
CP06. Richard Crandall and Carl Pomerance. Prime numbers: a computational perspective, volume 182.
Springer Science & Business Media, 2006. pp.136-140.
Dai18. Wei Dai. Crypto++. https://www.cryptopp.com/, April 2018.
Den18a. Tom St Denis. LibTomCrypt. http://www.libtom.net/LibTomCrypt/, April 2018.
Den18b. Tom St Denis. LibTomMath. http://www.libtom.net/LibTomMath/, April 2018.
Den18c. Tom St Denis. TomsFastMath. http://www.libtom.net/TomsFastMath/, April 2018.
DLP93. Ivan Damg˚ard, Peter Landrock, and Carl Pomerance. Average case error estimates for the strong
probable prime test. Mathematics of Computation, 61(203):177–194, 1993.
DR08. T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246
(Proposed Standard), August 2008. Updated by RFCs 5746, 5878, 6176, 7465, 7507, 7568, 7627,
7685, 7905, 7919.
23
FGHT17. Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emmanuel Thom´e. A kilobit hidden
SNFS discrete logarithm computation. In Jean-S´ebastien Coron and Jesper Buus Nielsen,
editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, pages 202–231. Springer, Heidelberg,
April / May 2017.
fSidI17. Bundesamt f¨ur Sicherheit in der Informationstechnik. BSI TR-02102-1 Cryptographic Mechanisms:
Recommendations and Key Lengths. Technical guideline, Federal Office for Information Security,
January 2017.
Gil13. Jeff Gilchrist. Pseudoprime enumeration with probabilistic primality tests. http://gilchrist.
ca/jeff/factoring/pseudoprimes.html, August 2013.
Gil16. D. Gillmor. Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer
Security (TLS). RFC 7919 (Proposed Standard), August 2016.
Goo18. Google. The Go Programming Language. https://golang.org, July 2018.
Gt18. Torbjorn Granlund and the GMP development team. GNU MP: The GNU Multiple Precision
Arithmetic Library. https://gmplib.org, April 2018.
Gut18. Peter Gutmann. CryptLib. http://www.cryptlib.com/, April 2018.
H¨o16. Andreas H¨oglund. MPZ SPSP’s under GMP 5.0.1. http://www.hoegge.dk/gmp/gmp501.htm,
2016. Last accessed 2016-10-31.
Jac15. Dana Jacobsen. Pseudoprime Statistics, Tables, and Data. http://ntheory.org/pseudoprimes.
html, August 2015.
Jae93. Gerhard Jaeschke. On strong pseudoprimes to several bases. Mathematics of Computation,
61(204):915–926, 1993.
JP06. Marc Joye and Pascal Paillier. Fast generation of prime numbers on portable devices: An update.
In Louis Goubin and Mitsuru Matsui, editors, CHES 2006, volume 4249 of LNCS, pages 160–173.
Springer, Heidelberg, October 2006.
JPV00. Marc Joye, Pascal Paillier, and Serge Vaudenay. Efficient generation of prime numbers. In
C¸ etin Kaya Ko¸c and Christof Paar, editors, CHES 2000, volume 1965 of LNCS, pages 340–354.
Springer, Heidelberg, August 2000.
Koc05. Werner Koch. Github - libgcrypt changes to default primality test. https:
//github.com/gpg/libgcrypt/commit/78a84338cb36748f17cc444b17ab7033ce384c34#
diff-96a06fc4d0080caec00d423ca08a6c86, April 2005.
Koc18. Werner Koch. Libgcrypt. https://gnupg.org/software/libgcrypt/index.html, April 2018.
Lib18. LibTomMath. Pull request - added Fips 186.4 compliance, an additional strong Lucas-Selfridge
(for BPSW). https://github.com/libtom/libtommath/pull/113, August 2018.
Lit09. Dwayne C. Litzenberger. PyCrypto 2.1.0. https://pypi.python.org/pypi/pycrypto/2.1.0,
December 2009.
LK08. M. Lepinski and S. Kent. Additional Diffie-Hellman Groups for Use with IETF Standards. RFC
5114 (Informational), January 2008.
LLC18. Telegram FZ LLC. Telegram Messenger. https://telegram.org, 2018.
Llo18a. Jack Lloyd. Botan. https://github.com/randombit/botan, August 2018.
Llo18b. Jack Lloyd. Botan pull request - add Lucas test from FIPS 186-4. https://github.com/
randombit/botan/pull/1636, August 2018.
Mac17. Macsyma group. Maxima 5.41.0, Documentation, 2017. Available at http://maxima.
sourceforge.net/docs/manual/maxima_10.html.
Mac18. Macsyma group. Maxima 5.41.0, a Computer Algebra System, 2018. Available at http://maxima.
sourceforge.net/index.html.
Mar16. Marcel Martin. PRIMO–Primality Proving, 2016. https://www.ellipsa.eu.
McC97. Jud McCranie. OEIS A014233: Smallest odd number for which Miller-Rabin primality test on bases
less than or equal to the n-th prime does not reveal compositeness. https://oeis.org/A014233,
Feb 1997.
Mil75. Gary L Miller. Riemann’s hypothesis and tests for primality. In Proceedings of seventh annual
ACM symposium on Theory of computing, pages 234–239. ACM, 1975.
Mon80. Louis Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms.
Theoretical Computer Science, 12(1):97–108, 1980.
MVOV96. Alfred J Menezes, Paul C Van Oorschot, and Scott A Vanstone. Handbook of applied cryptography.
CRC press, 1996.
Nar14. Shyam Narayanan. Improving the Speed and Accuracy of the Miller-Rabin Primality Test. MIT
PRIMES-USA, 2014. https://math.mit.edu/research/highschool/primes/materials/2014/
Narayanan.pdf.
24
Nic16. Thomas Nicely. GNU GMP mpz probab prime p pseudoprimes.
http://www.trnicely.net/misc/mpzspsp.html, 2016. Last accessed 2016-10-31.
NSS+17. Mat´us Nemec, Marek S´ys, Petr Svenda, Dusan Klinec, and Vashek Matyas. The return of coppersmith’s
attack: Practical factorization of widely used RSA moduli. In Bhavani M. Thuraisingham,
David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 17, pages 1631–1648. ACM Press,
October / November 2017.
OP18a. GitHub The OpenSSL Project. Pull request - Increase number of MR tests for RSA prime
generation #6075. https://github.com/openssl/openssl/pull/6075, August 2018.
OP18b. The OpenSSL Project. OpenSSL: The Open Source toolkit for SSL/TLS. www.openssl.org,
May 2018.
otBCI18. Legion of the Bouncy Castle Inc. The Bouncy Castle Crypto Package For C Sharp, 2018.
https://github.com/bcgit/bc-csharp.
Pom84. Carl Pomerance. Are there counter-examples to the Baillie-PSW primality test. Dopo Le Parole
aangeboden aan Dr. A. K. Lenstra., 1984.
PSW80. Carl Pomerance, John L Selfridge, and Samuel S Wagstaff. The pseudoprimes to 25 · 109
.
Mathematics of Computation, 35(151):1003–1026, 1980.
Pub13. Federal Information Processing Standards Publication. FIPS PUB 186-4 Digital Signature
Standard (DSS). Standard, National Institute of Standards and Technology, Gaithersburg, MD,
July 2013.
Rab80. Michael O Rabin. Probabilistic algorithm for testing primality. Journal of number theory,
12(1):128–138, 1980.
RI18. Wolfram Research, Inc. Mathematica, Version 11.3, 2018. Champaign, IL, 2018.
Rie16. Gerhard Rieger. Socat security advisory 7 - Openwall oss-security mailing list, 2016. http:
//www.openwall.com/lists/oss-security/2016/02/01/4.
S
+17. William Stein et al. Sage Mathematics Software Version 8.2. The Sage Development Team, 2017.
Available at http://www.sagemath.org.
Sta05. British Standards. ISO/IEC 18032:2005 Information technology – Security techniques – Prime
number generation. Standard, International Organization for Standardization, January 2005.
Str16. Falko Strenzke. An analysis of OpenSSL’s random number generator. In Marc Fischlin and
Jean-S´ebastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 644–669.
Springer, Heidelberg, May 2016.
Sym17a. SymPy. SymPy GitHub repository. Available at https://github.com/sympy/sympy/commit/
9e35a94eceaff73b350794dcc70b4a412dc2f6e6#diff-e20bc128d13486b598a04fce77584900,
2017.
Sym17b. SymPy Development Team. SymPy: Python library for symbolic mathematics, 2017.
The18a. The PARI Group, Univ. Bordeaux. PARI/GP Frequently Asked Questions, 2018. available from
http://pari.math.u-bordeaux.fr/faq.html#primetest.
The18b. The PARI Group, Univ. Bordeaux. PARI/GP version 2.9.0, 2018. available from http:
//pari.math.u-bordeaux.fr/.
VAS+17. Luke Valenta, David Adrian, Antonio Sanso, Shaanan Cohney, Joshua Fried, Marcella Hastings,
J. Alex Halderman, and Nadia Heninger. Measuring small subgroup attacks against Diffie-Hellman.
In NDSS 2017. The Internet Society, February / March 2017.
Wat17. Waterloo Maple (Maplesoft). Maple Version 2017, 2017. Available at https://www.maplesoft.
com/products/Maple/.
Wei18. Eric W. Weisstein. Baillie-PSW primality test from MathWorld- a Wolfram web resource.
http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html, April 2018.
Wol18a. WolfSSL Inc. Pull request - Prime Number Testing. https://github.com/wolfSSL/wolfssl/
pull/1665, August 2018.
Wol18b. WolfSSL Inc. WolfSSL. https://www.wolfssl.com/wolfSSL/Home.html, April 2018.
Won16. David Wong. How to Backdoor Diffie-Hellman. Cryptology ePrint Archive, Report 2016/644,
2016. https://eprint.iacr.org/2016/644.
Wu17. Tom Wu. JSBN: RSA and ECC in JavaScript. http://www-cs-students.stanford.edu/~tjw/
jsbn/, April 2017.
A An Overview of Arnault’s Method
Arnault’s method generates n of the form n = p1p2 . . . ph where the pi are distinct odd primes such
that n is pseudoprime to a set of t prime bases {a1, a2, . . . , at}. By [Arn95, Lemma 3.2] we know
25
that if gcd(a, n) = 1 and 
a
pi

= −1 for all 1 ≤ i ≤ h, then a will be a Miller-Rabin non-witness
with respect to n (this set of conditions is sufficient but not necessary for a to be a Miller-Rabin
non-witness with respect to n).
Now, by Gauss’s law of quadratic reciprocity, we know that, for any prime p,

a
p

can be
determined from
p
a


and the values of a and p taken modulo 4. This in turn means that, for each
a, we can compute the set Sa of possible non-residues mod 4a of potential primes p. That is, we
can compute the set Sa satisfying

a
p

= −1 ⇐⇒ p mod 4a ∈ Sa.
Arnault’s method selects p1 and then determines the other pi from equations of the form pi =
ki(p1 − 1) + 1 where the ki are values also chosen as part of the method (with k1 = 1). This
is done so as to ensure that the resulting n = p1p2 . . . ph is a Carmichael number. But the
conditions 
a
pi

= −1 for all 1 ≤ i ≤ h imply that, for each a ∈ A and each 1 ≤ i ≤ h we have
ki(p1 − 1) + 1 ∈ Sa. Rewriting this, we obtain that:
p1 mod 4a ∈
\
h
i=1
k
−1
i
(Sa + ki − 1), (5)
where k
−1
i
(Sa + ki − 1) denotes the set {k
−1
i
(s + ki − 1) mod 4a|s ∈ Sa}. This gives a set of
conditions on the value of p1 modulo 4a for each a ∈ A; typically a few candidates for p1 mod 4a
remain for each value of a. By selecting one of these candidates za for each a ∈ A and using the
CRT, the conditions can be combined into a single condition on p1 modulo m = lcm(4, a1, . . . , at).
The ki values must be selected so that the sets on the right of (5) are non-empty; typically, they are
set to small primes larger than the maximum of the a ∈ A so that k
−1
i
exists mod 4a for each a.
Arnault’s method then brings into play other restrictions on p1 mod ki for each i = 2, . . . , h.
These result from the requirement that n be a Carmichael number. We omit the full details, but,
for example, when h = 3, the additional restrictions can be written as:
p1 = k
−1
3 mod k2 and p1 = k
−1
2 mod k3
Making the ki co-prime to each other and to the a ∈ A ensures that another application of the
CRT can be made to incorporate these conditions. The end result is a single condition of the form:
p1 = z mod lcm(4, a1, . . . , at, k2, . . . , kh)
where z is a fixed value determined by the choice of the za values and the additional restrictions.
Finally, the method repeatedly generates candidates for p1 satisfying the above constraint and
uses the equations pi = ki(p1 − 1) + 1 to determine the other pi
. The method is successful for a
given p1 if all of the resulting p1, . . . , ph are prime.
Evidently, the method is complex and not guaranteed to succeed on every attempt for a given
set A. However, it can be iterated with different choices of the ki until the sets on the right of (5) are
non-empty; moreover a back-tracking approach can be used to select the za values to speed-up the
entire process of constructing p1. The density of all-prime solutions (p1, . . . , ph) amongst all possible
candidates (p1, . . . , ph) satisfying p1 = z mod lcm(4, a1, . . . , at, k2, . . . , kh) and pi = ki(p1 − 1) + 1
for i = 2, . . . , h can be estimated using standard heuristics concerning the distribution of primes of
size L = lcm(4, a1, . . . , at, k2, . . . , kh); it is roughly 1/(logh
(L) ·
Ph
i=2 log(ki)).
Notice that, the larger the set A, the larger the modulus L in the condition determining p1 will
be. Thus, if A contains many bases, then larger pi and hence larger n will tend to result. Moreover,
all-prime solutions will become less dense. As an example, when analysing the primality test in
Maple V.2, Arnault [Arn95] considers h = 3 so n = p1p2p3 and A = {2, 3, 5, 7, 11} (so t = 5); he
works with k2 = 13 and k3 = 41 and arrives finally at the condition:
p1 = 827443 mod 4924920.
26
For p1 = 286472803, this yields a 29-decimal digit composite passing Maple’s fixed-base Miller-Rabin
primality test.
We give a short example of the method described for an n of the form n = p1p2p3 for which the
first 10 primes are Miller-Rabin non-witnesses. That is, we target A = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
We start by generating the set Sa of residues modulo 4a of primes p such that 
a
p

= −1 for
each base a ∈ A. Table 3 gives the sets Sa for our chosen set A.
Table 3. Values a and subsets Sa of residues modulo 4a of primes p such that 
a
p

= −1.
a Sb
2 {3, 5}
3 {5, 7}
5 {3, 7, 13, 17}
7 {5, 11, 13, 15, 17, 23}
11 {3, 13, 15, 17, 21, 23, 27, 29, 31, 41}
13 {5, 7, 11, 15, 19, 21, 31, 33, 37, 41, 45, 47}
17 {3, 5, 7, 11, 23, 27, 29, 31, 37, 39, 41, 45, 57, 61, 63, 65}
19 {7, 11, 13, 21, 23, 29, 33, 35, 37, 39, 41, 43, 47, 53, 55, 63, 65, 69}
23 {3, 5, 17, 21, 27, 31, 33, 35, 37, 39, 45, 47, 53, 55, 57, 59, 61, 65, 71, 75, 87, 89}
29 {3, 11, 15, 17, 19, 21, 27, 31, 37, 39, 41, 43, 47, 55, 69, 73, 75, 77, 79, 85, 89, 95, 97, 99, 101, 105, 113}
We now set k2 = 41 and k3 = 101; these are coprime to all a ∈ A. We find subsets of the Sa
that meet the requirement:
p1 (mod 4a) ∈
\
h
i=1
k
−1
i
(Sa + ki − 1).
This gives us a set of residues modulo 4a for each a ∈ A that p1 must satisfy. We give an example
of this for the first 10 primes in Table 4.
a
Th
i=1 k
−1
i
(Sa + ki − 1) Modulo
2 {3, 5} 8
3 {7} 12
5 {3, 7, 13, 17} 20
7 {15} 28
11 {21, 23} 44
13 {21, 47} 52
17 {5, 29, 31, 39, 63, 65} 68
19 {33, 37, 39, 47, 69} 76
23 {31, 47, 57, 87, 89} 92
29 {19, 37, 41, 55, 77, 95, 99, 113} 116
Table 4. Values a and the sets Th
i=1 k
−1
i
(Sa + ki − 1) when k2 = 41 and k3 = 101.
We then need to make a choice of one residue za per set. This choice is arbitrary, but we note
that not all combinations of choices will lead to a solution. We give an example of a good set of
choices in Table 4 in bold.
We then have two additional conditions to add, based on our choice of the ki values. These can
be written as:
p1 = k
−1
3 mod k2 and p1 = k
−1
2 mod k3
In our example, we chose k1 = 41 and k2 = 101 which gives us:
p1 ≡ 28 (mod 41) and p1 ≡ 32 (mod 101).
27
We can then use the Chinese Remainder Theorem to simultaneously solve for the 10 conditions
implied by the bold entries in Table 4 and the two conditions above. In this case, we have the
solution:
p1 ≡ 36253030834483 mod 107163998661720.
The prime
p1 = 142445387161415482404826365418175962266689133006163
satisfies this condition, and yields primes
p2 = 5840260873618034778597880982145214452934254453252643
p3 = 14386984103302963722887462907235772188935602433622363
such that the product n = p1p2p3 is a 512-bit number that is a Miller-Rabin pseudoprime to the
bases 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.
B A Large strong Lucas Pseudoprime
Using our SAGE implementation of the method as described in Section 3.2.1, we construct an n of
the form n = p1p2p3, where pi = ki(p1 + 1) − 1 with (k2, k3) = (31, 43) and
p1 = 2576
· 0x0000000000000000000000bc508ae6dacc43b138c0e9f22d
+ 2384
· 0xfb99b146bedd0ac93f84e8cfe2780a881fdbad85918a6b75
+ 2192
· 0xbd3af841123bad7438fe08c5433ec8b5fa7b0a1b149876bf
+ 20
· 0x5af73cd9a608317066029e0cff4171ce336ff0b666344757.
Then n = p1p2p3 is a 2050-bit strong Lucas pseudoprime for Selfridge’s Method A of parameter
selection.
C Constructing GMP Pseudoprimes
Recall that we work with candidates x of the form x = kM + 189, and then consider n =
(2x + 1)(4x + 1); we select x so that 2x + 1 and 4x + 1 are both prime, and we select M as a
product of the first ` primes from the set P = {2, 3, . . . , 373}. We justify this construction here.
First, note that 2x + 1 = 2kM + 379 while 4x + 1 = 4kM + 757, where both 379 and
757 are prime. Considering 2x + 1 modulo each of the ` prime factors p in M, we see that
2x+ 1 = 379 mod p 6= 0 mod p because p < 379; similarly, we obtain 4x+ 1 = 757 mod p 6= 0 mod p.
Hence no such p divides either 2x + 1 or 4x + 1, so these numbers are not divisible by any of
the primes in the product M (i.e. the first ` primes). For this reason, with random choices of
k and with x = kM + 189, it follows that 2x + 1 and 4x + 1 are more likely to be prime than
they would be for random choices of x. An analysis of the effect involves an application of the
inclusion-exclusion principle to determine how many numbers are “sieved out” by the process. We
omit the full analysis here, but note that, for numbers of cryptographically interesting size and
with ` = 69 that we use in the construction of our 1024-bit example for n, the effect is to increase
the probability of primality for each number from 1/ ln x to roughly 5/ ln x. Since we have two
numbers 2x + 1, 4x + 1 whose primality behaves largely independently over the choice of x, this
yields a 25-fold improvement in the performance of our approach over the direct approach of trying
random x values.
Next, we consider the Fermat test on n with base a = 210, assuming the factors 2x + 1
and 4x + 1 are prime. This test computes the value of a
n−1 mod n and compares it to 1. Now
n − 1 = (2x + 1)(4x + 1) = 8x
2 + 6x = 2x(4x + 3), so we obtain:
a
n−1 = (a
4x+3)
2x = 1 mod 2x + 1
28
and
a
n−1 = a
8x
2+6x = (a
2x+1)
4x
· a
2x = 1 · a
2x = a
2x mod 4x + 1.
Here, we have made repeated use of Fermat’s Little Theorem (which states that a
p−1 = 1 mod p
for prime p and a 6= 0 mod p).
It follows that a
n−1 = 1 mod n if and only if a is a quadratic residue modulo 4x + 1. It follows
that n passes a Fermat test to base a for roughly half of the possible bases a (since roughly half of
the values a mod n are quadratic residues mod4x + 1).
Now we use the fact that a = 210 = 2 · 3 · 5 · 7 to write:

210
4x + 1
=

2
4x + 1  3
4x + 1  5
4x + 1  7
4x + 1
.
Since M is even, we can write 4x + 1 = 8k(M/2) + 757 = 5 mod 8, hence ( 2
4x+1 ) = −1. Also
(
3
4x+1 ) = ( 4kM+757
3
) = ( 757
3
) = ( 1
3
) = 1, where we use Gauss’s Law of Quadratic Reciprocity and
3|M. Similarly, we obtain ( 5
4x+1 ) = −1 and ( 7
4x+1 ) = 1. Combining everything, we finally get

210
4x + 1
= (−1) · 1 · (−1) · 1 = 1.
We conclude that the Fermat test for n of the given form with base a = 210 always passes.
D A Pseudoprime for Mini-GMP
Using our SAGE implementation of the composite fixed base technique as described in Section 3.1.4,
we construct an n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1 with (k2, k3) = (10937, 11257)
and
p1 = 2960
· 0x00000000000000000000000000000000000000000002e394
+ 2768
· 0x1a2fe4aa9e66358347f63732494d08635ccc9ae0a3c17764
+ 2576
· 0xa8e266f4d26758ab804a702c235f63b1e109a81fc007f94b
+ 2384
· 0xec5158f231a30b1cbf96a7fc444c09be62f5a809f049cc5d
+ 2192
· 0xe94b84275c38885c9b61a6bdc44111501527722a8ac87ea2
+ 20
· 0xa5d4498caa2d9d07b34001a508fa53063991206268c547d7.
This yields a 2960-bit composite n that is guaranteed to pass any number up to and including
t = 101 rounds of Mini-GMP’s primality test.
E Java Code Listing
We include the source code of the function primeToCertainty from the class java.math.BigInteger.
Listing 1.1. OpenJDK10 java.math.BigInteger function primeToCertainty
boolean p r im eToC e r ta in ty ( in t c e r t a i n t y , Random random ) {
in t rounds = 0 ;
in t n = (Math . min ( c e r t a i n t y , I n t e g e r .MAX VALUE−1)+1) / 2 ;
// The r e l a t i o n s h i p between th e c e r t a i n t y and th e number o f rounds
// we p er form i s g i v e n i n th e d r a f t s t and a rd ANSI X9 . 8 0 , ”PRIME
// NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES” .
in t s i z e I n B i t s = t h i s . b i t L en g th ( ) ;
i f ( s i z e I n B i t s < 1 0 0 ) {
rounds = 5 0 ;
rounds = n < rounds ? n : rounds ;
return p a s s e sM i l l e r R a b i n ( rounds , random ) ;
}
i f ( s i z e I n B i t s < 2 5 6 ) {
29
rounds = 2 7 ;
} e l s e i f ( s i z e I n B i t s < 5 1 2 ) {
rounds = 1 5 ;
} e l s e i f ( s i z e I n B i t s < 7 6 8 ) {
rounds = 8 ;
} e l s e i f ( s i z e I n B i t s < 1 0 2 4 ) {
rounds = 4 ;
} e l s e {
rounds = 2 ;
}
rounds = n < rounds ? n : rounds ;
return p a s s e sM i l l e r R a b i n ( rounds , random ) && pass esLu casL ehm er ( ) ;
}
F An Example Pseudoprime for JSBN
Using our SAGE implementation of the method as described in Section 3.1.2 with A containing
the first 1000 primes, we construct a 4279-bit n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1
with (k2, k3) = (1013, 2053) and
p1 = 21344
· 0x0000000000000000000000000000083dda18eb04a7597ca3
+ 21152
· 0xc6bc877df8a08eec6725fa0832cba270c42adc358bc0cf50
+ 2960
· 0xc82cb10f2733c3fb8875231fc1498a7b14cb675fac1bf3c5
+ 2768
· 0x127a76fc11e5d20e27940c95ceba671fe1c4232250b74cbd
+ 2576
· 0xf8448c90321513324c0681afb4ba003353b1afb0f1e8b91c
+ 2384
· 0x60af672a5a6f4d06dd0070a4bc74e425f3eae90379e57754
+ 2192
· 0x82d26e80e247464a4bb817dfcf7572f89f8b9cacd059b584
+ 20
· 0x0e4389c8af84f6a6ea15a3ea5d62cb994b082731ba4cde73.
This produces an n that is guaranteed to be declared prime by JSBN’s primality test for any
certainty parameter t.
G An Example Pseudoprime for Cryptlib
Using our SAGE implementation of the method as described in Section 3.1.2 with A containing
the first 100 primes, we construct a 2315-bit n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1
with (k2, k3) = (641, 677) and
p1 = 2576
· 0x24a027808260908b96d740bef8355ded63f6edb7f70de9a9
+ 2384
· 0xb99c408f131cef3855b4b0aea6b17a4469ed5a7ec8b2be62
+ 2192
· 0x66c3a9eae83a6769e175cb2598256da977b9e191b9b847a7
+ 20
· 0xe2cf4750d9bc2d64ccd3406f5db662c22c3fc65e3c56eff3.
This n is declared prime for any valid number of rounds t of testing performed by Cryptlib’s
primality test.
H Example Pseudoprimes for Apple CommonCrypto
Using our SAGE implementation of the method as described in Section 3.1.2 with A containing the
first 16 primes, we construct three compsites n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1
with (k2, k3) = (113, 173) where:
p1 = 0x32972d4e607a45f57d7144df60a7abf8b473a1680b
30
produces a 512-bit n,
p1 = 2192
· 0x00000000000151452e0a832f27b9eead0000000000000000
+ 20
· 0x000000000000000000000000aff3796792e7ceb8d55206a3
produces a 1024-bit n, and
p1 = 2576
· 0x000000000000000000000032972d4e607a45f57d66c00000
+ 20
· 0x000000000000000000000001f2a7b5c6a50fc1e38aae911b
produces a 2048-bit n.
These composites are always declared prime by CommonCrypto.
I Example Pseudoprimes for Apple corecrypto and CommonCrypto,
LibTomMath, LibTomCrypt and WolfSSL
Using our SAGE implementation of the method as described in Section 3.1.2 with A containing
the first 256 primes, we construct a 7023-bit n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1
with (k2, k3) = (2633, 5881) and
p1 = 22304
· 0x00000000000000000000000000000000000000001e46d6a8
+ 22112
· 0x4d42d684ddb3415e871b661303b1c60f0388dfb9e525f8bc
+ 21920
· 0x51c9de3c9f45627608de2f75dee580d9d4d97cab6fa86dad
+ 21728
· 0x9e6bbfd721f297472480a9bed9508aa884bda9dc56833752
+ 21536
· 0xfac8e89f413a9517d14731277148789987806654a8723593
+ 21344
· 0xa452f960facc9b65f6962cb26131b42650c29c8735083c7e
+ 21152
· 0x6c3a220d77d1cbe7f9628885a7b79465287d4b02ad546007
+ 2960
· 0x1d43306a8813836de5ccd162fbeca4f117552dba01975451
+ 2768
· 0x2f7684e32b0377e76f87b96906f8fa276381db612f76c2c7
+ 2576
· 0xdd97ab4380042c991a4719884377c70065a3614237a41289
+ 2384
· 0x24a1017fbb529443b0ad43c5424753db5b518cee5a1fcd87
+ 2192
· 0xea038ffcad33380db1d89cd4e0b15b480cf0c62e8999924d
+ 20
· 0x0284af806081ea106f35f85a664456166b864650ef034cf3.
This n is declared prime for any valid number of rounds t for the Apple corecrypto and CommonCrypto,
LibTomMath, LibTomCrypt and WolfSSL libraries.
Also using the method as described in Section 3.1.2 but now with A containing the first 40
primes, we can construct a 1024-bit n of the form n = p1p2p3, where pi = ki(p1 − 1) + 1 with
(k2, k3) = (233, 241) and
p1 = 2192
· 0x000000000000e17516504450e648b6aedb0c0784e17dda33
+ 20
· 0x63e1956a843076a9e5b6d15a819cf0907a96154d47662d0b.
This n is guaranteed to be declared prime by mp prime is prime with t ≤ 40, and therefore also
guaranteed to be declared prime by mp prime is prime as in LibTomCrypt 1.18.1 and WolfSSL
3.13.0 for the same values of t. The same applies for Apple corecrypto and CommonCrypto.
J An Example Pseudoprime for GoLang pre-1.8
Using the method described in Section 4.2, we construct a 1024-bit composite n that is declared
prime by GoLang’s primality test in versions prior to 1.8 with 100% success for t ≤ 13. We take
31
n = 2960
· 0x00000000000000000000000000000000ff7d428a8a9f9ffc
+ 2768
· 0x2ea178501115ec855f1154c054f5f67e15967a139a92fe15
+ 2576
· 0xddf2c49b044820ea8c58551b74f81b45b116da4e1f11b926
+ 2384
· 0x93e0cdc58006bc2052eb9b2fc32c71dd041d1907225e2814
+ 2192
· 0xebe18736f626fea57c965b67b296a6461455226b39aba263
+ 20
· 0x3faeb483847a715c6a01d8d0e401a4aaf8f3d22121fd142f.
K An Example of a Malicious DH Parameter Set for Botan
Using our SAGE implementation of the method in Section 3.1.3, we construct a 160-bit q of the
form q = q1q2q3, where qi = ki(q1 − 1) + 1 with (k2, k3) = (61, 101) and q1 = 537242417098003.
This q is declared prime with probability 1/4096 by Botan’s verify group function. By setting
k = 2864 + 134 in p = kq + 1 we obtain a prime p, and thus by setting the generator g as:
g = 2960
· 0x0000000000000000000000000000000075ead4f9fa60a06e
+ 2768
· 0x0787a1e0708f5e2055b2899691f7dd73303d5643e57b1636
+ 2576
· 0x66ce328086bd6a0df756175c35549ba7a5ffe517036c0ef1
+ 2384
· 0x44a9542f698255efb66cda28b0b8a5ebebf2c0892f8147d3
+ 2192
· 0x72083822a36098addcd30a1767ccefaae65d1dcd6b45de92
+ 20
· 0x09047326d40b622af6a76218664ba3df13eb0fead02d772a
we obtain a parameter set (p, q, g) such that g generates the subgroup of order q. The probability
that this set is accepted by Botan’s verify group function is 1/4096. The DLP in the subgroup
generated by g can be solved using the Pohlig-Hellman algorithm over each of the 49-bit, 55-bit
and 56-bit factors q1, q2 and q3 of q. The cost is dominated by the largest prime factor, and is
approximately 228 operations.
L Details of Mathematics Software Packages
L.1 Magma
Magma V2.23-9 [BCP97] is a mathematical software package designed for computations in algebra,
number theory, algebraic geometry and algebraic combinatorics.
Analysis. Magma provides a primality testing function that can either invoke a primality proving
algorithm, or what they call a probable-primality test, depending on the arguments given when
called. The main function call for primality testing is IsPrime(n:- Proof). The more rigorous
method of primality proving is based on an implementation of the ECPP (Elliptic Curve Primality
Proving) method [AM93] is used by default, unless the number tested is greater than 34 × 1013
or the parameter Proof = False. In this case, the probable-primality test IsProbablePrime is
instead called. By default, this consists of 20 rounds of Miller-Rabin with random bases. By setting
the optional parameter Bases to some value B, the number of bases used is B instead of 20.
Pseudoprimes. The pseudoprimes generated in Section 3 attempt only to overcome probabilistic
primality testing and are not designed to overcome primality proving methods such as ECPP.
However, if the parameters are set to invoke the probable-primality test with default parameters,
then composites generated by the methods in Section 3.1 have a probability of 2−40 of being falsely
declared prime. This probability is correctly alluded to as being worst-case by the documentation
given for this function.
32
L.2 Maple
Maple 2017 [Wat17] is a computer algebra system developed by Maplesoft, that provides a general
purpose software tool for mathematics, data analysis, visualisation, and programming.
Analysis. The primality test in Maple is called as isprime(n) on a candidate n to be tested.
Documentation states that “It returns false if n is shown to be composite within one strong
pseudo-primality test and one Lucas test. It returns true otherwise”. The function begins with
some trial division on a series of small primes before calling gmp isprime(n). If the result of
gmp isprime(n) is 1 (i.e. the number is “probably prime”) and the candidate n being tested is
greater than 5 × 109 ≈ 2
33, then isprime will go on to perform a Lucas test on n. In all other
cases, the Lucas test is omitted.
Although we cannot directly inspect the code of gmp isprime(n) (since Maple is proprietary
software) we are able to reverse-engineer this function by calling it on our own input n and
assessing how it performs. Maple’s documentation states that it performs a Miller-Rabin test
and uses GMP for this function, yet since there is no other code indicative of a Miller-Rabin
test in gmp isprime(n), we deduce that Maple is calling GMP’s function mpz probab prime p-
(n, reps). Since gmp isprime(n) takes only a single argument, we inferred that Maple passes a
hardcoded value of reps to GMP. We were able to verify that the value of reps is actually 5. We
did this by using the methods described in Section 4.2 to generate composite numbers of various
bit-sizes that are declared prime by mpz probab prime p (n, reps) for reps = 1,2,3,4,5. For
composites that can only pass at most reps = 4, Maple’s gmp isprime correctly identifies these as
composite. But for composites that pass reps = 5, the function falsely declares them to be prime.
Pseudoprimes. When testing numbers n ≤ 5×109
, isprime acts as a deterministic version of the
Miller-Rabin test. We have verified this by calling mpz probab prime p(n,5) for all n ≤ 5 × 109
and comparing the results to a list of primes below 5 × 109
. The different sets of bases that GMP
chooses for each n are such that there are no composites below this threshold that are declared
prime by mpz probab prime p with reps > 3. However, any change made to the (flawed) way
GMP currently chooses its bases for testing could actually make Maple’s isprime function less
accurate (and no longer deterministic) for n ≤ 5 × 109
!
To fool Maple’s primality testing for numbers larger than 5 × 109
, we would need a composite
n passing a Lucas test and 5 rounds of Miller-Rabin testing. We do not currently know any such n.
L.3 Maxima
Maxima 5.41.0 [Mac18] is a free, open source computer algebra system developed by the Macsyma
group. Maxima is a general-purpose system including tools for a variety of mathematical functions
and the manipulation of symbolic and numerical expressions.
Analysis. The primality test supplied by Maxima is the function primep(n). When testing an n
less than 341550071728321 (≈ 2
49) a deterministic version of Miller-Rabin’s test is used. This is
achieved by calling repeated rounds of Miller-Rabin tests with a set of bases for which it has been
verified that no composites are falsely declared prime. These are as defined in [Jae93,McC97], and
therefore can in general be used to create a deterministic test for numbers less than 264
.
When testing an n bigger than 341550071728321, primep(n) performs 25 random base MillerRabin
tests, then conducts one Lucas test. The source Maxima uses for base selection is then
provided by the Maxima random number generator, which is an implementation of Mersenne
twister MT 19937 [Mac17].
Maxima’s documentation correctly states that “The probability that a non-prime n will pass
one Miller-Rabin test is less than 1/4. Using the default value 25 for primep number of tests,
the probability of n being composite is much smaller that 10−15.”
33
Pseudoprimes. When testing numbers n < 341550071728321 (≈ 2
49) the function primep(n)
is deterministic, so no pseudoprimes can arise. If n > 341550071728321, then the combination of
Miller-Rabin testing and a Lucas test mean that no pseudoprimes for the test are known.
L.4 SageMath
SageMath 8.2 (or simply Sage) is a free Python-based open source mathematics software system
originally created by William Stein [S
+17] but now developed by many volunteers. Sage provides a
toolkit of mathematical functions in areas such as algebra, combinatorics, numerical mathematics,
number theory, and calculus.
Analysis Although there are many methods one could use to test the primality of a number in
Sage, the flagship function is is prime(n, proof) found in /src/sage/rings/integer.pyx. If
called with the value of proof set as True (default when starting Sage), the function will perform
use a provable primality test. If set to False it uses a strong pseudo-primality test and instead
calls is pseudoprime(n).
The “provable primality test” called when proof = True is the PARI [The18b] isprime
function. This then uses a combination of the Baillie-PSW test, Selfridge “p − 1”, and AdlemanPomerance-Rumely-Cohen-Lenstra
(APRCL). It is indicated in documentation that this test can
be “very slow” when testing a prime that “has more 1000 digits”.
The “strong pseudo-primality test” called when proof = False is less accurate, but much
quicker, and is therefore a likely choice when testing large candidates. The candidates are then
tested by PARI’s is pseudoprime(n), which consists of a Baillie-PSW test.
Pseudoprimes. Since a Baillie-PSW test is being performed, we know of no composites that are
incorrectly declared prime by SageMath for either boolean value of proof.
L.5 SymPy
SymPy [Sym17b] is a free, open source and widely used symbolic computation Python library that
provides a computer algebra system like functionality.
Analysis. SymPy provides the primality test isprime(n), which like Maxima, uses select bases to
perform a deterministic version of Miller-Rabin when testing candidates n < 2
64. We shall consider
the latest couple of releases of SymPy (SymPy 1.0 and SymPy 1.1), since significant changes to
the function isprime have been made recently.
SymPy 1.0 Prior to release 1.1 in July 2017, SymPy 1.0 conducted the primality test found
in isprime in the same manner. After some initial trial divisions, if no factor is found, the
function would call upon a deterministic version of the Miller-Rabin test, using bases described
in [Jae93,McC97]. For numbers larger than ≈ 2
53, the test would call additional rounds of MillerRabin.
In all releases up to and including 0.6.6 of 2009, this would simply perform 8 rounds of
Miller-Rabin on the bases {2, 3, 5, 7, 11, 13, 17, 19}. In version 0.6.7 [Sym17a], this was increased to
46 rounds of Miller-Rabin, using the first 46 primes as bases. The test then remained fundamentally
unchanged until version 1.1 in 2017.
SymPy 1.1 onwards In July 2017 the function isprime was revised to remove the final Miller-Rabin
test on 46 bases and replace it with a Baillie-PSW test as described in Section 2.4.
34
Pseudoprimes. SymPy 1.0 and all previous versions are vulnerable to composite numbers n
generated by the methods in Section 3.1.2. These numbers are trivial to construct when the final
Miller-Rabin test is based on the first 8 primes, but even after the changes made in 0.6.7, all
versions prior to 1.1 would wrongly declare composites generated in this manner to be prime. For
example, using the method of Section 3.1.2, we are able to construct a 1024-bit n of the form
n = p1p2p3 that is pseudoprime to all bases selected by SymPy in all versions prior to 1.1. Here
pi = ki(p1 − 1) + 1 with (k2, k3) = (241, 257) and
p1 = 2192
· 0x000000000000f8ae31e07964373e4997647e75fa186dd5e7
+ 20
· 0xe42ada869da0b3a333813f8102b1fb5f20623d6543e78a3b.
Since SymPy 1.1 introduced a Baillie-PSW test, we can no longer generate composites that would
be declared prime by SymPy.
L.6 Wolfram Mathematica
Wolfram Mathematica is a computational software package developed by Wolfram Research that
covers scientific, engineering, mathematical, and computing fields. The current release, Mathematica
11.3 [RI18], features built-in integration with Wolfram Alpha.
Analysis. Mathematica provides the inbuilt primality test PrimeQ that is said to perform two
Miller-Rabin tests using bases 2 and 3, combined with a “Lucas pseudoprime” test. Since the source
code is not open source, we are unable to verify the parameters used in the Lucas test. We note
that the documentation references Baillie and Wagstaff [BW80], from which Selfridge’s parameters
originate. Documentation of the function also indicates that this procedure is only known to be
correct for n < 1016 and that “it is conceivable that for larger n it could claim a composite number
to be prime”.
Pseudoprimes. Since a Baillie-PSW test is being performed, we know of no composites that are
incorrectly declared prime.
35