6
$\begingroup$

I am working on a crypto project using the secp256k1 elliptic curve.

I know that I can select a random point $P = (x, y)$ from the curve by randomly selecting the first coordinate $x \in \mathbb{Z}_p$ (where $p$ is the prime of the elliptic curve field $\mathbb{F}_p$) and computing the second coordinate $y$ using the curve equation $y^2 = x^3 + 7$. Because the cofactor of the curve is $h = 1$, for every value $x \in \mathbb{Z}_p$ that spawns a valid $y \in \mathbb{Z}_p$, there is a point on the curve with coordinates $x, y$. In case there is a value $x \in \mathbb{Z}_p$ for which the curve equation does not find a valid value for $y \in \mathbb{Z}_p$, that means there is simply no point on the curve at that $x$ coordinate.

I also know that the curve order is $q$, with $q < p$. That means there exist $q$ valid points on the curve, which is less than all the values that $x$ could have in $\mathbb{Z}_p$.

My question is: How far are points from each other, in respect to the $x$ coordinate? What is the largest distance between two points on the curve? Is there any documentation in this regard?

Improve this question
$\endgroup$
3
  • $\begingroup$ In which coordinate system? You do understand that the discrete modular curves do not look like curves in the X,Y coordinate system, right? And that although $q < p$, the value of $q$ is only a tiny bit smaller than $p$ for the curves we use for cryptographic operations... $\endgroup$
    – Maarten Bodewes ♦
    Aug 14, 2019 at 11:42
  • $\begingroup$ What exactly do you mean by "distance"? $\endgroup$
    – Conrado
    Aug 14, 2019 at 14:13
  • $\begingroup$ By distance between two points (in respect to the $x$ coordinate) I mean the following: Having two valid points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$, with all $x \in (x_1, x_2)$ generating invalid points, the distance between $P_1$ and $P_2$ is $|x_1 - x_2|$. $\endgroup$
    – Hulub
    Aug 19, 2019 at 13:41

1 Answer 1

Reset to default
3
$\begingroup$

I also know that the curve order is $q$, with $q<p$. That means there exist $q$ valid points on the curve,

True

which is less than all the values that $x$ could have in $\mathbb{Z}_p$

Actually, that's less relevant than you think.

  • For every $x$ value in $\mathbb{Z}_p$ that has a valid solution, there are two values of $y$ that satisfy the equation (and hence correspond to two points). It's easy to see, if $(x, y)$ is a solution, then so is $(x, -y)$ (aka $(x, p-y)$)

Note: some elliptic curve have 1 or 3 $x$ values that correspond to a single $y$ value (which is the $y$ value 0) - secp256k1 is not one of those curves.

In addition, there is a single 'point of infinity' which doesn't correspond to a solution to the equation, but is thrown in as an additional group element.

Hence, there are exactly $(q-1)/2$ $x$ values that correspond to (at least one) valid point. Since $p \approx. q$, this if you pick an $x$ value at random, you have almost exactly a 50% probability of picking one with a solution.

Improve this answer
$\endgroup$
5
  • $\begingroup$ After some more research, I found out the following: $\endgroup$
    – Hulub
    Aug 19, 2019 at 13:44
  • $\begingroup$ The largest "distance" between two point is not that relevant, because there could potentially be points at any distance on the curve. A more interesting question is how easy can you find two points that are $n$ far away from each other. Formally, given a valid point $P = (x, y)$, the probability of the next $n$ consecutive values for the $x$ coordinate to generate invalid points is $2^{-n}$. $\endgroup$
    – Hulub
    Aug 19, 2019 at 13:52
  • $\begingroup$ @Hulub: do we know that? Is there a proof that the valid $x$ coordinates are not non-uniformly distributed? There might be; I haven't seen such a proof... $\endgroup$
    – poncho
    Aug 19, 2019 at 14:53
  • $\begingroup$ By your argument, that every $x$ value has a probability of $1/2$ to generate a valid point, that also means it has a probability of $1/2$ to generate an INVALID point. If we take 3 consecutive $x$ values, the probability of all 3 to NOT generate valid points is $1/2 * 1/2 * 1/2 = 2^{-3}$. Hence, the generalisation holds. $\endgroup$
    – Hulub
    Aug 22, 2019 at 7:49
  • $\begingroup$ @Hulub: that does not follow. Yes, if we take 3 random $x$ values, the probability is approximately $2^{-3}$ (approximately because the probability of a single value isn't precisely $2^{-1}$). On the other hand, we don't know if the valid $x$ values are clustered; any correlation because whether successive values are valid would invalidate your argument (and as I said previously, I don't know of any proof about correlation of successive $x$ values) $\endgroup$
    – poncho
    Aug 22, 2019 at 16:43

Your Answer

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

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