3
$\begingroup$

We're all aware of the Logjam attack, which is known as "FREAK on discrete logarithms". The attack works by doing a large pre-computation step, which needs only to be done once per field and then quickly computes discrete logarithms. As this seems to be a special property of the GNFS version for discrete logarithms I asked myself if the same property applies for the GNFS version for factoring.

Question: As the GNFS performs a large pre-computation step, can intermediate results be re-used for distinct factorizations?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ With discrete log, precomputation is per group: you share results for different discrete logs over the same group. What would the analogue be for factoring? $\endgroup$ – cpast Jun 27 '15 at 17:28
  • 1
    $\begingroup$ @cpast, I don't have any idea what this analogue would be, hence my question. But I also don't have understanding of the details of the GNFS and the various proposed extensions and optimizations. This DJB paper may be related $\endgroup$ – SEJPM Jun 27 '15 at 17:43
  • $\begingroup$ There is an technique called Batch NFS but I don't know about the details. $\endgroup$ – CodesInChaos Jul 4 '15 at 12:29
  • $\begingroup$ @CodesInChaos, already linked as "maybe related DJB paper" in my above comment :( $\endgroup$ – SEJPM Jul 4 '15 at 12:45
3
$\begingroup$

Yes, but it's different and not as cost-efficient.

The discrete log variant of the number field sieve goes (very loosely) like this:

  • Collect logarithms of many small primes using sieving and linear algebra (the precomputation stage)
  • Represent the target field element as a product of small primes and use the small logarithms to recover it (the individual logarithm stage)

In factorization by the number field sieve we do not have an individual log step, so the same principle used in Logjam does not apply directly. But if we look deeper into the inner workings of the number field sieve, we can obtain something similar.

The number field sieve begins by choosing two polynomials $f(x)$ and $g(x)$. The only conditions required for these polynomials is that they share the same root modulo $N$—the number to be factored—and that they are irreducible (if you find a splittable polynomial, you can immediately factor $N$). There are several ways to accomplish this, but the most common is (again, loosely):

  • Pick an appropriately-sized base $m$
  • Represent N in base m, and let $f(x)$'s coefficients be the $d+1$ base-$m$ digits of N. Thus $f(m) = 0 \pmod{N}$.
  • Let $g(x) = x - m$. Trivially $g(m) = 0 \pmod{N}$.

Then, we proceed with the number field sieve:

  • Find pairs $(a, b)$ such that both $b g(a/b) = a - bm$ and $b^d f(a/b)$ are smooth.
  • Once sufficiently many pairs have been found, use linear algebra to find two distinct squares modulo $N$: $t_1^2 \equiv t_2^2 \pmod{N}$.
  • Compute the square roots on both sides, and factor $N$ with $\gcd(t_1 - t_2, N)$.

Notice that $g(x)$, for any particular fixed $m$, is always a root of the polynomial regardless of which $N$ we are working with. This suggests a batching approach:

  • Pick an appropriately-sized $m$ for a given integer size (or set of integers $N_i$). Say, $m \approx \sqrt[6]{2^{1024}}$ for $N \approx 2^{1024}$.
  • Precompute a sufficiently-large number of pairs $(a, b)$ for which $a - bm$ is $B$-smooth for some appropriate bound $B$.
  • For every $N_i$, take the pairs $(a, b)$ precomputed earlier and find the ones for which $b^df_i(a/b)$ are also smooth. Then proceed with the number field sieve as usual.

This approach was suggested by Coppersmith as the "Factorization Factory", and is itself based on earlier work by Schnorr, who also found a batch version of a factoring algorithm by Miller. The complexity Coppersmith came up with was $L_N[1/3, 2.006]$ time and $L_N[1/3, 1.638]$ space for the initial precomputation, and then $L_N[1/3, 1.608]$ time for each individual factorization. Here $L[a, c]$ is the usual

$$ L_N[a, c] = \exp((c + o(1)) (\log N)^a (\log \log N)^{1-a}). $$

In 2001 Bernstein proposed the "circuit NFS", which used the area-time (AT) cost metric instead of the usual RAM metric (where memory is free), which had been used until then. This metric shows that the factorization factory is actually pretty terrible when it comes to cost, due to its enormous space (and time) requirements. Circuit NFS instead optimized for the AT cost—using mesh circuits instead of a more common RAM model—and reached an AT cost of $L[1/3, 1.97]$. The Batch NFS follow-up included Coppersmith's factorization factory ideas into the circuit NFS, and given sufficiently many numbers to factor reaches an AT cost of $L_N[1/3, 1.704]$ per factorization.

Now, this may make the Batch NFS sound great, and raise the question of why, say, the FREAK attackers did not use it. Firstly, the Batch NFS assumes a mesh circuit layout; this alone makes implementing it out of reach for the vast majority of people, since we are generally constrained to (more or less) RAM machines. Secondly, the results on the Batch NFS are purely asymptotic—we simply don't know what the constant factors look like in reality.

There is one instance of the factorization factory being used in practice—the Mersenne factorization factory. Here the authors flipped the idea above: instead of fixing $g(x)$ and testing $b^df(a/b)$ for smoothness, they fixed $f(x)$ and tested $a - mb$ for smoothness. The result was an estimated 50% savings in computation on the factoring of 17 Mersenne numbers, with a 70 TB storage overhead. This is a fairly modest saving, but according to the authors it gets worse for general (that is, RSA) numbers. In practice, without your own chip factory you are likely better off factoring each integer one by one with the classic number field sieve.

| 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.