4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$
  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.

$\endgroup$

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.