Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From the ECDH demo here, if I generate a private key for Alice I can get _

P = 1175846487558108474218546536054752289210804601041

Which gives the following public key point.

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

For ECDSA public key compression the above coordinates would be prepended by 02 and the X coordinate would be used. So the compressed key for the above (based on X9.62) is:

02583857549063195252150226340830731484791130788759

If I only have the compressed key given above, how would I derive Y i.e. the uncompressed point?

share|improve this question
    
For ECDH you probably don't need to uncompress at all. For ECDSA you take the curve equation and solve for the unknown coordinate. The only tricky part is the square-root, which AFAIK can be solved by modular exponentiation. – CodesInChaos Jun 28 '13 at 10:40
    
You need to uncompress for ECDH too: for computations on the curve points, you have to know both coordinates. What you don't need to do with ECDH is to disambiguate between Y and -Y because at the end of ECDH you only take the X coordinate; so you must do the square root, but there is no need to keep around the least significant bit of Y. For ECDSA, you need the complete decompression, including the least significant bit. – Thomas Pornin Jun 28 '13 at 15:22
    
@ThomasPornin I didn't look into other curve shapes, but at least for Montgomery curves you don't need decompression for DH when you use x/z coordinates. – CodesInChaos Jun 28 '13 at 21:42
up vote 11 down vote accepted

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format includes the least significant bit of $Y$ in the first byte (the first byte is 0x02 or 0x03, depending on that bit): this bit is enough to know whether you got $Y$ or $-Y$ with the square root, and adjust in consequence.

All computations above are done in the base field, i.e. (usually) the integers modulo a prime integer. See this for square root extraction modulo a prime.


Edit: for binary curves, things are somewhat similar. We work in a field $GF(2^m)$, so addition is a XOR; the curve equation is $Y^2+XY = X^3+aX^2+b$ (generic equation for non-supersingular curves). When point $P = (X,Y)$, the opposite point is $-P = (X,Y+X)$. We assume that the point we are encoding and decoding has coordinate $X \neq 0$, because a point with such a coordinate $X = 0$ is equal to its opposite, i.e. has order $2$. In practice, when we work on such a curve, we really use a sub-group of order $r$ prime (generally, we arrange for the complete curve order to be equal to $2r$ or $4r$).

Since $X\neq 0$, we can define $Z=Y/X$, and divide the curve equation by $X^2$. This yields: $$ Z^2+Z = X+a+\frac{b}{X^2} $$ Thus, given $X$, we can compute $Z^2+Z$. From that value, we can compute the two solutions, which are $Z$ and $Z+1$ (see below). Since $Y = XZ$, this yields $Y$ and $Y+X$, thus the points $P$ and $-P$.

This gives us the compression method for curves in binary fields: from $(X,Y)$, compute $Z=Y/X$; the compressed point then consists in $(X,z_0)$, where $z_0$ is the least significant bit of $Z$. When decompressing, you use the equation above to recompute $Z^2+Z$, then $Z$ (the knowledge of $z_0$ tells you which of the two solutions is the right $Z$), then $Y = XZ$.

To know how to solve for $Z$, we need to define the trace and the half-trace. We are in $GF(2^m)$; the trace of a value $x$ is: $$ \mathrm{Tr}(x) = \sum_{i=0}^{m-1} x^{2^i} $$ We are in a field of characteristic $2$, which implies that squaring is an automorphism: $(uv)^2 = u^2v^2$ and $(u+v)^2 = u^2+v^2$ for all $u$ and $v$ (this is called the Frobenius automorphism). Moreover, for all $u$, $u^{2^m} = u$ (this is analogous to Fermat's little theorem, because the non-zero elements of $GF(2^m)$ are a multiplicative group of order $2^m-1$). This implies two important characteristics of the trace:

  • The trace is linear: for all $u$ and $v$, $\mathrm{Tr}(u+v) = \mathrm{Tr}(u) + \mathrm{Tr}(v)$.
  • The trace of any $u$ is either $0$ or $1$. Indeed, for all $u$, $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)^2$ (by the Frobenius automorphism), and also $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)$ (try it in the equation that defines the trace). Thus, for all $u$, $\mathrm{Tr}(u)^2 = \mathrm{Tr}(u)$. The equation $x^2=x$ is a polynomial equation of degree $2$, so it can have only (at most) $2$ solutions in a field, and $0$ and $1$ are solutions. Therefore, $\mathrm{Tr}(u)$ can only be $0$ or $1$.

Let's now define the half-trace. For now, I suppose that $m$ is odd (this is the normal case for binary elliptic curves, e.g. NIST curve B-233 is defined in $GF(2^{233})$). For any value $x$, the half-trace of $x$ is: $$ H(x) = \sum_{i=0}^{(m-1)/2} x^{2^{2i}} $$ That is, we take the equation for the trace, but we keep only half of the operands in the sum.

Like the trace, the half-trace is linear. Also, for any $x$, we can see that: $$ H(x)^2 + H(x) = \mathrm{Tr}(x) + x^{2^m} = \mathrm{Tr}(x) + x $$

Let's get back to our equation $Z^2+Z = \beta$ where $\beta = X+a+(b/X^2)$. Since the trace is linear, and since for $Z$ and $Z^2$ have the same trace, it follows that $\mathrm{Tr}(\beta) = \mathrm{Tr}(Z^2+Z) = \mathrm{Tr}(Z^2)+\mathrm{Tr}(Z) = 0$ (remember that addition is XOR in $GF(2^m)$). Thus, the equation can have solutions only if $\mathrm{Tr}(\beta) = 0$. Then, we have $H(\beta)^2+H(\beta) = \beta$, so the solutions for $Z$ are $H(\beta)$ and $H(\beta)+1$.

If $m$ is even (this will often be the case if using pairings over binary curves, although this is probably not a good idea since discrete logarithm in binary fields is a lot easier than previously expected), then most of the above hold, although we need another definition for the half-trace. Basically, we need a constant element $w$ such that $\mathrm{Tr}(w) = 1$, and we can define the half-trace as: $$ H(x) = \sum_{i=0}^{m-1}\left(\sum_{j=0}^{i} x^{2^j}\right)w^{2^i} $$

In both cases ($m$ odd and $m$ even), the half-trace is linear, so it can be computed as a XOR of some precomputed values for the bits equal to $1$ of the source. This is rather inexpensive. The trace is even easier: it is simply a XOR of some of the input bits, and, in practice, often a XOR of very few of these bits.

share|improve this answer
    
How is point compression done in binary field? – Myath Jan 23 at 4:02
    
@Myath: in binary curves it is a bit more complex to explain, but a rather efficient compression method still exists. I have updated my answer with some extra explanations. – Thomas Pornin Jan 23 at 19:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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