Main Page   Reference Manual   Compound List   File List  

Cracking parameter a of the elliptic curve


As was deduced from the brute force point counting data for all possible elliptic curves of the form x3 + ax2 + b = y2 + xy over binary fields up till and including extension degree m = 10, the values of parameter a can be devided into two sets, both of a size q/2, where q = 2m is the cardinality of the field and therefore equal to the number of possible values of a.  Let us call these two sets A0 and A1 so that A0 $\cup$ A1 = $\mathbb{F}_q$, A0 $\cap$ A1 = $\emptyset$ and A0 = A1 = q/2.

Then furthermore it was found that A0 and A1 are only a function of the field (GF(2m)/<tm+tk+1>) and not of b.  Let a0 $\in$ A0 and a1 $\in$ A1, and then define the curves E0 and E1 to be E0: x3 + a0x2 + b = y2 + xy and E1: x3 + a1x2 + b = y2 + xy, then it was found that for some fixed b also #E0 and #E1 are fixed (not depending on the specific choice of a0 and a1 respectively) and that #E0 + #E1 = 2(q + 1).  (Note: the notation #E is often used in literature to denote the cardinality of the Abelian group formed by the points of the elliptic curve E).

We would like to find how A0 and A1 depend on the field parameters, because that will reduce the amount of computations needed during the continuation of this research dramatically, as then we only have to try two values of a instead of q values.

A hyperplane

The finite field $\mathbb{F}_{2^m}$, called a binary field, can be viewed as a vector space of dimension m over $\mathbb{F}$2.  That is, there exists a set of m elements { $\alpha$0, $\alpha$1, ..., $\alpha$m-1} in $\mathbb{F}_{2^m}$ such that each a $\in$ $\mathbb{F}_{2^m}$ can be written uniquely in the form

\[ a = \sum_{i=0}^{m-1} c_i\alpha_i \]

where ci $\in$ {0,1}.

The set { $\alpha$0, $\alpha$1, ..., $\alpha$m-1} is called a basis of $\mathbb{F}_{2^m}$ over $\mathbb{F}$2.  We can then represent a as a binary vector (c0, c1, ..., cm-1).  Libecc uses the polynomial basis, so in our case we just have $\alpha$i = ti where t is the fixed complex (or whatever) root of our reduction trinomial tm + tk + 1.  (Note that it is possible to chose another basis, called a normal basis, of the form { $\beta$, $\beta$2, $\beta$22, ..., $\beta$2m-1} where $\beta$ $\in$ $\mathbb{F}_{2^m}$.  It is well known that such a basis always exists).

The observation that A0 is exactly half of the total space, and considering that there are only two possible values per 'dimension', indicates that A0 is a subspace of $\mathbb{F}_{2^m}$ of one dimension less than $\mathbb{F}_{2^m}$

It seems highly unlikely that this subspace would be 'curved'.  I cannot prove this at this point, but it seems to me that there must be some kind of symmetry between the different dimensions: when we exchange any two coordinates then there shouldn't be a dramatic impact on the other coordinates.  One property of a given coordinate ci that I expect to stay fixed under the permutation of the other coordinates is the property of whether or not toggling ci causes us to switch between A0 and A1.  This doesn't mean that a permutation of the other coordinates doesn't cause us to switch between A0 and A1 too, but it shouldn't cause us to change from switching to non-switching. 


A0 is a hyperplane.

As one of the goals of this project is to reach people who did not study mathematics, lets first explain what a hyperplane means.  Consider some n-dimensional vector space for which there exists an orthogonal basis.  An orthogonal basis is a basis of elements (vectors) of that vector space that are all orthogonal to eachother.  Orthogonal means, in terms of vectors, that they make an angle of 90 degrees with eachother.  When two vectors are orthogonal, then their inproduct will be zero.  I hestitate to explain inproduct, because when you don't know that then I doubt you would be reading this in the first place.  But why not, the inproduct of two vectors can be calculated by multiplying their coordinates pair-wise and then summing up all those products.  Thus, if one vector has coordinates (1,1,0,0,1,0,1) (in some seven dimensional space) and another one has coordinates (0,0,1,1,0,1,0) then they make an angle of 90 degrees because 1*0 + 1*0 + 0*1 + 0*1 + 1*0 + 0*1 + 1*0 = 0.  A hyperplane is a subspace of one dimension less than the space in which it is contained (mathematicians would say, of codimension 1) that is 'flat'.  That means that there exists a fixed vector n that that is a normal of the hyperplane at any point (it makes an angle of 90 degrees with the hyperplane at any point; or in other words with any vector that is the result of subtracting two arbitrary, though distinct, vectors that are element of the hyperplane).  Ok, by now you should get the picture that the thing is 'flat'!

