Point decompression on an elliptic curve

Question

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?

Answer 1

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.

Answer 2

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_

Answer 3

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)$.

( http://sites.cs.ucsb.edu/~koclab/teaching/ccs130h/projects/03-ecc-protocols/Julio_Slides.pdf )

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.