Index calculus, end to end

Index calculus is the attack that makes RSA and finite-field Diffie–Hellman keys large, and the attack that elliptic curves are chosen to escape. This note runs it end to end, twice, on groups small enough to show every relation.

Part 1
Find x with 17x ≡ 10155 (mod 10163), using the primes up to 13
Part 2
Find k with Q = kP on y2 = x3 + x + (1 + t) over F2632, a group of 69,383 points
Checked
Every logarithm on this page is verified by exponentiation or scalar multiplication each time the site is built
What it shows
The mechanics. At these sizes neither part beats a generic attack, and Part 2 would not at any size; the last section says why

The idea

Choose a small set of group elements, the factor base. Find many random group elements whose logarithm you know and which can be written as products of factor-base elements; each one gives a linear equation in the unknown logarithms of the factor base. Solve those equations. Then write the target as a product of factor-base elements too, and its logarithm follows. The number field sieve is a far more elaborate version of the same plan.

Part 1: the instance

The group is the nonzero integers modulo p = 10163 under multiplication. This p is a safe prime: p − 1 = 2 · 5081 with 5081 prime, which will make the linear algebra simple. g = 17 generates the group. The target is h = 10155, and the task is to find x with 17x ≡ 10155 (mod 10163).

The factor base is the primes up to 13: 2, 3, 5, 7, 11, 13. An integer is 13-smooth if all its prime factors are in that list.

Collecting relations

Pick a random exponent e, compute ge mod p as an ordinary integer between 1 and p − 1, and try to factor it over the factor base. If it factors as ∏ ℓici, then taking logarithms gives one linear equation:

e ≡ c1·log 2 + c2·log 3 + … + c6·log 13   (mod 10162) Logarithms to base g live modulo the group order, p − 1.
Every relation the search found, in order. Each says e ≡ Σ ci·log(ℓi) (mod 10162).
#e17e mod 10163factorisation
151851953 · 5 · 13
2731131532 · 5 · 7
3636648422 · 112
41886327622 · 32 · 7 · 13
547349216210 · 32
617326426

The search tried 51 exponents and kept 6, a rate of 11.8%. Exactly 737 of the 10162 residues are 13-smooth, 7.3%, so about 3.7 hits were expected and this run found more. The search stops as soon as its relations determine all 6 logarithms; here that took 6.

Solving for the factor base

The equations hold modulo 10162 = 2 · 5081, which is not a prime, so they are solved in two pieces. Modulo 5081 they are ordinary linear equations over a field, and Gaussian elimination gives each logarithm modulo 5081. Modulo 2 there is a shortcut: since g generates the group, log ℓ is even exactly when ℓ is a square modulo p, which the Legendre symbol decides. The Chinese remainder theorem then combines the two residues into the logarithm modulo 10162.

The factor base's logarithms: the linear algebra gives them mod 5081, the Legendre symbol gives them mod 2, and the Chinese remainder theorem combines the two. The build checks 17log = ℓ for every row.
ℓlog mod 5081square mod 10163?log mod 2log17 ℓ
23676no18757
34311yes09392
54285no14285
74566yes04566
114588yes04588
131670yes01670

The individual logarithm

The target itself is not smooth, so multiply it by a random known power of g until the product is. After 4 tries, s = 4549 works:

10155 · 174549 ≡ 9504 = 25 · 33 · 11   (mod 10163) So x + s is a sum of factor-base logarithms.
x ≡ 5·8757 + 3·9392 + 4588 − 4549 ≡ 866   (mod 10162) The build checks that 17866 ≡ 10155 (mod 10163).

Why this is subexponential

The factor-base bound B is a trade-off. A larger B makes random residues more likely to be smooth, but adds unknowns, so more relations and a bigger linear system are needed. Balancing the two, using the known density of smooth numbers, gives a running time of Lp[1/2, c] for this basic method: slower than polynomial, much faster than the √p of a generic attack. The number field sieve reaches Lp[1/3, 1.923] by making the numbers that must be smooth much smaller.

Everything above depends on one fact: an element of Fp× is also an integer, and integers factor. A point on an elliptic curve is not a product of anything. Part 2 is about what can be used instead.

Part 2: an elliptic curve

Gaudry's idea is to use a subfield. Over Fqn, take the factor base to be the points whose x-coordinate lies in the subfield Fq, and try to write a random point as a sum of n of them. The smallest case is n = 2. Here q = 263, and F2632 is built as F263(t) with t2 = 5, so its elements are u + vt with u and v in F263.

The curve is y2 = x3 + x + (1 + t). Its group has 69,383 points. That number is prime, it lies in the Hasse interval [68,644, 69,696], and the build finds a point of that order; since the interval is narrower than the order, the curve has exactly 69,383 points. P = (127 + 190t, 207 + 25t), and the target is Q = (219 + 142t, 183 + 101t).

The factor base: for each x in F263, the curve has two points with that x-coordinate or none. 141 of the 263 values give points, 282 points in all, about the half that one would expect. Since log(−P) = −log P, each pair ±P contributes one unknown. Write Px for the member of the pair with x-coordinate x that the code treats as positive.

Decomposing one point

Take R = mP for a random m, here m = 28924. Its x-coordinate is xR = 194 + 22t. The question is whether R = ±Px1 ± Px2 for some x1, x2 in F263. Semaev's third summation polynomial answers exactly this: for the curve y2 = x3 + ax + b,

