# How to generate safe primes in a verifiable way?

FIPS 186-3 (APPENDIX A: Generation and Validation of FFC Domain Parameters) specifies how to generate Finite Field Cryptography Domain parameters and how to perform an explicit domain parameter validation. These parameters consist of the set of values: (p, q, g {, domain_parameter_seed, counter}). The Standard specifies the following bit lengths of p and q:

p: 1024, q: 160

p: 2048, q: 224

p: 2048, q: 256

p: 3072, q: 256

I would like to generate FFC Domain parameters when p is 2048 and q is 2047 bits (p=2q+1). Is there any way to adapt the methodology proposed in FIPS 186-3 to these bit lengths? or is there any way to generate safe primes in a verifiable way?

• Why do you want to do this? – mikeazo Feb 16 '18 at 16:30
• I am using ElGamal encryption and I was wondering how to demonstrate that I have chosen parameters appropriately. – adarim Feb 17 '18 at 11:53
• Interesting, but I wonder if there would still be any performance benefits over normal DSA. Would it be faster do you think or is this just an exercise? I think generating the parameters might take very long, but I don't think that would be a big issue of course. – Maarten - reinstate Monica Feb 17 '18 at 23:34
• What exactly is it that you want to verify? That it is a safe prime of the appropriate length? In that case just check that it has the correct length, that it's prime and that $(p-1)/2$ is also prime. Seems trivially checkable. – Maeher Feb 19 '18 at 1:54
• What do you need? A nothing up my sleeve number? A deterministic primality proof? – CodesInChaos Feb 19 '18 at 11:42

Here's a very simple method: Find the largest number below $2^n$ that is a safe prime. Use standard primality tests for $p$ and $q = (p - 1)/2$. For example, $2^{2048} - 1942289$ is the largest safe prime below $2^{2048}$.

But you didn't specify what you want this for. If you want to use this with Diffie–Hellman to resist discrete logarithms, then that won't be a good option. The bit lengths you describe are designed for DSA, which has different security requirements.

For an $n$-bit safe prime to use with Diffie–Hellman, you want few small subgroups and you want to destroy the structure that the SNFS exploits, so you can pick the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$$ is a safe prime and congruent to 7 modulo 8. The latter condition ensures that 2 generates the subgroup of quadratic residues in $(\mathbb Z/p\mathbb Z)^\times$, of prime order $(p - 1)/2$. This is the technique used by RFC 3526 to pick standard groups at sizes from 1536 to 8192; the technique is described in RFC 2412, Appendix E.

This technique is sometimes called NUMS, for nothing-up-my-sleeves, because it uses the conventional transcendental constant $\pi$ instead of some inexplicable string of 1920 bits. There's no security significance to $\pi$ except that it destroys some structure the SNFS could exploit—you could use $e$ instead, or $e^\pi$, or $\cos 1$, or all manner of other options to get a result you want if you knew of a small, say one in a million, fraction of primes that admitted a back door. For this reason, may I interest you in doing Diffie–Hellman over rigidly selected elliptic-curve groups free of magic constants instead? As a bonus, you get higher performance, smaller keys, easier defense against timing side channels, a number of high-quality implementations, and cooler names like X25519.

I'm not sure offhand what all the security requirements for Elgamal encryption: approximately nobody uses Elgamal encryption these days. Naively, if the recipient given $(c, d)$ yields $d \cdot c^{-x}$ where $x$ is the secret exponent, then the adversary can apply the Lim–Lee active small-subgroup attack by supplying $d = 1$ and $c$ of small orders $n_0$, $n_1$, $n_2$, etc., to learn points ${g_0}^x$, ${g_1}^x$, etc., to which they can apply discrete logarithms in small subgroups to recover $x \bmod n_0$, $x \bmod n_1$, etc., and reconstruct $x$ with the Chinese remainder theorem.

Could I interest you in replacing your use of Elgamal encryption by X25519 in a NaCl crypto_box or libsodium crypto_box_seal, which have none of these finicky considerations and run much faster with fewer side channels and have smaller ciphertext expansion and are widely implemented and understood?

• Note that the comment of fgrieu has been removed. There is a comment of the original author where El Gamal encryption is indicated as reason for the larger parameters. You can indeed to El Gamal encryption with OAEP padding, but as you might imagine, the overhead of OAEP won't let you encrypt that much data and without parameters you may need to change OAEP if you don't (hint). – Maarten - reinstate Monica Feb 17 '18 at 23:37