Modulo Errors

On Friday I gave a geometry club seminar, speaking about some of the computational aspects of discrete-logarithm cryptography in general and as implemented for elliptic curves. My notes supplement rather than completely describe the talk, being heavier on the formalities and lighter on the narrative.

The topics covered are: Diffie-Hellman and one-way functions for key exchange; the generic Discrete Logarithm Problem and BSGS algorithm; scalar multiplication- addition chains, fast exponentiation, m-ary methods and windowing; group law implementations, Side-channel attacks and the Edwards form.

I’ve discussed several of these ideas elsewhere on this blog, as well as the cryptanalysis ideas I mentioned on the day but which are not in the notes. I also refered to a recent real-world example of a side-channel attack; see this story from The Register for details.

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

Update 4/v/07: I’ve switched from Cantor’s definitions for a curve of the form y²=f(x) to a more general form, following the notation of a paper by Tanja Lange; that also describes many efficiency gains for these calculations, none of which I have yet adopted… I’m also implementing these procedures in SAGE, which seems a more natural environment. So consider all genus 2 stuff as work in progress!

jac is an implementation of the group law on the jacobian of a genus 2 hyperelliptic curve over a finite field, to work with the generic_group procedures described previously. Standard version is for Maple 10; you can also get a version for Maple 9, but this may not be updated as frequently.

An arbitrary divisor D is now either a list [a(u),b(u)] or the identity element zero. Addition of two such divisors D,E is given by g2JacGroupLaw(D,E) whilst g2JacMinus(D) gives the inverse. So these functions can be used as arguments for ncopies and so on. To set up the worksheet, specify a characteristic p; a degree five monic squarefree polynomial f(u) and a polynomial h(u) of degree at most 2. Only rational divisors and prime fields seem to work: working mod p generates sufficiently ugly Maple code to discourage me from trying extension fields there.

Also included are a couple of ways to get random divisors to compute with. randomDiv is incredibly slow as it naively tests random choices of a (monic quadratic) and b (linear) for suitability (that is, a dividing b^2+bh-f). randPoint(f,h) is smarter (transforming to y²=g(x), using the legendre symbol to test random choices of x for square g(x) then finding a root and transforming back to a suitable y) and of course you can combine two points into a weight 2 divisor using the group law.

Order computation, even with BSGS, becomes very slow for less than staggering values of p: this is of course the point cryptographically! For instance, it took my university workstation about 11 hours to find the order of a randomly constructed divisor from a curve over a field with around a hundred-thousand elements.

Last time I introduced the idea of divisors on a curve; but an observant reader may have noticed that along the way the idea of rational points seemed to be lost. Further, whilst the Riemann-Roch theorem guarantees that a divisor from the jacobian will have a reduced representative, no indication was given as to how that representative is to be found. In this post I’ll try to clear up both of these issues.

Recall that a semi-reduced divisor D from the jacobian takes the form (Σ_i^rP_i) - r∞ where the P_i are points (x_i,y_i) of C. We will represent this by a pair of polynomials D=div(a(u),b(u)) with the following properties:

such that b has degree less than that of a, and the appropriate multiplicity for repeated points- i.e., if P_i occurs k times in the semi-reduced representation of D, then (u-x_i)^k divides b-y_i. This ensures uniqueness.

The empty divisor (zero element of the jacobian) is denoted by div(1,0); if a is linear (and hence b constant) then the divisor corresponds to a single point of C; for the point (x,y) the divisor is div(u-x,y). The degree of a is described as the weight; ‘most’ reduced divisors will be of weight g. Recall that the co-ordinates of a point were only required to be in A rather than K; we describe a divisor as rational over K if the coefficients of a and b are from K. Beware that a rational divisor may therefore be the sum of points which are not K-rational points of the curve; however, a weight 1 rational divisor obviously corresponds to a K-rational point.

The K-rational principal divisors of C are a subgroup of P₀ and their image in J, J_K, the subgroup of rational divisors of the Jacobian, is the object of computational interest. The K-rational points of C are then identified with a subset of J_K; namely the divisors of weight at most 1; except in genus 1 (where they are J_K), this isn’t a subgroup due to the lack of closure.

So we wish to work with rational divisors from J_K.Given such divisors of the form div(a,b), it is undesirable to construct their sum by ‘unpacking’ the points P_i and forming new polynomials as the co-ordinates (roots of a, evaluations of b) might not be from K but A. Fortunately, it is also unnecessary: the only complications are connected to repeated points or the combination of a point and its negative; careful manipulation of gcds allows for direct computation of the semi-reduced form. See ¹ for details, which also describes moving from semi-reduced to reduced form. To do this, note that for a divisor D=div(a,b), the divisor E=-((b-v)-D)=div(a’,b’) is equivalent to D with deg(a’)=max(2g+1,2)-deg(a); thus by repeated iteration we can move to a reduced representative (the explicit formulae are a’=(f-b²)/a, b’=-b mod a’).

