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 | 17e mod 10163 | factorisation |
|---|---|---|---|
| 1 | 5185 | 195 | 3 · 5 · 13 |
| 2 | 7311 | 315 | 32 · 5 · 7 |
| 3 | 6366 | 484 | 22 · 112 |
| 4 | 1886 | 3276 | 22 · 32 · 7 · 13 |
| 5 | 4734 | 9216 | 210 · 32 |
| 6 | 1732 | 64 | 26 |
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.
| ℓ | log mod 5081 | square mod 10163? | log mod 2 | log17 ℓ |
|---|---|---|---|---|
| 2 | 3676 | no | 1 | 8757 |
| 3 | 4311 | yes | 0 | 9392 |
| 5 | 4285 | no | 1 | 4285 |
| 7 | 4566 | yes | 0 | 4566 |
| 11 | 4588 | yes | 0 | 4588 |
| 13 | 1670 | yes | 0 | 1670 |
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:
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,
The order of x1 and x2 does not matter, so rewrite S3 in e1 = x1 + x2 and e2 = x1x2, which lowers the degrees:
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
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 + φ:
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
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
| # | m | m ≡ … (mod 69,383) |
|---|---|---|
| 1 | 28924 | −log P118 + log P242 |
| 2 | 46502 | log P12 + log P60 |
| 3 | 11914 | log P99 − log P186 |
| 4 | 26091 | −log P73 − log P176 |
| 5 | 59935 | log P39 + log P45 |
| 6 | 66930 | −log P123 + log P204 |
| 7 | 46064 | log P133 − log P239 |
| 8 | 24430 | log P40 − log P81 |
Each relation involves at most two unknowns, so the matrix is extremely sparse:
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
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
- L. Adleman, "A subexponential algorithm for the discrete logarithm problem with applications to cryptography", FOCS 1979
- I. Semaev, "Summation polynomials and the discrete logarithm problem on elliptic curves" (2004)
- P. Gaudry, "Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem", Journal of Symbolic Computation 44 (2009)
- C. Diem, "On the discrete logarithm problem in elliptic curves", Compositio Mathematica 147 (2011)
- S. D. Galbraith and P. Gaudry, "Recent progress on the elliptic curve discrete logarithm problem", Designs, Codes and Cryptography 78 (2016)