Let us next show that a hyperplane indeed fulfills the intuitive feeling that whether or not toggling any bit of a causes us to either switch between A0 and A1 or not, independent of the choice of the other bits.  Lets use the notation from above and write a as a binary vector (c0, c1, ..., cm-1) where ci $\in$ {0,1} represents the bits of a.  Furthermore, let n be represented by the binary vector (n0, n1, ..., nm-1).  Without loss of generality, we can chose a = 0 = (0, 0, ..., 0) to be element of A0 (it has to be an element of either A0 or A1, so why not A0).  Assume that A0 is a hyperplane and that n is the normal of that hyperplane.  Then the angle that the vector n makes at any point a0 $\in$ A0 will be 90 degrees, as per our definition that n is the normal of the hyperplane A0.  And that means that the inproduct of n with a0 - ai will be 0 for any arbitrary ai $\in$ A0.  Therefore also for ai = 0.  Let (a0,0, a0,1, ..., a0,m-1) be the vector representation of a0 then the inproduct can be written as $\sum_{i=0}^{i=m-1}n_ia_{0,i} = 0$ [mod 2].  And since the ni are fixed, this clearly shows that when ni = 0 then changing a0,i has no influence on the result of the inproduct and therefore will not cause a change of a0 being an element of A0.  While when ni = 1 then changing the corresponding bit a0,i will toggle the outcome of the inproduct and hence cause that vector not to be an element of A0 anymore.  And this is independent of the value of any of the other bits.

Understanding the above (and still assuming that A0 is indeed a hyperplane of course) it is very easy to find the normal (n0, n1, ..., nm-1).  One only has to try each value of a with exactly one bit set (which are only m different values).  Let this single bit be cj so that

\[ c_i = \begin{cases} 0 & i \neq j \\ 1 & i = j \end{cases} \]

If, using this a, the resulting curve has the cardinality #E0, the cardinality corresponding to A0, then the inproduct has to be 0 (because we defined that a = 0 is element of A0).  The inproduct will therefore have to equal 1 precisely for each j that corresponds to A1 and thus has a cardinality #E1 $\neq$ #E0!  And the inproduct will only be 1 when nj = 1.

An algorithm for finding the normal n of hyperplane A0 could therefore be the following:

  1. Find the cardinality of the curve with a = 0 and some fixed b (#E0).
  2. Find the cardinality of all curves with a parameter a that has exactly one bit set, cj, using the same fixed parameter b.
  3. If the cardinality of the curve with just cj set is equal to #E0 then nj = 0, otherwise nj = 1.

There is a little problem with this algorithm.  This project has two goals: 1) to make elliptic curve cryptography more accessible to people without a mathematic university degree, and 2) to be the first Open Source project providing the means to generate your own cryptographically safe curves, which basically comes down to providing the means to determine the cardinality of an arbitrary elliptic curve.  Therefore, an algorithm with the phrase "Find the cardinality of all curves ... blah blah" is easier said than done.  Surely, we can do the above brute force, and it would be feasible for curves over fields up till extension degrees of m = 31, and that might be enough to guess a relationship between A0 and m, but... we still have a hypothesis to prove too, namely that A0 is indeed a hyperplane and using the above algorithm won't prove that at all, it will just give results.  Therefore, it would be necessary to check in addition whether or not the resulting normal n is indeed a normal to all a0 $\in$ A0!  And determining the cardinality of the curves for any a is really too much and/or will not give enough data points to feel secure about the hypothesis...

Time to become really smart therefore (and believe it or not but I am actually proud of the following, heheh). 

Suppose for a moment that #E0 is a multiple of 4 (as is the case as I will show below).  That is, #E0 = 4k for some k $\in$ $\mathbb{N}$.  Then #E1 = 2(q + 1) - #E0 = 2(2m + 1) - 4k $\equiv$ 2 mod 4 for m $\geq$ 1.  In other words, then #E1 is not divisable by 4.

Further, recall that the order of any point on the curve devides the cardinality of the curve.  That means that if we can find any point that has order 4, then the curve must have a cardinality that is divisable by 4.  Moreover, we are free to chose any arbitrary value of b for this investigation (as A0 does not depend on it).  So, we can chose b = 1.

Then it is easy to prove that there is always a solution to the curve with a = 0 with x coordinate 1.  Recall that E0: x3 + a0x2 + b = y2 + xy and set a0 = 0, b = 1 and x = 1 to get 0 = y2 + y, which has two solutions y = 0 and y = 1.  And thus, the point P = (1, 0) is an element of this curve.  Now lets calculate the order of P.  Doubling the point, using the known rules,

Doubling a point P

If Px = 0, then 2P = 0.

Provided that Px is not 0,

2P = R where

s = Px + Py / Px

Rx = s2 + s + a and Ry = Px2 + (s + 1)Rx

