# Finding scalar that creates a point with zero X-coordinate for popular elliptic curves

In signature creation in ECDSA we use a nonce, commonly identified as $$k$$. To create an ECDSA signature, we need to calculate two integers, commonly identified as $$r$$ and $$s$$. $$r$$ is simply the X-coordinate of the base point multiplied by $$k \bmod n$$.

$$s$$ is the actual signature, so it's $$s = k^{-1}\cdot(z+d\cdot r)\text{ mod }n$$, where $$z$$ is the number signed (usually the hash value as a big-endian integer), $$d$$ is the private key, and $$n$$ is the order of the base point.

Now, if a curve includes points with X-coordinate equal 0, then there may exist such a scalar that when multiplied by the base point it will result in a point that has such coordinate. That's true for some popular curves like NIST P-256, points

• $$\small{(0, \texttt{0x66485c780e2f83d72433bd5d84a06bb6541c2af31dae871728bf856a174f93f4})}$$ and
• $$\small{(0, \texttt{0x99b7a386f1d07c29dbcc42a27b5f9449abe3d50de25178e8d7407a95e8b06c0b})}$$

lay on the curve, and the curve has cofactor $$1$$, so we know that there is such $$k$$ that will generate them.

The ECDSA algorithm does require a retry with a different $$k$$ if either $$r$$ or $$s$$ ends up $$0$$, but I'd like to test if that code actually works correctly.

My questions:

1. Do we know of $$k$$ values for the popular curves (like the NIST P-256) that create points with $$x = 0$$?
2. Is there an algorithm to find them?
3. Same for the $$s$$ value: do we know of a triplet of $$k$$ value, message, and the private key that will result in $$s = 0$$ when using one of the popular curves?
4. If so, how would I go about finding it?

I did try a brute force approach (keep adding a base point to an accumulator, check fox x becoming zero), but that's too slow even for the likes of secp112r2.

1. No (See 2.). An alternative way to test a library could be to change the base point. You can find the point with x coordinate equal to zero, multiply it by a random $$r$$ and then use the result as the base point of ECDSA with $$k=r^{-1}$$.
4. $$s=k^{-1}(z+rd)$$ which is 0 when $$(z+rd)=0$$. If you can freely choose $$z$$ (e.g. the library receives it as parameter, and doesn't compute it internally) then you can choose $$z$$ such that $$z=-rd$$. Otherwise, you can select $$d$$ such that $$d=-\frac{z}{r}$$.
Note that another corner case that I test on implementations of ECDSA is where the $$x$$ coordinate of $$k*G$$ is greater than the $$G$$'s order. This again is done with the same trick I described in point 1.