3
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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_
$\endgroup$
2
$\begingroup$

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://cs.ucsb.edu/~koc/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.

$\endgroup$
  • $\begingroup$ Shanks-Tonelli is the general answer for prime curves; however most elliptic curves have $p \equiv 3 mod 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) $\endgroup$ – poncho Jan 28 '15 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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