gives us the following for our P = (1, 0)s = 1 + 0 / 1 = 1, Rx = 1 + 1 + 0 = 0 and Ry = 1 + (1 + 1)0 = 1.  In other words 2P = (0, 1).  And because now the x coordinate is 0, doubling this point again results in 0 (the "point at infinity").  So, the order of this point is 4 independent of the extension degree of the field (we only used that the field characteristic is 2)!

This in turn means that the cardinality of every elliptic curve of the form E01: x3 + a0x2 + 1 = y2 + xy over $\mathbb{F}_{2^m}$, with a0 $\in$ A0 is a multiple of 4, for any m.  Conversely, also for any m, every elliptic curve of the form E11: x3 + a1x2 + 1 = y2 + xy over $\mathbb{F}_{2^m}$, with a1 $\in$ A1 is not divisable by 4, as was shown above.

As we saw before, there will always be a solution to the general elliptic equation E: x3 + ax2 + b = y2 + xy.  for which x $\neq$ 0, let us call those solutions (x, y) for now and remember that x $\neq$ 0.  But there does not necessarily exist a solution with x = $\sqrt[4]{b}$ (huh, where did that come from? Well, that will become clear in a minute).

Please note that the only solution to x4 = b is the unique x = $\sqrt[4]{b}$, because as we saw before there is only a single solution for a square root in a field with characteristic 2, and likewise there is only a single solution for $\sqrt[4]{b} = \sqrt{\sqrt{b}}$.

Consider the equation

x3 + ax2 + x4 = y2 + xy

This equation can only ever be true when x = $\sqrt[4]{b}$, because x and y are given to satisfy the curve equation and thus the above equation is equivalent with x4 = b (just add the curve equation to it).

We can rewrite this equation as x4 + y2 + x3 + xy + ax2 = 0 and then, remembering that x $\neq$ 0, divide both sides by x2 to get

x2 + y2/x2 + x + y/x + a = 0

Because of the field characteristic 2, we have x2 + y2/x2 = (x + y/x)2.  Then, with s = x + y/x, the equation becomes equivalent with

s2 + s + a = 0

Now looking again to the rules for point doubling, this means that adding (x, y) to itself will result in a point with x-coordinate 0, if and only if x = $\sqrt[4]{b}$!  In other words, when ( $\sqrt[4]{b}$, y ) is a solution of the elliptive curve then this point will have order 4 and the cardinality of the curve will be a multiple of 4 and the chosen parameter a must be element of A0.  However, if there is no solution with x = $\sqrt[4]{b}$ then there exists no point with order 4, and thus 4 does not devide the cardinality of the curve and the chosen parameter a must be element of A1

This result did not use my hypothesis that A0 is a hyperplane, but it also doesn't give us a formula for A0.  We'd still have to try every possible value of a, but at least we don't have to calculate a cardinality anymore!

Assuming that A0 is a hyperplane however, we can now formulate the much faster algorithm (using x = b = 1, and using the fact that a with just bit cj set is equal to tj):

  1. Try to solve the equation y2 + y + tj = 0, where j runs over all bits of a, 0 $\leq$ j < m.
  2. If there is a solution then nj = 0, otherwise nj = 1.

This algorithm is fast enough for every m and will suffice to find two values of a that do not result in two isomorphic curves.  Since we can always use a = 0 for E0 it will even suffice to find just a single j for which the above equation is not soluble.

If A0 is not (always) a hyperplane then in order to find all of A0 we'd have find all a0 for which there exists a solution for y2 + y + a0 = 0.  Also in this case it will suffice to find just a single a1 for which the equation is not soluble, but - it might come in handy later when we actually known what A0 is, and therefore I'd like to prove that it is, in fact, a hyperplane.

In order to do that we need two new mathematical tools.  The Frobenius automorphism and the trace.  I dedicated a special chapter to each, so please follow those links and get yourself familiar with these expressions.


Ok, now we have the mathematical tools to actually prove that A0 is a hyperplane.

Recall that A0 exists of all elements a0 for which there exists a y such that y2 + y + a0 = 0.  Then, using theorem 5, we can immediately conclude that those are the values for which the trace is 0.  And thus

\[ \begin{matrix} Tr(a_0) = 0 \\ Tr(a_1) = 1 \end{matrix} \]

Let tj be an element of A1, so that Tr(tj) = 1, then it is now easy to see that toggling that bit will switch between A0 and A1 independent of the value of the other bits:

\[ Tr(a + t^j) = Tr(a) + Tr(t^j) = Tr(a) + 1 \]

And that proves that A0 (and A1) is a hyperplane.

Our quest continues in the next chapter Cracking parameter b of the elliptic curve .

Copyright © 2002-2008 Carlo Wood.  All rights reserved.