Maple procedures to do all this will be provided in the next post.

Reference
¹Computing in the Jacobian of a Hyperelliptic Curve D.Gantor Mathematics of Comptuation Vol.48.No.177 (Jan., 1987).

One of the most celebrated properties of elliptic curves is that the set of rational points is a group, with a highly geometric explanation of the group law: the ‘chord and tangent’ process. Two points and their sum are linked by consideration of the intersection of straight lines with the curve: as the curve is a cubic, there are three intersections (subject to some technical book-keeping with repeated points and the point ‘at infinity’). Such an approach clearly won’t transfer immediately to curves given by higher degree polynomials, as there will be more intersections, but as there are only finitely many, one would still hope to be able to define relationships between points. For instance, on an elliptic curve, if A, B and ∞ are colinear then B is -A; thus if on a more complicated curve we had A,B,C,∞ colinear it might make sense to think of C as -(A+B), and then A+C as -B and so on. That is to say, there may be relationships between groups of points rather than individual points.

In algebraic geometry, this (and much more) is captured by the notion of a divisor; rather than present them here in full generality, I will consider the specific case of divisors on (hyperelliptic) curves. These will then serve as the building blocks for a group structure connected to the curve which reduces in the special case of an elliptic curve to the familiar group of rational points.

To fix ideas, let K be a field of characteristic other than 2 with algebraic closure A. A curve C is described as a hyperelliptic curve of genus g if there is some degree 2g+1 polynomial f with distinct roots such that v²=f(u) is a model of C: so the familiar elliptic curves are the special cases with genus 1.

A point P on C is a pair (x,y) of elements of A (not K) satisfying y=f(x); or the point at infinity ∞. Then a divisor D of C is a finite formal sum Σ_im_iP_i for integers m_i and points P_i on C. D is described as having degree Σ_im_i; if all the m_i≥0 then we write D≥0. Formal (that is, pointwise) addition of divisors gives the additive group D of divisors; its identity is the divisor consisting of summing no points and it has a subgroup D₀ consisting of divisors with degree zero.

Any polynomial p(u,v) can be considered as a function on C of the form p=a(u)+b(u)v, since v²=f(u). If p vanishes at (x,y) then the order of the zero (x,y) of p is the exponent of the highest power of (u-x) which divides a²-b²f.

Thus we can define functions on C as h=p/q for p,q polynomials from K[u,v] such that v²-f(u) does not divide q(u,v): that is, q is not everywhere zero on C. Then h will have a finite set of zeros (those of p) and of poles (those of q); we associate to h a divisor, (h) = Σ_im_iP_i where the P_i are those zeros and poles and m_i their multiplicities:

If there is a nonzero function h on C such that D a divisor is (h), then D is described as principal. the principal divisors form a subgroup P of D₀ and hence D: the jacobian J of C is then the quotient D₀/P. That is, two divisors correspond to the same element of the jacobian if they differ by a principal divisor. This gives some idea as to how to simplify arbitrary divisors- we work in the jacobian and seek a simplest representative; that is, one comprised of the minimal number of points.

Consider that if (x,y) is a point P of C, then so is P’=(x,-y). The function u-x has zeros P and P’ with a double pole at ∞ so P+P’+∞ = (u-x) is principal and hence equivalent to zero mod P. Hence -P’ is equivalent to P-2∞ so we can rewrite divisors to only feature positive multiples of points other than ∞ Thus in J, where the degree is necessarily 0, any element has a representation

such that if P_i appears in D, then no P_j=P’ for any j different to i. Hence, any point of the form (x,0) will appear at most once. Such a representation is called semi-reduced; if r≤g then it is called reduced.

Remarkably, (by the Riemann-Roch theorem) any divisor in the Jacobian will have a unique, reduced representative (in other words, any divisor is the sum of a reduced divisor and a principal divisor). Now we can see what’s really going on with the elliptic curve group law: as a reduced divisor will have r≤1, it takes the form P-&infty; so there is an obvious isomorphism between the set of rational points and the Jacobian. Hence adding two points A,B on the curve gives rise to another point of the curve, by reducing the divisor A+B-2∞ to some representative C-∞ and setting A+B=C.

But with hyperelliptic curves, this needn’t be the case: the sum of two points is a perfectly good reduced divisor in the next simplest case of genus 2, for instance, so we can’t add two points and expect the answer to be a point. Hence we need to consider the divisors corresponding to rational points in the broader setting of the jacobian; to extract useful information about those points, we’ll need to consider the rational divisors. This motivates an alternative notation for divisors, more suitable to computation: I leave all these issues to the next post.

