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:


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

  • $\begingroup$ 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. $\endgroup$ Commented Jun 28, 2013 at 10:40
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jun 28, 2013 at 15:22
  • $\begingroup$ @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. $\endgroup$ Commented Jun 28, 2013 at 21:42
  • $\begingroup$ 02583857549063195252150226340830731484791130788759 is wrong, if only because it mixes hexadecimal (the 02) and decimal (the X coordinate). And we have to guess that's for secp160r1, which matters to the number of bytes. The correct values for the compressed key then is 02664513f68596befd31c8d541d3e5c8ec32ab9397. $\endgroup$
    – fgrieu
    Commented Mar 1 at 16:55

2 Answers 2


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.

  • $\begingroup$ How is point compression done in binary field? $\endgroup$
    – Myath
    Commented Jan 23, 2016 at 4:02
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Jan 23, 2016 at 19:20

The compressed point format includes the least significant bit of ๐‘Œ in the first byte (the first byte is 0x02 or 0x03, depending on that bit): this bit is enough to know whether you got ๐‘Œ or โˆ’๐‘Œ with the square root, and adjust in consequence.

Since I just spent a day figuring what "adjust in consequence" means, I thought Id post my findings in case its useful to others. This is meant to answer the question "how to convert a compressed elliptic curve point (just X coordinate and "sign of Y") to uncompressed form (X and Y coordinate)". Its not specific to ECDSA public keys, but ill use that as the exemplar. It is specific to a group using prime modular arithmetic. Not sure about binary curves.

As above, you know ๐‘‹ and you use the curve equation F(x) to compute Y^2, then take the square root of that to get one of the roots, Y or -Y. Since everything is in modular arithmentic, you cant check to see if the value is negetive (all values are positive), but you can note that if Y is less than P/2, then -Y is greater than P/2, since -Y = P - Y. Y less than P/2 means that Y is even, and Y > P/2 means that Y is odd (ie the low bit is set).

The 02/03 leading byte tells you whether the orginal root is even or odd (I think 02 means even). Now, after you have computed your own Y = sqrt(F(x)), you check to see if it is even or odd, ie which root do you have? If it matches the 02/03 leading byte, then thats your answer, if not, then you take its negative, eg Y.negate().mod(P).

That for me was the missing piece I couldnt find anywhere. Hope its useful to someone else.


Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge you have read our privacy policy.

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