2
$\begingroup$

I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ on the curve has two $Y$'s, one even and one odd. Therefore, we only need to store whether the corresponding $Y$ point we are storing is even or odd. So to store the point $(X,Y)$ now, we shift $X$ ridding of its most significant bit and add $1$ if the $Y$ point is odd. Therefore, one can think of the compressed point being $2 \cdot X+B$ ($B$ is the bit we added to tell if $Y$ was odd or even) since the multiplication by $2$ is implied because of the shift. I understand this completely. It's recovering the original point that has me confused.

Since a point on the curve is given by the equation $y^2=x^3+ax+b$, we can find square roots officially in $\mathrm{GF}(p)$. The following from my spec is what confuses me.

If $p$ is prime and congruent to $3$ mod $4$, one of its square roots is $z^{(p+1)/4} \bmod p$ and the other is $p-z^{(p+1)/4} \bmod p$. How would I solve this? What is $z$?

For example, I know how to extract the $x$ point so let's say I simplify the right side of the equation to be $7$ and $p$ is $11$. Would I be trying to solve for the square root that's equal to $7$ mod $11$?

$\endgroup$
  • $\begingroup$ This question is related to this recent one. It is maybe a homework? $\endgroup$ – cygnusv Dec 4 '14 at 14:49
  • $\begingroup$ yup, that one is not answered so I figured I'd write a nicer looking question and hope for an answer. $\endgroup$ – Joe Dec 4 '14 at 14:51
  • $\begingroup$ Corrected: If $p$ is prime and congruent to $3$ mod $4$, and $z$ is a quadratic residue mod $p$, then one of $z$'s square roots mod $p$ is $z^{(p+1)/4}$ and the other is $p-z^{(p+1)/4}$. $\endgroup$ – fkraiem Dec 4 '14 at 16:02
  • $\begingroup$ so I've made some progress in understanding this since I'm going to get a whole number exponent. What is z? Is z what i calculate the right side of the equation to be? Determing z is confusing me. Could you give me an example where like P is 11 and A is 1 and B is 6. Once I see how to solve it than I know i can program it. I have algorithms implemented like the repeated square $\endgroup$ – Joe Dec 4 '14 at 16:06
  • $\begingroup$ $z$ is whatever you want to compute the square root of. Of course, you must first be sure that it is a quadratic residue. $\endgroup$ – fkraiem Dec 4 '14 at 16:10
4
$\begingroup$

You want to find a point $(X,Y)$ on an elliptic curve $y^2 = x^3 + ax + b$ knowing only $X$ and a single bit indicating whether $Y$ is even or odd. To find $Y$, you use the relation defining the curve: you know that $Y^2 = X^3 + aX + b$ since the point is on the curve. So you compute $X^3 + aX + b$ using your value of $X$ and the public parameters $a, b$, and you want to find values of $Y$ such that $Y^2$ is equal to that value.

If the modulus $p$ is congruent to $3$ mod $4$, that's very easy to do: for any $z$, the square roots of $z$, if they exist, are $\pm z^{(p+1)/4} \bmod{p}$. Indeed, suppose $z$ has a square root, say $a$. Let $g$ be a primitive root mod $p$, and let $a = g^x$. Then $z = (g^x)^2 = g^{2x}$. In turn,

$$(z^{(p+1)/4})^2 = z^{(p+1)/2} = (g^{2x})^{(p+1)/2} = (g^x)^{p+1} = (g^x)^{p-1}g^{2x} = g^{2x} = z$$

which shows that $z^{(p+1)/4}$ is indeed a square root of $z$.

$\endgroup$
2
$\begingroup$

If p is prime and congruent to 3 mod 4, one of its square roots is z(p+1)/4modp and the other is p−z(p+1)/4modp. How would I solve this? What is z?

If the elliptic curve equation is given by $y^2 = x^3 + ax + b$, to find the value of $y$ you would need to find the square root of the right hand side of the equation, meaning that $z = x^3 + ax + b$ in this case.

You would solve this by substituting in all of the parameters that you know -- $p$ is an elliptic curve parameter (the order of the Galois field $GF(p)$), and you have $a$ and $b$ as defined in your question.

Would I be trying to solve for the square root that's equal to 7 mod 11?

It's a little more accurate to say that you would be trying to solve for $y$ (or the two values of $y$) such that $y^2 \equiv 7 \bmod 11$.

$\endgroup$

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.