4
$\begingroup$

A few days ago I asked a question about the security of the Lim-Lee Prime Generation algorithm used by GNU Privacy Guard’s libgcrypt library. L. Carvalho provided a good answer to that question.

As a follow up question, I am wondering whether one could use Lim-Lee Prime Generation as a means of creating a “Nothing Up My Sleeve” prime for use in Diffie-Hellman key exchanges?

It seems to me that if one wanted a 2048-bit prime (p) with no prime (other than 2) dividing p-1 less that 256 bits in length then by choosing a set of maximum prime divisors of p-1 that give a prime p, one would have a good construction of unique, "Nothing up my Sleeve" (NUMS) numbers for a given prime size and prime order subgroup size.

I'm thinking that for a 2048-bit Lim-Lee Prime (p), p-1 could be divisible by 2, the largest 255-bit prime, and the 7 largest 256-bit primes such that p is prime. That would be unique – right?

$\endgroup$
3
$\begingroup$

While I agree that there exists a largest Lim-Lee prime I think it may be computationally infeasible to construct/find this prime in a provable way. The set of 256-bit primes is very large and you would need to search through every product of 7 such primes to find the greatest such product that makes the resulting number a prime.

You could add an additional though rather artificial constraint to make the problem tractable. You could say that you want to look at products of 7 primes chosen from the 20 largest 256-bit prime and choose the largest such product such that when multiplied by 2 times the largest 255-bit prime (2^255 - 19) and added to 1 the result is a prime number.

There are 20 choose 7 or 77520 products of 7 primes to look at. One would expect there to be many primes formed from these products.

Your criteria for the NUMS prime would be:

  1. Pick the size of the prime. This size is chosen to make the cost of the Number Field Sieve Discrete logarithm prohibitively high

  2. Pick the size of the sub-primes in the Lim-Lee algorithm. The base 2 log of this size should be twice the desired security strength. For 128-bits of security one should use 256-bit primes. For n bits of security one should use primes of 2n bits.

  3. Pick the size (n) of the set of primes to examine. Given the size of the desired prime (a), the size of the sub-primes (b), c = the greatest integer less than (a/b)-1, you choose n such that n choose c is large enough to expect a prime in the set of putative primes that will be generated.

  4. Choose the n largest primes of size b for the set.

You have then described a family of primes that are unique given choices of

a = size of the prime

b = size of the sub-primes

c = size of the pool of primes

With those three constraints you will have a unique result. For some sets of parameters there will be ZERO primes that satisfy the criteria. .... Looking back on your question about Lim-Lee primes from several days ago, many people would recommend staying with the original idea of Lim-Lee's algorithm for ephemeral prime generation rather than using fixed NUMS values. If you were going to use a NUMS value you might consider using a 3072-bit prime to give an extra hedge against rich adversaries.

| improve this answer | |
$\endgroup$
2
$\begingroup$

While the previous person to answer this question raises some interesting philosophical issues regarding whether or not NUMS is an appropriate criteria for cryptographic parameters, I will try to answer the question from a mathematical standpoint.

As noted by you and by the answerer of your previous question, the Lim-Lee Prime Generation algorithm has been used in the GNU Privacy Guard for nearly 20 years. The security of this algorithm for generating ephermeral primes appears well established.

What you are suggesting is to find, in some sense, the largest possible values that could be generated by the Lim-Lee algorithm and call them "Nothing up my Sleeve" Numbers. That seems logical and consistent with the philosophy of generating "Nothing up my Sleeve" cryptographic parameters.

I believe that your criteria defines a unique prime number which has all of the characteristics necessary for use in Diffie-Hellman Key Exchanges. A slightly better NUMS parameter would be a 2049-bit prime (p) where p-1 is divisible by 2 and the 8 largest 256-bit primes that make p a prime. I see this as somehow more natural but it does go one bit over a byte boundary and that may be troublesome for implementation.

Again, I am not arguing with the previous answer. Rather I am just answering the underlying mathematical/cryptographic question.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.