Is it possible to hit point-at-infinity while performing scalar multiplication in Weierstrass curves?
According to this reply this is only possible when the scalar k is bigger then the order of the curve n. Is it so? If yes why?
3
-
1$\begingroup$ Perhaps I'm late to the party, but in my answer $n$ is not actually the group order. It is the order of the point $P$. In that case, if $1\leq k\leq n-1$, $[k]P$ will indeed never be the point at infinity. $\endgroup$– CurveEnthusiastJun 30, 2017 at 18:56
-
1$\begingroup$ And to clarify, $n$ is by definition the smallest positive number such that $[n]P=\mathcal{O}$, from which the above claim follows. $\endgroup$– CurveEnthusiastJun 30, 2017 at 18:59
-
$\begingroup$ I'm quite late to the party but if the question asks whether it is possible to hit the point at infinity as intermediate result of a scalar multiplication computation then the answers below are in general wrong as it really depends on the scalar multiplication algorithm you are using. Example: all methods from wikipedia initialize the temporary result to it. $\endgroup$– RuggeroJul 18, 2017 at 14:42
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
11
Yes, it is possible.
The smallest scalar $k$ for which $[k]P = \infty$ is called the order of $P$.
For every non-zero point $P$ on the curve there is such a $k$.
This is simply due to the fact that there is only a finite amount of points so if you keep increasing $k$ at some point you must get a repetition $[k]P = [k-i]P$ for some $i$. Now $[k]P - [k-i]P = \infty \iff [i]P = \infty$.
No, $k$ does not have to be bigger than the group order $n$.
In fact for any prime $p$ dividing $n$ there is a point $Q$ such that $[p]Q = \infty$. This is Cauchy's theorem.
On the other hand Lagrange's theorem tells us that the order of every point divides the group order: $[k]P = \infty \Rightarrow k|n$. Therefore, if the group order $n$ is picked to be prime it follows that the order of every non-zero element is $n$.
-
1
-
1$\begingroup$ There are infinitely many positive $k$ such that $kP = 0$; the order of $P$ is the smallest such $k$, and the others are its positive multiples. $\endgroup$– fkraiemJun 30, 2017 at 14:08
-
1
-
$\begingroup$ Yes, of course there are, unless the number of points is prime. I'm not sure where your confusion comes from. This is basically exactly what Cauchy says. $\endgroup$– EliasJun 30, 2017 at 15:27
-
2$\begingroup$ No, there are plenty of curves with non-prime order. See galvatron's answer for an example. (And as long as the characteristic of the base field is not 2 or 3 every curve can be written in Weierstrass form.) $\endgroup$– EliasJun 30, 2017 at 17:25
$\begingroup$
$\endgroup$
0
Not bigger, but bigger or equal (as the answer you refer to said). On curves with prime order you reach the point at infinity when the scalar $k$ is $k \geq n$, in fact when $k=n$ or it is a multiple of $n$, i.e. $k=\lambda n$. The order of an elliptic curve is defined as the number of distinct points on an elliptic curve $E$ including the point at infinity $\infty$. If the order of the elliptic curve is prime, then then $E$ is a cyclic group and any point on the curve can generate all distinct points on the elliptic curve, by performing point addition.
Point multiplication $kP$ is nothing but a lot of point additions (and doublings but let's assume only additions for the sake of transparency). Take the point $P$ for example on an elliptic curve $E$ of prime order $n$. By performing point multiplication which we said is just a lot of additions, i.e. $P+P+\dots$ you can get all points there are on the curve. After "a while", in fact exactly when you added $P$ to itself $n$ times (which is $nP$) you will get the point at infinity $\infty$. The next one would give you $nP + P = \infty + P=P$ which is $P$ again. This is called the identity law for elliptic curve groups.
$\begingroup$
$\endgroup$
The other answers have handled this correctly (yes, there is a $k$ such that $[k]P = \mathcal O$; no, $k$ can be less than the group order), so here's just an example to keep in mind for illustration, not for actual cryptographic use, taken from the non-free An Introduction to Mathematical Cryptography:
Let $E: y^2 = x^3 + 8x + 7$ over $\mathbb{F}_{73}$. There are $82$ points on this curve. So the only possible subgroup sizes are $2$ and $41$. Sure enough, if $P = (32,53)$, you have $[41]P = \mathcal O$, and $41 | 82$.