# Is using Euler's Totient/phi in Tonelli-Shanks (used to recover EC coordinate) safe?

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?

• 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$. – user94293 Nov 24 '16 at 18:35

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.
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.
• 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 :) – bekah Nov 24 '16 at 20:45