Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?

Question

I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.

Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete logarithm problem, such as Diffie-Hellman.

A modulus $p=2^k \pm s$ with $s$ small makes exponentiation $\bmod p$ appreciably simpler (the problem of quotient estimation in classical Euclidean division all but vanishes, and the cost of modular reductions becomes negligible compared to multiplications). This, and the desire to use a non-arbitrary, compactly stored modulus, makes it tempting to prefer such choice of $p$. Like "the modulus shall be the biggest 2048-bit safe prime, which is $p=2^{2048}-1942289$".

Are there any major reason not to do that, like a much faster algorithm for the discrete logarithm problem?

Answer 1

Short answer: Yes.

The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve.

Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given $a$ and $b=a^x$ in the above field.

Pollard's Rho and BSGS

In Baby-step giant step, we are trying to find $i$ and $j$ such that $b(a^{-m})^i = a^j$, where $m = \lceil \sqrt{n} \rceil$. Once we find such a pair, the discrete logarithm $x = i m + j$ follows, as $ b(a^{-m})^i = a^j \Leftrightarrow a^{x - m i} = a^j \Leftrightarrow x \equiv mi + j \pmod{n}$.

To do so, we first compute a table of all $a^j$ for all $j$ up to $m-1$. Then we iterate through all $i$ up to $m-1$, and compare $b(a^{-m})^i$ with $a^j$. Ignoring arithmetic costs, the runtime of this method is at most $2(m-1) = O(\sqrt{n})$ (with the same space requirements).

Due to the large space requirements, BSGS is rarely used in practice. Instead, we turn to Pollard's Rho. The crux of this method is to find a colliding nontrivial pair $(i,j)$ and $(k,l)$ such that $a^ib^j \equiv a^kb^l$. It follows that $x = \frac{k-i}{l-j} \pmod{n}$, since $a^i a^{xj} = a^k a^{xl} \Leftrightarrow a^{i + xj} = a^{k + xl} \Leftrightarrow i + xj \equiv k + xl \pmod{n}$.

So Rho comes down to finding a collision quickly. This can be done with various algorithms, Floyd's being the oldest and best known. The good news is that we can try and find a collision without an enormous table; the not so good news is that the algorithm is probabilistic, although the birthday paradox tells us we should expect a collision in about $\sqrt{n}$ steps.

In any case, these attacks are no good against a safe prime, where the order large enough that $\sqrt{n}$ is computationally unfeasible.

Pohlig-Hellman

The Pohlig-Hellman approach relies on the observation that there is an homomorphism $\phi$ from $a$ and $b$ from their group of order $n$, to the subgroup of order $p_i^{e_i}$ dividing $n$. In general, given $n = p_1^{e_1}p_2^{e_2}\ldots p_m^{e_m}$,

$$ \phi_{p_i^{e_i}}(a) = a^{n/p_i^{e_i}} $$

This allows us to compute the discrete logarithm of $\phi_{p_i^{e_i}}(a)$ and $\phi_{p_i^{e_i}}(b)$, which really is the discrete logarithm of $a$ and $b$ modulo $p_i^{e_i}$. From this observation, it is a matter of computing the logarithm modulo all prime divisors of $n$ (using the methods in the previous section) and combining them together using the Chinese remainder theorem.

If $n$ has many small prime divisors, i.e., it is smooth, this method is very much faster than Rho or BSGS. In a safe prime, however, this is not the case, since the order $n$ is the product $2q$, for a very large $q$. Pohlig-Hellman doesn't help much here.

Index Calculus

Index Calculus is the basis for the best-performing algorithms to compute discrete logarithms modulo safe primes. Suppose we know the logarithms of $2$ and $3$; finding the logarithm of $12$ is easy: $\log_a12 = 2 log_a2 + log_a3$, since $12$ factors into $2^2\times 3$.

We can generalize this method to arbitrary elements. Start by defining the factor base, i.e., all the primes up to some bound $B$. Then, find the logarithms of all the elements of the factor base (this is the tricky part). Finally, factor $b$ into the factor base, and simply add all the logarithms corresponding to the factorization you find. If $b$ does not factor completely into the factor base, multiply $b$ by some known exponent of $a$ and try again.

Finding the logarithms of all the primes up to $B$ requires some trickery. It has two major steps:

• For $k_i \in [1..n]$, find (usually by sieving) at least $\pi(B)$ elements $a^k$ that factor completely into the factor base. Store both $a^{k_i}$ and its complete factorization.
• Now we have the linear system (modulo $n$): $$ \begin{eqnarray} e_{1,1} \log_a 2 &+& e_{1,2} \log_a 3 &+& \ldots &+& e_{1,{\pi(B)}} &=& {k_1} \\ e_{2,1} \log_a 2 &+& e_{2,2} \log_a 3 &+& \ldots &+& e_{2,{\pi(B)}} &=& {k_2} \\ &&&&\ldots&&&& \\ e_{{\pi(B)},1} \log_a 2 &+& e_{{\pi(B)},2} \log_a 3 &+& \ldots &+& e_{{\pi(B)},{\pi(B)}} &=& {k_{\pi(B)}} \\ \end{eqnarray} $$
• Solving the above linear system gives us the needed logarithms for the factor base.

