Skip to main content
added 33 characters in body
Source Link
Samuel Neves
  • 12.8k
  • 46
  • 54

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

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.

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.

Source Link
Samuel Neves
  • 12.8k
  • 46
  • 54

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.