6
$\begingroup$

I'm looking for Schnorr groups allowing fast modular reduction. Say, using the notation in DSA, with 256-bit prime $q$ and 3072-bit prime $p$, and $p\equiv1\pmod q$.

Are there standards, RFC, or other references about this?

I'm considering choosing $p$ with all bits at $1$, except for a relatively short segment not too far from the top bits. That allows very fast Montgomery modular reduction, which can next to halve the computational effort compared to arbitrary $p$. Would that make GNFS faster, by allowing selection of a better polynomial?

Any reason not to use $g=2^{(p-1)/q}$, which seems a most natural generator?

A rather extreme example of what I have in mind: $$\begin{align} q&=2^{256}-2^{194}-1\\ p&=2^{3072}-1\\&\quad-2^{2745}\,\mathtt{2219c36803ffffff6352c900000000006008ef007fffffffbcc79fd201_h}\\ \end{align}$$

q=fffffffffffffffbffffffffffffffffffffffffffffffffffffffffffffffff
p=fffffffffffffffffe000000443386d007fffffec6a5920000000000c011de00ffffffff798f3fa401ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

where $q$ is the smallest $256$-bit prime with a single $0$ bit; $2745$ is chosen to minimize the bit size of the $230$-bit constant defining $p$, happens to put that term in the high-order bits of $p$, and (due to the special form of $q$) also creates long sequences of $0$ and $1$ in that segment of $p$.

Update: Daniel Shiu's answer shows that indeed, the above allows a sizable speedup of GNFS. Let's forget about it. What about taking $p=2^{3072}-1-c\,2^{3072-\ell}$ where $c$ is a $\ell-1$-bit nothing-up-my-sleeves constant, and some larger $\ell>230$? Up to $\ell$ about $1024$ (one third the bit size of $p$), we still save most of the modular reduction effort.

$\endgroup$
4
+100
$\begingroup$

TL;DR

  1. There are no standards or RFCs that use this idea.
  2. There is a slightly improved number field sieve attack on your example number based on back of the envelope calculations (see below).
  3. Your proposed generator would be fine.
  4. The follow on proposal should not admit special polynomials for $\ell\ge 768$.

The back-of-the-envelope generic attack
To attack a general 3072-bit prime number, one could use the method of Joux and Lercier to construct polynomials $f_\alpha(x)$ and $f_\beta(x)$ with a common root modulo $p$. A good choice seems to be $f_\alpha$ of degree 5 and coefficients 0,+1,-1 and $f_\beta$ of degree 4 and coefficients around 614-bits. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|,b\le 2^{65.5}$ for both being $2^{65.5}$ smooth (here $\mathcal N$ denotes the norm down to $\mathbb Q$). The largest numbers would be roughly, 327.5-bit and 876-bits and a quick Dickman-$\rho$ calculation in SageMath says that there's a $2^{-65.332}$ chance of them both being smooth and you should be able to get more smooth numbers than primes below the smoothness bound. You then solve a roughly $2\times\pi(2^{65.5})$ variable sparse linear algebra problem (where $\pi(n)$ denotes the number of primes up to $n$) and then and subsequent problem are significantly less work. The work of $2^{131}$ smoothness tests and the large linear algebra problem are not totally out of whack with the usually quoted 128-bits of work.

The back-of-the-envelope for your prime
Your prime admits the polynomial pair $$f_\alpha(x)=x^9-2^{15}cx^8-64$$ $$f_\beta(x)=x-2^{342}$$ where $c$ is your 230-bit constant. One can then test $\mathcal N(a+b\alpha)$ and $\mathcal N(a+b\beta)$ for $0\le |a|\le 2^{46.5}$ and $0<b\le 2^{76.5}$ for both being $2^{61.5}$ smooth. The largest numbers would be roughly, 693.5-bit and 418.5-bits and SageMath says that there's a $2^{-61.197}$ chance of them both being smooth. Thus again you should be able to get more smooth numbers than primes below the smoothness bound. You then have a roughly $2\times\pi(2^{61.5})$ variable sparse linear algebra problem etc. This is roughly $2^{123}$ smoothness tests and a commensurable linear algebra problem. Your problem is therefore perhaps 8-bits easier than a typical 3072-bit prime. This is much less degradation than other SNFS attacks, and might be tolerable depending on circumstances.

ETA: In re the follow up question. The smallest degree for which special polynomials could beat the J-L pair seems to be 4. A generic blob of 768 or more bits at the head of your 3072-bit number should mean that there is no special polynomial of degree 4 or more. Taking $\ell<768$ might still be secure in some cases, but the analysis starts getting fiddly.

$\endgroup$
3
  • $\begingroup$ Thanks, that wounds my initial proposal to the point I drop the idea. If you feel like it (you well deserve the bounty anyway), what about the less radical variant in the new update paragraph? $\endgroup$
    – fgrieu
    Apr 19 at 13:02
  • $\begingroup$ What are $\mathcal{N}$ and $\pi$? $\endgroup$ Apr 19 at 13:23
  • 2
    $\begingroup$ @AmanGrewal: The norm of the algebraic number down to the rational field and the prime counting function respectively. I've edited to add these definitions. $\endgroup$
    – Daniel S
    Apr 19 at 13:31

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.