1
$\begingroup$

I'm implementing an algorithm in order to recover the $y$ co-ordinate from $x$ in order to construct a co-ordinate pair that satisfies secp256k1's elliptic curve equation, which is: $y^2 = x^3 + 7 \bmod q$.

$q$ is a prime and $q \equiv 3\bmod 4$ (I've checked) so we should be able to use:

$y = (x^3 + 7 \bmod q)^{\frac{q+1}{4}}.$

However, the size is limited to 256 bits and so $\frac{q+1}{4}$, which I'm calculating by $(q+1) \times 4^{-1}$, will be taken modulo $256$. I'm scared of this making the overall result wrong, so I was thinking of using Euler's totient and taking $\frac{q+1}{4} \bmod (q-1)$, as $\phi(q) = q-1$ due to $q$ being prime.

Is this safe? I can't find it recommended anywhere and I feel like it would be a good optimisation if it was actually safe to use, and so would be noted somewhere?

$\endgroup$
  • 1
    $\begingroup$ Since $q \equiv 3 \pmod 4$, it follows that $(q+1)/4$ is an integer. Further, as this integer is $< q-1$, $\frac{q+1}4 \bmod (q-1) = \frac{q+1}4$. $\endgroup$ – user94293 Nov 24 '16 at 18:35
2
$\begingroup$

As user94293 says, $q\equiv 3\bmod4 \implies q+1\equiv0\bmod 4$ hence $\frac{q+1}{4}$ is an integer. Clearly it is smaller than $q$ and larger than $0$, hence reducing it mod $q-1$ does not change anything. Hence in your circumstance everything is okay.

In a bit of a more broad context, determining whether something is "safe to use" depends on context. What can generally go wrong is that execution time of an algorithm is dependent on some secret data. An attacker will exploit this timing dependency to gain information about the secret, which is indeed a problem. So in this case you can ask yourself two more general questions:

  1. What information could an attacker learn if you were to compute $$\left(x^3+7\right)^{\frac{q+1}{4}\bmod{q-1}}\bmod{q}$$ as opposed to $$\left(x^3+7\right)^{\frac{q+1}{4}}\bmod{q}?$$ As long as you don't compute either one or the other depending on some secret, both are fine. Note that this includes that we could choose to compute a square root by doing $$\left(x^3+7\right)^{\frac{q+1}{4}+1000(q-1)}\bmod{q},$$ but we won't because it is not efficient.
  2. What data is actually being processed? I'm not aware of the details of the protocol you are working with, but in many cases $x$-coordinates of points are part of public data. In that case even if you do the exponentiation based on the value of $x$, an attacker can still not learn anything secret.

In short, it is important to remember that it is not important for an algorithm to be constant time, but to have run-time independent of secret data.

$\endgroup$
  • $\begingroup$ Brilliant, thank you! My $x$ is allowed to be public knowledge -- it's a sha256 hash of a message, and the message being hashed is public knowledge, I just needed a way to transform it into a valid EC point, and am working with a very restricted programming language and so cannot use eg the randomness required for a hashing to EC algorithm such as Foque and Tibouchi's. Thanks again :) $\endgroup$ – bekah Nov 24 '16 at 20:45

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.