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

Question

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.

Answer 1

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}$.
2. This is equivalent to solving an ECDLP (discrete logarithm problem) which on standard curves, is believed to be hard (practically unfeasible)
3. This is possible.
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.