# Point decompression on an elliptic curve

I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding:

Given a point $x$ and $y$, we can compress its representation since for every $x$ on the curve, there are two $y$s; one even and one odd. Therefore, we can express the point as $x$ concatenated with a bit $y'$, thus representing the point in half the bits. To do this, we calculate $y' := y \bmod 2$ to detect if $y$ it is even or odd and add this remainder to the $x$ value which has been left-shifted by one bit (one can think of this representation as $2x + y'$). I understand completely why we do this, in fact it's pretty ingenious. My problem is with decompressing the point which apparently involves square roots in a finite field.

Since the equation of the elliptic curve is $y^2=x^3+ax+b$, where $a$ and $b$ are parameters of the curve, we apparently need to compute square roots to uncover $y$. I know how to recover $x$ from the compressed representation; just subtract $1$ if it is odd and divide by $2$ and that's the $x$ coordinate. My specification noted the formula: If $p$ is prime and congruent to $3$ modulo $4$, then finding square roots of an element $z\in\mathbb F_p$ is easy. $z^{(p+1)/4}$ is one root and the other is its negative. This confuses me: Why is this a square root and how do I implement this computation?

Let $x\in\mathbb Z/p\mathbb Z$ be the point's first coordinate, and define $z := x^3+ax+b$. We know that there exists a square root $y\in\mathbb Z/p\mathbb Z$ of $z$, i.e. $y^2=z$. Let's assume we have already found such an $y$. Since the order of $(\mathbb Z/p\mathbb Z)^\ast$ is $p-1$, Lagrange's theorem implies $y^p=y\text,$ hence $$\left(z^{(p+1)/4}\right)^2=\left((y^2)^{(p+1)/4}\right)^2=\left(y^{(p+1)/2}\right)^2=y^{p+1}=y^2=z\text,$$ which shows that $z^{(p+1)/4}$ is a square root of $z$. The possible second coordinates for the uncompressed point are thus $z^{(p+1)/4}$ and $-z^{(p+1)/4}$, and you can select the right one using the "sign" bit from the compressed representation.

• What is the significance of the 'sign' bit? Could you explain to me why the first bit of the y denotes whether the point is negative or not, and could you explain why there is one odd y and one even y for every x (why can't they both be even and vice versa)? Thanks Jul 9, 2022 at 11:41
• This answer assumes $p\bmod 4=3$. The "sign bit" is conventionally $(y\bmod p)\bmod2$, encoded as byte 02or 03. See sec1v2 section 2.3.4, subcase 2, and within this 2.4.1
– fgrieu
Apr 12 at 16:00

I had trouble with this as well when I was learning about ECC. I have no idea if this is the technically correct way to do it, but it works in my program... Well, I know for a fact it works with secp256k1, secp384r1, and secp511r1 at least.

i = (first byte of compressed point) mod 2
y2 = ((x ^ 3 mod p) + a*x + b) mod p
y_ = (y2 ^ ((p+1)/4)) mod p

if i is odd: y = p-y_
else y = y_

• The test is incorrect; it could be corrected to if i+p is odd. Also, it's useful to check that y^2 mod p equals y2, which catches a possibly invalid x.
– fgrieu
Apr 12 at 18:45

Have a look at Shanks-Tonelli algorithms about modular square root.

On binary curves $$y^2 + x y - (x^3 + bx^2 + b) = 0$$, you can rewrite it as $$y^2 + Ay + B = 0$$, you need to solve a quadratic equation in $$F(2^m)$$.

Computation complexity is about the same (prime curves and binary curves), with a slight advantage to binary implementations where squaring and modular square root are really really fast.

• Shanks-Tonelli is the general answer for prime curves; however most elliptic curves have $p \equiv 3 \pmod 4$, and in this case, the problem can be simplified: to compute the square root of $n$, you just compute $n^{(p+1)/4}$ (and check that that value squared gives you $n$; this last bit catches values of $n$ that don't have a square root) Jan 28, 2015 at 16:56