2
$\begingroup$

I am reading Programming Bitcoin. The author said:

Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.

He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.

$\endgroup$
  • 1
    $\begingroup$ If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures. $\endgroup$ – Squeamish Ossifrage Apr 8 '19 at 1:54
3
$\begingroup$

The points on the Elliptic Curves ($E$) over e field $K$ are forming a commutative additive group with the identity $\mathcal{O}$; the point at infinity, also notated as $P_\infty$.

The scalar multiplication $[k]P$ this actually means adding $P$, $k$-time itself. More formally;

let $k \in \mathbb{N}\backslash\{ 0\}$

\begin{align} [k]:& E \to E\\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}

and $[0]P = \mathcal{O}$, and $[k]P=[-k](-P)$ for $k<0$.

Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $\mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.

Point addition in $\mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $\mathcal{O}$.

$$\underbrace{P+P+\cdots+P}_{\text{$t$ times}} = [t]P= \mathcal{O}$$

The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.

Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.

Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field ($K$) are same then the discrete logarithm on this curves runs in linear time.

$\endgroup$
  • 1
    $\begingroup$ The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed. $\endgroup$ – Squeamish Ossifrage Apr 7 '19 at 14:58
  • $\begingroup$ @SqueamishOssifrage thanks and for the links. $\endgroup$ – kelalaka Apr 7 '19 at 17:00
  • $\begingroup$ I'm thinking that the points on the elliptic curve are a group and not a ring because of the lack of an absorbing element (0) for multiplication? $\endgroup$ – Andreas Yankopolus May 9 '19 at 23:35
  • 2
    $\begingroup$ @AndreasYankopolus: there is no multiplication operation defined on two points -- only scalar x point, which is actually repeated addition -- much less a multiplicative identity. PS: although not true in general, the X9/Certicom prime curves, including secp256k1 used in Bitcoin, were chosen with group order prime so all elements generate the full group (cofactor=1) $\endgroup$ – dave_thompson_085 May 11 '19 at 3:24
  • $\begingroup$ Why $[k]P=[-k][-P]$ for $k<0$? should not it be $[k]P=[-k][P]$? why $[-P]$ on the left hand side? $\endgroup$ – Andrew Jan 22 at 18:41
1
$\begingroup$

In a secp256k1 context (including bitcoin), multiplying a point $P$ on the curve by an integer $k$ leads to the point at infinity $\mathcal O$ if and only if:

  • $k$ is a multiple of the group order $n$, including when $k=0$. This $n$ is a large (prime) integer part of the secp256k1 characteristics. That's the number of points on the curve, including the point at infinity.
  • or point $P$ is the point at infinity $\mathcal O$. That can't occur when $P$ is the generator $G$.

Mathematically: $k\times P=\mathcal O\iff k\bmod n=0$ or $P=\mathcal O$.

A good analogy is multiplication modulo prime $n$: multiplication by $k$ yields zero (modulo $n$) when $k$ is a multiple of $n$, or when what we multiply was already zero (modulo $n$). The analogy goes further: adding something that's zero (modulo $n$) changes nothing (modulo $n$), and that's the definition of zero (modulo $n$); much like adding the point at infinity $\mathcal O$ to any point on the curve leaves it unchanged, and that's the definition of the point at infinity.

Even simpler analogy: when in clock arithmetic we repeatedly add the current time (expressed as a whole number of hours), or equivalently multiply the current time by increasingly large integers, we eventually get to 12 o'clock (even if we did not start from 12 o'clock, that can occur before we multiplied by 12; that's because 12 is not prime).

Notice that when multiplying by $k$ not a multiple of $n$, some point multiplication algorithms might still internally encounter the point at infinity. For example when $k=8n-1$, some algorithms to compute $k\times P$ could compute it as $2\times\bigl(2\times\bigl(2\times\bigl(((k+1)/8)\times P\bigr)\bigr)\bigr)\,-\,P$. This is mathematically correct, but encounters the point at infinity in the computation of $((k+1)/8)\times P$.

When $P$ is not on the curve, multiplying it by an integer is not mathematically defined, and what happens can only we stated by examining how the multiplication is attempted.

Some point multiplication algorithms avoid both issues by special-casing multiplying the point at infinity; validating that the point is on the curve; reducing $k$ modulo $n$, then special-casing $k=0$; and making sure that they internally manipulate $j\times P$ only with $|j|<n$ (perhaps with an exception for even $j$ with $|j|<2n$ ).

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