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:
- Do we know of $k$ values for the popular curves (like the NIST P-256) that create points with $x = 0$?
- Is there an algorithm to find them?
- 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?
- 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.