ella is an update of gla, the elliptic curve group law procedures, to work with the generic_group procedures described previously.

An arbitrary point P is now either a list [x,y] or the identity element zero. Addition of two such points P,Q is given by ellGroupLaw(P,Q) whilst ellMinus(P) gives the inverse. So these functions can be used as arguments for ncopies and so on. Setting up the curve is as described for gla: specify variables a_1 through a_6 and optionally set workModM and a modulus M for computation over prime fields. The getQuantities function is also included for convenience; order calculations and functions like the old mnadd should make use of the generic_group procedures and thus are omitted.

I’m keeping gla available for use with torsion_tools, most of the functions of the latter depend strongly on the underlying group being that of an elliptic curve so cannot be translated to generic form, so I can’t be bothered to update the notation from x,y to [x,y] !

Overview

For the last month or so I’ve been working with hyperelliptic rather than elliptic curves. This requires working in the Jacobian of the curve rather than the curve itself, but the basic computational tasks are of course the same: adding arbitrary points, multiplication by m, finding orders. I wrote Maple code for all of these in the elliptic curve case, but the simplicity of both the group law and the examples I worked on meant I could get away with brute force computation of these. But for higher genus (even genus 2), this becomes crippling very early on, so I needed some smarter methods. Having discovered that you can pass functions as arguments in Maple, it seemed best to divorce the group methods from the specifics of the group being computed with. To that end, I present generic_group, a set of Maple procedures for generic group algorithms.

A generic algorithm is one which only performs the group operation, inversion, or testing for equality. To that end, these procedures may take as arguments: elements; a function grouplaw that performs the group operation on an input of two elements; or another function groupminus that inverts its input element. Since I’m usually working with additive groups, the neutral element is given as zero, and so the supplied functions must be able to handle this.

The idea is that other sets of procedures will specify those functions: for instance, I’ve been writing procedures for the group of divisors of an algebraic curve: as a special case I have a function g2JacGroupLaw which will sum two rational divisors from the Jacobian of a genus 2 hyperelliptic curve. Rather than writing a multiplication by m function for such divisors, I just plug that function into the generic procedure for finding n copies of an element. I’ve updated my earlier elliptic curve procedures to this format as well.

The Procedures

Multiplication by n (ncopies and brutencopies)

A call of ncopies(n,g,grouplaw,groupminus) computes [n]g; it catches the special cases of n=0 (giving zero), n=1 (giving g) and n negative (giving [|n|](-g)).
This procedure uses around 2ceil(log₂n) instances of the group law by exploiting fast exponentiation, rather than naively adding successive terms. If out of boredom or to compare performance you want naive addition, you can use brutencopies(n,G,grouplaw,groupminus) instead.

Discrete Logarithm Problem (BSGSDL)

In the previous post I described the Baby Step, Giant Step algorithm for computing discrete logarithms, in the case of unknown order of the generator (Terr’s variant). BSGSDL(g,h,grouplaw) will use this to return an integer t such that [t]g=h; this assumes that there is such a t, i.e., that h is in <g>. beware that if it isn’t, the procedure will wander off to deep space and never terminate.

Order finding (BSGSOrder and bruteOrder)

Terr’s variant can be used to establish the order of an element by solving the DLP with h=zero; however you have to check that g itself is not the identity first. So BSGSOrder(g,grouplaw) will find the least t such that [t]g=zero. If you want to try this by checking successive multiples of g, you can use bruteOrder(g,grouplaw) instead; again, knowing nothing about the group neither of these procedures knows when to give up so can churn forever if g is of infinite order.

The discrete logarithm problem is the vital part of elliptic curve cryptography, but can be defined (to varying cryptographic strength) for any cyclic group:

Discrete Logarithm Problem (DLP)
Let G be a cyclic group, with operation ⊕. Let [n] represent (n-1)-fold application of ⊕ i.e., [2]g=g⊕g, [3]g=g⊕g⊕g etc.

Given g,h from G, the discrete logarithm problem is to find t such that [t]g=h.

The baby-step, giant step (BSGS) algorithm is a generic algorithm for solving the DLP- that is to say, it makes no appeal to properties of the group involved, merely calculating abstractly with ⊕. There is a theoretical upper bound to the effectiveness of generic algorithms, and BSGS approaches are of that order of magnitude.

The simplest demonstration of BSGS (the original by Shanks) assumes that g generates G, with both of known order n: recall that the group order is simply the number of elements it contains, whereas the order of an element g is the least n such that [n]g=id_G, should such a value exist. The order n of an element always divides the order of the group N, with equality when g generates G. Between the two there is also the exponent, the least value e such that [e]g=id_G for all g in G; for cyclic groups this is N, but for products of cyclic groups (the structure of groups of rational points) it is the lowest common multiple of their respective orders, and thus, although a divisor of N, may be significantly smaller than it.

