I received a representation of a point on an elliptic curve $GF(2^m)$ (with curve coefficient A, B) in specific format and some description how to decode it but not all is clear to me. I would be appreciate to someone to explain some issues to me. So I have an array of the bytes $\tilde{P}$ (array's size equal to m) and to get a point $P= (x_p, y_p)$ from it I need to do the following:

  1. If $\tilde{P} = 0$, we set $x_p=0, y_p=\sqrt{B}$, and then go to step 7
  2. We take the right byte $k$ of the $\tilde{P} = (\tilde{P}_{m-1},..., \tilde{P}_0)$, i.e $k = \tilde{P}_0$
  3. We set the the coordinate $x_p$ of the $P$ point as $x_p = (x_{p, m-1}, ... , x_{p,1}, x_{p,0}) = \tilde{P}$ and then make $x_{p,0} = 0$. But if trace $tr(x_p)\neq A$ we set $x_{p,0} = 1$
  4. Calculate $w=x_p^3 + A x_p^2 + B$
  5. Solve the equation $ z_2 + z = v, v = w x_p^{-2}$
  6. If trace $tr(z)$ of the solution $z = (z_{m-1},...,z_0)$ is equal to $k$ then we take $y_p = zx_p$, otherwise $y = (z+1) x_p$
  7. The result of the calculation is a point $P = (x_p, y_p)$

So the first (1) item above is clear absolutely :)

Second (2) item is clear and the trouble begins from (3) item because i need calculate $tr(x_p)$ operation to determine $x_{p,0}$: it can be 0 or 1 here. How could i calculate the $tr$ ? Can i use any simplifications?

(4), (5) are clear as well

In (6) we need to calculate $tr$ again, but in my case the right byte $k$ from $\tilde{P}$ equal to 40 !!! (not to 0 or 1)

So my question is whether can i utilize mentioned instructions to restore point or maybe it has mistakes in description??

The described method appears to be point decompression. Take care first that what you call "bytes" are actually bits. The value $k$ must be the right bit (hence $0$ or $1$), not the right byte.

Below is the general treatment of the question.

Binary Fields