S3(x1, x2, x3) = (x1 − x2)2x32 − 2((x1 + x2)(x1x2 + a) + 2b)x3 + (x1x2 − a)2 − 4b(x1 + x2) S3 vanishes exactly when there are points with these x-coordinates satisfying ±P1 ± P2 ± P3 = O. The build checks this against the group law before using it.

The order of x1 and x2 does not matter, so rewrite S3 in e1 = x1 + x2 and e2 = x1x2, which lowers the degrees:

(e12 − 4e2)x32 − 2(e1(e2 + a) + 2b)x3 + (e2 − a)2 − 4be1 = 0

Now substitute x3 = xR and the curve's a and b. Every coefficient is an element u + vt of F2632, and the unknowns e1, e2 are meant to lie in F263, so the equation holds only if the parts with and without t vanish separately. That splits one equation over F2632 into two over F263: this is the Weil restriction. For this R the two equations are

C1:   (219e1 + 46)·e2 + 120e12 + 215e1 + 188 = 0
C0:   e22 + (138e1 + 204)·e2 + 80e12 + 134e1 + 100 = 0 All coefficients modulo 263. C1 is linear in e2 because the e22 term of S3 has no t part.

Eliminating e2 between them, by taking the resultant, leaves one polynomial in e1. For the equations above it is β2 − αβδ + α2φ, where C1 = αe2 + β and C0 = e22 + δe2 + φ:

38e14 + 42e13 + 196e12 + 149e1 + 262 = 0 At this size the code simply tries all 263 values of e1; at real sizes one computes gcd(f, e1q − e1) instead.

It has exactly one root in F263, e1 = 97. From C1, e2 = 152. Then x1 and x2 are the roots of X2 − 97X + 152, which are 242 and 118, both in F263 and both with points on the curve. Checking the four sign choices gives R = P242 − P118, and so the relation

28924 ≡ log P242 − log P118   (mod 69383) One equation in two unknowns, from one random multiple of P.

In general this step is a polynomial system: for n factor-base points it has n unknowns and degree 2n−1 in each, solved with Gröbner bases rather than one resultant. The summation polynomials page covers what that costs.

How often a point decomposes

The code repeated this for random multiples of P until it had 10 more relations than unknowns. It took 380 attempts to find 151 relations, a success rate of 39.7%.

At this size the true rate can be computed outright, by adding every pair of the 282 factor-base points and counting the distinct results. Exactly 30,388 of the 69,382 nonzero points are sums of two factor-base points: 43.8%. Counting pairs alone, 39,903 of them, would suggest 57.5%, but different pairs can give the same sum; treating the sums as random points gives 1 − e−39,903/69,382 = 43.7%, close to the exact figure. Gaudry's heuristic probability, 1/n! = 1/2, is the leading term of the same count. This run's 39.7% is within sampling error of the exact value.

The linear algebra

The first eight of the 151 relations. Each row is one random multiple mP that decomposed; Px is the factor-base point with x-coordinate x.
#mm ≡ … (mod 69,383)
128924−log P118 + log P242
246502log P12 + log P60
311914log P99 − log P186
426091−log P73 − log P176
559935log P39 + log P45
666930−log P123 + log P204
746064log P133 − log P239
824430log P40 − log P81

Each relation involves at most two unknowns, so the matrix is extremely sparse:

The whole relation matrix, 151 rows by 141 columns: one mark per nonzero entry. 150 rows have two entries and the rest have one.

Gaussian elimination modulo 69,383 gives the matrix rank 121, and determines 118 of the 141 logarithms uniquely; the build checks each by scalar multiplication. The other 23 stay free even though there are more equations than unknowns. With two unknowns per equation, the relations form a graph on the factor base, and a logarithm is pinned down only when its part of the graph contains a suitable cycle; parts that are trees leave one degree of freedom each. Collecting more relations closes them. The descent below only needs two determined logarithms, so the code stops here.

The descent

Now bring in Q. Pick a random c and try to decompose Q + cP. After 8 tries, c = 58003 gives Q + cP = −P235 − P218, with both logarithms known, so

k ≡ −log P235 − log P218 − c ≡ −64061 − 35459 − 58003 ≡ 50626   (mod 69383) The build checks that 50626P = Q.

What this does and does not show

It shows the pipeline: factor base, relations, sparse linear algebra, descent, and, on the elliptic side, the summation polynomial and the Weil restriction that turn point decomposition into polynomial solving over a smaller field.

It does not show a speedup. Pollard's rho on this group would expect about √(πn/2) ≈ 330 steps, each one point addition. Index calculus used 380 decomposition attempts, each costing a resultant and a root search, plus the linear algebra. For n = 2, Gaudry's complexity Õ(q2−2/n) = Õ(q) has the same exponent as rho's O(qn/2) = O(q), and the constants favour rho. The advantage starts at n = 3, where Õ(q4/3) beats q3/2, and grows with n, but so does the degree of the polynomial systems, which is where the real difficulty lives.

Primary sources

  1. L. Adleman, "A subexponential algorithm for the discrete logarithm problem with applications to cryptography", FOCS 1979
  2. I. Semaev, "Summation polynomials and the discrete logarithm problem on elliptic curves" (2004)
  3. P. Gaudry, "Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem", Journal of Symbolic Computation 44 (2009)
  4. C. Diem, "On the discrete logarithm problem in elliptic curves", Compositio Mathematica 147 (2011)
  5. S. D. Galbraith and P. Gaudry, "Recent progress on the elliptic curve discrete logarithm problem", Designs, Codes and Cryptography 78 (2016)