Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

Question

My company wants to generate new primes for every Diffie-Hellman key exchange. We are thinking of using the prime generation scheme in GPG’s libgcrypt library.

The code documentation says that the scheme that libgcrypt uses is based on a paper from Crypto 97. It is entitled, ”A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup” and is by Lim and Lee.

Is this Prime Generation scheme by Lim and Lee still considered secure? Is the libgcrypt code the only implementation of this scheme?

Answer 1

The Lim-Lee Prime Generation Algorithm you reference has been used in GPG’s libgcrypt for almost 20 years. As long as the bit length of the smallest prime (other than 2) dividing the prime (p) is greater than or equal to twice the desired bit security the Lim-Lee prime generation produces sufficiently strong primes for use in Diffie-Hellman key exchanges. For instance, if one wished for 128-bits of classical security, the smallest prime (other than 2) dividing p-1 should be at least 256 bits in length.

Using the Lim-Lee algorithm to generate a prime p gives all of the prime factors of p-1. These factors can be used to prove the primality of p using an extension of Pocklington’s theorem. If you were to use the Lim-Lee algorithm for generation of ephemeral primes for a Diffie-Hellman key exchange you should consider using deterministic RNG for the Lim-Lee algorithm. If you sent the seed for the deterministic RNG to the other side of the key exchange, they could re-run the Lim-Lee algorithm, produce the prime p, the factors of p-1 and check that p is indeed prime and that all of the prime factors of p-1 are suitably large. Sending a seed rather than the prime and all its prime factors is more bandwidth efficient.

Given the widespread use of GPG in the world, I would assume that if there were some major weakness in the Lim-Lee algorithm someone would have published a criticism of the algorithm by now. I have never run across such a criticism. Therefore, I believe that the Lim-Lee generation scheme is fit for the purpose you describe.