Everything here happens in a binary field $GF(2^m)$ where things are somewhat different from integers. In a nutshell:

  • Every element of $GF(2^m)$ can be expressed as a polynomial of degree at most $m-1$, with coefficients in $GF(2)$. I.e. an element $d$ will be: $$ d = \sum_{i=0}^{m-1} d_i X^i $$ such that each $d_i$ is either $0$ or $1$ (it's a bit).

  • Addition is done term-by-term in $GF(2)$, with no carry propagation of any sort: if $f = d + e$, then $f_i = d_i + e_i \bmod 2$. It is usually expedient to represent an element of $GF(2^m)$ by a string of bits (i.e. an array of bytes, each byte containing a bit); in that case, addition is really a bitwise XOR. Note that the addition of an element with itself yields $0$ (that's why the field is called "binary").

  • Multiplication is more complicated: you multiply the polynomials together (again, the coefficients are $0$ or $1$, and there is no carry to propagate anywhere); then the result must be reduced modulo the irreducible polynomial of degree $m$ that defines the field representation.

  • Every element in $GF(2^m)$ is a square, and has a unique square root.

  • Squaring in $GF(2^m)$ is actually known as the Frobenius automorphism and preserves both addition and multiplication: \begin{eqnarray*} (ab)^2 &=& a^2 b^2 \\ (a+b)^2 &=& a^2 + b^2 \\ \end{eqnarray*} (The latter holds because $(a+b)^2 = a^2 + 2ab + b^2$, but $2 = 0$ in $GF(2^m)$.)

  • Since the field $GF(2^m)$ has order $2^m$, it follows that for every element $z \in GF(2^m)$, we have $z^{2^m} = z$.

Trace and Half-trace

Let's now consider the equation: $$ z^2 + z = \beta $$ in $GF(2^m)$. To analyze it, it is convenient to define the trace: $$ \text{Tr}(z) = \sum_{i=0}^{m-1} z^{2^i} $$ (This is still an addition in $GF(2^m)$. We don't use integers anywhere here.)

Now note that the trace is linear, i.e. $\text{Tr}(z+z') = \text{Tr}(z) + \text{Tr}(z')$ for all $z$ and $z'$ in the field (this is because the trace is really a lot of Frobeniusing). Moreover, the trace is preserved by squaring: \begin{eqnarray*} \text{Tr}(z^2) &=& \sum_{i=0}^{m-1} (z^2)^{2^i} \\ &=& \sum_{i=0}^{m-1} z^{2^{i+1}} \\ &=& z^{2^m} + \sum_{i=1}^{m-1} z^{2^i} \\ &=& z + \sum_{i=1}^{m-1} z^{2^i} \\ &=& \text{Tr}(z) \\ \end{eqnarray*} We used here that $z^{2^m} = z$. The squaring simply "rotates" the term, so we end up on the same value at the end.

Frobenius strikes again: since squaring preserves additions and multiplications, it will also preserve anything built out of additions and multiplications, including the trace. Thus: $$ \text{Tr}(z^2) = (\text{Tr}(z))^2 $$ Taking the two together, we find that: $$ \text{Tr}(z) = (\text{Tr}(z))^2 $$ for all elements of $GF(2^m)$. There can be only two elements in a field that are equal to their own square ("$t^2 = t$" is a polynomial equation of degree $2$, and thus can have only two solutions in a field). The values $0$ and $1$ are equal to their own square. This therefore demonstrates that the trace, formally an element of $GF(2^m)$, can only be $0$ or $1$.

Let's come back to our equation: $$ z^2 + z = \beta $$ If we apply the trace on both side, then we get: $$ \text{Tr}(z^2 + z) = \text{Tr}(\beta) $$ By linearity, and by equality of $\text{Tr}(z^2)$ with $\text{Tr}(z)$, we get that the left half of this equation can only be $0$. Therefore: if $\text{Tr}(\beta) \neq 0$, then there is no solution.

We will now show that if $\text{Tr}(\beta) = 0$, then there are exactly two solutions, that can be built with the half-trace.

The half-trace is defined as: $$ \text{H}(z) = \sum_{i=0}^{(m-1)/2} z^{2^{2i}} $$ It really is the sum of half of the terms we used in the trace, hence the name of "half-trace". Also, an important note: I used the fact that we are working in $GF(2^m)$ for an odd integer $m$ (you did not say it, but I am willing to bet on it because $m$ is prime for all standard curves, and there are good reasons for that).

The half-trace, contrary to the trace, is not reduced to $0$ or $1$; however, it is still linear, because Frobenius. Consider now an element $z$, and compute the following: \begin{eqnarray*} (\text{H}(z))^2 + \text{H}(z) &=& \sum_{i=0}^{(m-1)/2} z^{2^{2i+1}} + \sum_{i=0}^{(m-1)/2} z^{2^{2i}} \\ &=& z^{2^m} + \sum_{i=0}^m z^{2^i} \\ &=& z + \text{Tr}(z) \\ \end{eqnarray*} Here, I am relying on the fact that $m$ is odd (I told you it's important), so that the first sum yields an extra $z^{2^m}$; and, of course, it is still a total Frobenius fiesta (you'll get used to it).

This expression gives us a solution to our equation. Indeed: $$ (\text{H}(\beta))^2 + \text{H}(\beta) = \beta + \text{Tr}(\beta) $$ We saw that our equation can have solutions only if $\text{Tr}(\beta) = 0$. If that is the case, then one solution is $z = \text{H}(\beta)$.

It is easy to see that is $z$ is such that $z^2+z = \beta$, then $z+1$ is also a solution (because $(z+1)^2 + z = z^2 + 1 + z + 1 = z^2 + z$). Our equation is polynomial and of degree $2$, so it cannot have more than two solutions.

To sum up: the solutions to $z^2+z = \beta$ are $\text{H}(\beta)$ and $\text{H}(\beta)+1$. These solutions work only if $\text{Tr}(\beta) = 0$; otherwise, the equation has no solution. Note that "adding $1$" means, in a binary field, XORing the low-order bit with a $1$. In other words, the two solutions, when they exist, differ only by their low-order bit.

Point Decompression

Let $E$ be the elliptic curve of equation $y^2 + xy = x^3 + Ax^2 + B$ over $GF(2^m)$, for two given constants $A$ and $B$. Suppose that I give you the coordinate $x$, and I challenge you to find the coordinate $y$.

If $x = 0$, then the equation becomes $y^2 = B$, so a solution $(0,y)$ must be such that $y$ is a square root of $B$. In a binary field, $B$ has exactly one square root, so this is one solution.

If $x \neq 0$, we can divide both sides of the curve equation with $x^2$. We get this: $$ \left(\frac{y}{x}\right)^2 + \frac{y}{x} = x + A + \frac{B}{x^2} $$ We recognize here the equation $z^2+z = \beta$, by setting $z = y/x$ and $\beta = x + A + B/x^2$. We know how to solve that: with the half-trace, as described above.

So solve it to get $z$, then multiply by $x$ to get $y$. And you're done.

Note that when $z^2 + z = \beta$ has solutions, it has two solutions, that differ by the last bit. Hence, $y$ will be equal to either $zx$ or $(z+1)x$. The choice of the solution must be conveyed in the encoding.

Extra Subtleties

The method you describe is more or less point decompression. However, there is an extra twist. True point decompression requires $m+1$ bits: $m$ bits for $x$, and the extra bit for the choice of the solution for $y$. However, once can save one bit, in the following way.

A normal (non-supersingular) curve over $GF(2^m)$ has an even order. For cryptographic purposes, we want to work in a subgroup of prime order, hence odd. Standard curves will thus have order $2q$ (or $4q$) for some prime integer $q$. We are thus interested only in half the points at most.

Moreover, the "interesting half" can be distinguished with the trace! It can be shown that for the "interesting" points (those in the subgroup of prime order), the trace of the $x$ coordinate must equal the trace of $A$. Thus, we can use the trace of $x$ and infer its last bit.

So back to your description:

  1. If the provided $x$ coordinate is $0$, then the solution is $(0,\sqrt{B})$. Done.
  2. Separate the rightmost bit of the provided input, and call it $k$; this is the bit that will be used to choose the solution for $y$.
  3. Decode the input as coordinate $x$. Note that the rightmost (least significant) bit is missing, since that slot was used for bit $k$, so just suppose that the missing bit is $0$. However, if the result has the wrong trace (i.e. $\text{Tr}(x) \neq \text{Tr}(A)$, then flip that bit (which has the effect of flipping the trace, thus restoring the equality). Note: in your description, you compare $\text{Tr}(x)$ with $A$ itself; this is because you work with one of the standard curves that have $A$ equal to $0$ or $1$, not any other element of $GF(2^m)$.
  4. Compute $w = x^3+Ax^2+B$. This is the right-hand side of the curve equation. No worry here.
  5. Compute $v = wx^-2$ and solve the equation $z^2+z = v$; this is where the half-trace is used. Take care that there may be no solution, in case the provided $x$ is not actually the $x$ coordinate of a valid curve point; this may happen because the encoded point comes from the outside, where there are evil people who may send you invalid data.
  6. The bit $k$ that you used before tells you which solution $z$ you must keep. The way you describe it appears to be somewhat mangled. One simple way is to say that $k$ and the low bit of $z$ must match, but there can be other conventions, including stating that $\text{Tr}(z)$ must match $k$. In standard point decompression, there is no trace here, bit $k$ is supposed to be equal to the low-order bit of $z$. However, standard (as in "ANSI X9.62") point compression does not use the extra trick of not encoding the low order bit of $x$, so I must assume that you are doing something non-standard here.
  7. This step is trivial.

Now for computing the trace and the half-trace. The expressions above work, but are complicated. Since the trace is linear, and outputs only $0$ or $1$, then it follows that $\text{Tr}(z)$ is just the XOR of a few bits of $z$. Which bits to use depends on the field representation, but usually there won't be many. For the half-trace, the result has length $m$ bits, so it can still be done with linear algebra: for a given input $z$, XOR together some precomputed values $h_i$ for all $i$ such that $z_i = 1$. These $h_i$, again, depend on the field definition; precomputing them is a nice exercise. Take care that table lookups, if not done carefully, are prone to make side-channel leaks.

All of this assumes that you can compute things in $GF(2^m)$. This requires functions to add, multiply, and divide values in that field. Implementing these correctly is not easy. Some guidance can be obtained from the Guide to Elliptic Curve Cryptography, especially section 2.3, which talks about binary fields (and it so happens that the chapter 2 is a free download as a PDF!). Making such code constant-time is possible, but harder (especially for division). For a basic Diffie-Hellman, decoding of points occurs on data which has travelled over the wire, hence non-secret, which helps here. Implementing cryptographic algorithm is a path fraught with perils, in particular side-channel attacks; elliptic curves over binary fields are certainly not the easiest thing to do among cryptographic implementations.

  • Thank you @Thomas for your extended answer! Now many important things in one place. But the issues with calculating trace and half trace are obscure. Where could I take "bits of x" to do XOR operation to calculate $tr(x)$. To calculate half-trace $H(z)$ i use a algorithm 3 from x9.62 d.1.6. Unfortunately, using this algorithm i have in all cases $w\neq 0$ and no solutions exist, that i don't understand why – Rotvik Knuzich Oct 3 at 12:19
  • For the trace, you simply use the complicated formula with all the squarings on "10000...", "01000...", "00100...", and so on. The cases where you get a 1 will correspond to the "bits of x" that you need to XOR to compute the trace of x. This relies on linearity, i.e Tr(a+b) = Tr(a)+Tr(b), both additions being bitwise XOR. – Thomas Pornin Oct 3 at 13:09
  • You are using a draft version of X9.62. In the actual standard (I have X9.62-2005), the "algorithm 3" is not present (only 1 and 2). Maybe it does not actually work? Drafts sometimes contain mistakes. – Thomas Pornin Oct 3 at 13:12
  • you said about multiplication of the binary fields as "... multiply the polynomials together (again, the coefficients are 0 or 1, and there is no carry to propagate anywhere); then the result must be reduced modulo the irreducible polynomial ..." but how is it possible to multiply polynomials without any carry propagation? it will be the same polynomial after multiplication!! – Rotvik Knuzich Nov 24 at 18:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.