So, if we can find an order m rational point on a curve, we know that the cardinality of the group of rational points is zero modulo m. By testing random points and taking the lowest common multiple of their order we can usually find the exponent e of the group. With luck, but not always, this will be large enough that when combined with bounds on the cardinality the latter is established exactly (as with modular information in the SEA algorithm).

But it is no good attempting to do so using an algorithm that requires the order of the point! There are BSGS algorithms for the DLP which can handle unknown order, for a given g we can apply these to solve for h=id_G in the cyclic group generated by g. Provided the algorithm gives the minimal t such that [t]g=h=id_G in G=<g>, then t is the order of g.

One such algorithm, by Terr, is given in Cohen and Frey’s Handbook of Elliptic and Hyperelliptic curve cryptography (my current bible!) It relies on the following observation:

Let T_n be the nth triangular number: that is, defined by the recursion T₁=0, T_n+1=T_n+n.

Then any non-negative integer t, there are unique integers j and k with t=T_j+1-k with 0≤k<j.

To see how, notice that there is a unique j such that t lies in the interval (T_j , … , T_j+1]=(T_j+1-j , … , T_j+1-0] and that this interval has width j so there is an appropriate choice of k.

We then suppose that t satisfies [t]g=h. Then we have [T_j+1]g=h⊕[k]g. So, instead of testing each [t] in turn until we hit equality, for a given j we need only test the ‘giant step’ [T_j+1]g against the set of ‘baby steps’ β={β_i}={h⊕[0]g,…,h⊕[i]g,…,h⊕[j-1]g. If that j yields no matches, we move to j’=j+1: by keeping track of [j]g at each iteration, the new T_j’+1 and the extra h⊕[j’-1]g are found by a single group operation each. Hence this is attractive from both storage and time complexity perspectives: we need only record the baby steps β, [j]g and a single giant step at any given iteration j, whilst the time complexity is of order t^1/2.

Terr’s BSGS variant for the DLP
Finds t such that [t]g=h for g generating G of unknown order, h from G.

Initialise β={β₀=h}, γ=δ=id_G, j=0. ((For each iteration, we have γ=[T_j+1]g and δ=[j]g)
Then loop over j as follows:

• Increment j by 1, then update:
• Set δ=δ⊕g=[j-1]g⊕g=[j]g.
• Set γ=γ⊕δ=[T_j]g+[j]g=[T_j+1]g.
• If j≥2 then
  • For s from 0 to j, if γ=β_s then return T_j+1-s
• Add β_j=β_j-1⊕g to β

I’ve implemented this generic DLP algorithm and an order-finding version (which requires you to catch g=id_G) as Maple procedures for arbitrary groups- details on that will be in the next post! BSGS-based approaches become impractical at finite field sizes well within the grasp of SEA for counting on elliptic curves; but are of interest in the higher genus case which lacks an Elkies procedure.

I managed to arrange a talk by Nina Snaith for the final event by the undergraduate maths club I helped set up this year. As at Durham, she spoke on her work connecting quantum chaos to the moments of the riemann zeta function, via random matrix theory. Turnout was good, including some postgrads and staff, and the advantage of hearing the talk here is that I benefit from any feedback or insights they have.

To calculate the moments requires knowledge of a particularly elusive coefficient g_k, about which very little is known: g₀ is trivially 1, Hardy and Littlewood established that g₁=1 in the early part of the 20th century, Ingham proved that g₂=2 in 1926. No progress was made until 1995, when Conrey and Ghosh conjectured that g₃ was, of all things, 42. At a conference in Vienna, Conrey and Gonek planned to present a conjecture for g₄; yet the random matrix theorists had a conjecture for all values of k. Following some frantic checking at a blackboard, it was confirmed that the two conjectures agreed for g₄=24024: and thus that quantum physics really could offer predictions about number theory!

One of my lecturers plugged the coefficients 1,1,2,42,24024 into the OEIS, and just one result comes up, sequence A039622. Curiously, this is about Young diagrams, which are linked to irreducible representations of the symmetric group. Young Tableau themselves describe a fairly elegant number theory puzzle. I’ve been studying representation theory this semester, and I’m always amazed by how different strands of mathematics can pull together like this- from quantum theory to distribution of primes to symmetry, somehow they’re all woven together.

For an overview of the current status of work on the Riemann Hypothesis, including Random Matrix Theory, see this article by Conrey. Marcus Du Sautoy’s the music of the primes also mentions Nina’s work, and Riemann’s own study of problems in Physics alongside the zeta function.

View as:   

First introduction to group theory via the properties of the general linear group.