-2
$\begingroup$

knowing the coordinates of $R$ on secp256k1 and an integer $s$, how do we validate that $s$ is the slope at the point $Q$ on secp256k1 such that $R=2Q$ ?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Knowing the coordinates of $R$ on secp256k1 and an integer $s$, how do we validate that $s$ is the slope at the point $Q$ on secp256k1 such that $R=2Q$ ?

One way would be computing $Q=((n+1)/2)R$ by point multiplication as in this answer, then computing the slope at $Q$ and comparing to $s$.

But there's a better way. From point doubling equations we know that

$$\begin{align}s&=(3Q_x^{\,2})/(2Q_y)&\bmod p\label{fgr1}\tag{1}\\ R_x&=s^2-2Q_x&\bmod p\label{fgr2}\tag{2}\\ R_y&=s\,(Q_x-R_x)-Q_y&\bmod p\label{fgr3}\tag{3}\end{align}$$

I suggest this procedure, which starts from $s$, $R_x$, $R_y$ only.

  1. check that $0<s$ and $s<p$
  2. check that $R$ is on secp256k1, that is $(R_x^{\,3}+7-R_y^{\,2})\bmod p=0$
  3. compute $Q_x=(((n+1)/2)(s^2-R_x))\bmod p$ (which follows from $\ref{fgr2}$)
  4. compute $Q_y=(s\,(Q_x-R_x)-R_y)\bmod p$ (which follows from $\ref{fgr3}$)
  5. check that $Q$ is on secp256k1, that is $(Q_x^{\,3}+7-Q_y^{\,2})\bmod p=0$
  6. check that $(3Q_x^{\,2}-2s\,Q_y)\bmod p=0$ (which follows from $\ref{fgr1}$)

I'm not sure step 6 is necessary; it may be redundant with 5.

If we omit step 1, then adding $p$ to a valid slope can yield an $s$ that the other steps will accept, even though that $s$ could not be obtained as s = (3 * Qx**2) * pow(Qy*2, -1, p) % p as in the definition of slope given in the original version of a related question.

I made an example implementation in Python. Try it Online!

$\endgroup$
2
  • $\begingroup$ The procedure you provided is one way it can be done but am looking for a approach that involves only $s$,$R_x$ and $R_y$. Can you give more insight on step one $0<s<p$ $\endgroup$ Oct 9, 2023 at 12:35
  • $\begingroup$ I added explanation on step 1. My procedure involves only $s$, $R_x$ and $R_y$ (notice that $Q_x$ and $Q_y$ are recalculated from that, and form $p$). $\endgroup$
    – fgrieu
    Oct 9, 2023 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.