The runtime of this method, for appropriate choice of $B$, is $\exp{((2+o(1)((\log n)^{1/2}(\log \log n)^{1/2}))}$. This is not strictly polynomial, but is a big improvement on the previous methods.

Number field sieve

The number field sieve is currently the best algorithm for both integer factorization and discrete logarithms over finite fields. For the discrete logarithm, it is analogous to the above index calculus, with a few major modifications:

• We are working in the number fields $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$ instead of the integers; there is, however, a map from such fields to the integers under some conditions. The number fields are defined by the polynomials $f_1$ and $f_2$ of degree $d_1$ and $d_2$; there must exist an integer $m$ such that $f_1(m) = f_2(m) = 0 \pmod{p}$.
• The factor base is formed by the primes in both $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$, up to bounds $B_1$ and $B_2$.
• During sieving, we look for pairs $(x,y)$ such that $N_{f_1}(x + \alpha y)$ and $N_{f_2}(x + \beta y)$ are $B_1$ and $B_2$-smooth, respectively, where $N_{f_i}$ is given by $$ N_{f_i}(x + \alpha y) = y^{d_i} f_i(x/y) $$

The speed of the number field sieve hinges on the speed of finding $(x,y)$ with smooth norms $N_{f_i}(x,y)$. In turn, the probability of $N_{f_i}(x,y)$ being smooth is linked to its size: the smaller it is, the more likely it is to be smooth. And in turn, the size of $N_{f_i}(x,y)$ is determined by $x$ and $y$ (obviously), but also by the coefficients of $f_i$! When $f_i$ has very small coefficients, the number field sieve becomes asymptotically faster, from

$$ \exp ( (1.923 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}) $$

to

$$ \exp ( (1.526 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}). $$

When one chooses a prime $p$ very close to $2^k$, it becomes easy to find a sparse polynomial that has a root modulo $p$. In your example, $p = 2^{2048} - 1942289$, we can find the degree $8$ polynomial

$$ x^8 - 1942289, $$

since $2^{2048} - 1942289 = (2^{256})^8 - 1942289$. This polynomial has very small coefficients, that render the number field sieve for the discrete logarithm in this field much faster that it would be for a random 2048-bit prime.

Answer 2

I have asked a similar question to Arjen Lenstra a few years ago: I was investigating three 2048-bit primes of low Hamming weight:

• $p_1 = 2^{2048} - 2^{1056} + 2^{736} - 2^{320} + 2^{128} + 1$
• $p_2 = 2^{2048} - 2^{1376} + 2^{992} + 2^{896} + 2^{640} - 1$
• $p_3 = 2^{2048} - 2^{2016} + 2^{1984} - 2^{1856} - 2^{1824} + 2^{1792} - 2^{1760} + 2^{1696} + 2^{1664} + 1$

Since all the exponents are multiple of $32$, this allows for fast arithmetics (especially modular reduction). Moreover, $p_1 = 2^{128} q_1 + 1$, $p_2 = 2 q_2 + 1$ and $p_3 = 2^{1664} q_3 + 1$, where $q_1$, $q_2$ and $q_3$ are prime, and the subgroup generated by $2$ has an order which is a multiple of $q_1$, $q_2$ and $q_3$, respectively. So these looked good for performance, when implementing Diffie-Hellman (especially with $p_2$, which is a "safe prime") or DSA (with $p_3$). But it was possible that discrete logarithm modulo such special primes was easier than with "normal" primes, especially if Special Number Field Sieve applied.

Lenstra himself was not sure of the answer, but he forwarded the question to someone else (I do not know who), who answered this:

I did a short search for SNFS-like polynomial, just examining small powers of 2 as zeros (using LLL) without caring about skewness.

For $p_1$ one gets:

f1(x)=309485009821345068724781056*x^8 - 75557863725914323419136*x^4
     + 2*x^3 - 37778931862957161709568*x
     + 340282366920938463463374607431768211457

with $f_1(2^{245})=p_1$.

This is much better than GNFS, but also worse than (usual) SNFS for a 2048 bit number. Perhaps one can get a better polynomial by also examining skewed polynomials. Similarly, for $p_2$ there is the following degree 9 polynomial:

f2(x)=16*x^9 - 17179869184*x^6 + 332306998946228968225951765074280448*x^4
     + x^3 - 4611686018427387904

with $f_2(2^{234})=p_2$ and for $p_3$:

f3(x)=170141183381241069254316454265464291329*x^9
     - 737869762914022326280*x^8
     + 130668428917922779575948702919181067091968*x^7
     + 2722258934733682407888030063919506653192

with $f_3(2^{228})=p_3$.

Perhaps degree 9 is too big for 2048 bit number, but the degree 8 and degree 7 polynomials also seem to be better than GNFS polynomials. Moreover, by examining the numbers $p_1$, $p_2$ or $p_3$ more closely, one might find better polynomials, thus getting closer to SNFS complexity.

As reference I only know the following paper by O. Schirokauer which essentially does the constructions above.

Bottom-line: when $p$ has a special format with low weight, it seems that SNFS applies at least partially, and offers a faster DL algorithm than GNFS. Complexity-wise, when SNFS applies, you need a $2n$-bit modulus to get the same resistance than what you have with a $n$-bit random prime where only GNFS works. So, to be safe, if you want a special-format $p$ like the one you suggest, or those I investigated, you need to double the length (a 4096-bit modulus, not a 2048-bit modulus), which cancels any implementation advantage derived from the special format.

On the other hand, special-format primes $p$ appear to be fine for base fields for elliptic curves; the NIST curves like P-256 use such special primes.

Answer 3

Beyond the existing answers, any clever selection of $p$ is problematic. If we use a special $p$ and it is reused widely, an attacker can attack all of them together. Most of the work in calculating Dlog only depends on the public paramaters and not on the individual value we are trying to get the discrete logartithm of. We even have reason to believe the NSA has successfully done this against common DH paramaters. Even if you find a special prime with fast modular exponentiation and no known algorithm to speed up Dlog for it, the mere fact you are encouraging people to reuse this special prime rather than select their own weakns it by a factor of the number of connections which reuse these special paramaters.