Introduction
Dealing with the neutral element $\mathcal{O}$ of an elliptic curve in Weierstrass form is a major problem in implementations. This is due to the fact that this point has no affine representation on this form of elliptic curve and is called the infinity point.
This point can still be written using projective coordinates. Noting $x=X/Z$ and $y=Y/Z$, the equation of the elliptic curve defined by $y^2 = x^3 + ax + b$ becomes:
$$
Y^2Z = X^3 + aXZ^2 + bZ^3.
$$
An affine point $(x,y)$ has the representation $(X:Y:Z)$ where $Z \neq 0$ (and can have as many representation as there are possible values for $Z$). When $Z=0$, then $X=0$, so the point $(0:k:0)$ with $k \neq 0$ is the only point at infinity and is the neutral element $\mathcal{O}$.
Then it might be tempting to use this representation of $\mathcal{O}$ in the formulas. Unfortunately for most of them it doesn't work.
To make an implementation constant-time relatively to the infinity point, I see two general methods:
- Manage the point addition in constant-time;
- Use an algorithm that avoids the infinity point.
Solution 1: dummy point addition
The basic idea is to compute a point addition and ignore its result when the infinity point is one of the inputs.
This is what the double-and-add-always algorithm does, but can be extended to other regular algorithms.
This can be implemented using booleans based on the coordinates $Z$ of the points, then applying the point addition normally. Then the computation is ignored if one of the boolean indicates that one of the points is $\mathcal{O} by replacing the computed values by the other input point.
For example, this is exactly how it is done for several curves in OpenSSL with a conditional copy that erases the calculated values:
copy_conditional(x_out, x2, z1_is_zero);
copy_conditional(x_out, x1, z2_is_zero);
copy_conditional(y_out, y2, z1_is_zero);
copy_conditional(y_out, y1, z2_is_zero);
copy_conditional(z_out, z2, z1_is_zero);
copy_conditional(z_out, z1, z2_is_zero);
Source
Advantage:
- can be used for any algorithm (double-and-add-always, fixed window based algorithms).
Drawbacks:
- Useless computation;
- Vulnerable to C safe-error attacks (an attacker inject a fault during the point addition and if no effect are observed on the output of the scalar multiplication, then the attacker knows the infinity point is involved and may decude information on the scalar).
Solution 2: Complete point addition
On the Edwards form of elliptic curves, the neutral element is an affine point, so it is possible have point addition formulas that are complete as was shown in this paper.
The authors of this paper proposed formulas for prime order elliptic curves that are complete using projective coordinates.
Advantage:
- Unified and complete point addition (works for any inputs including the infinity point).
Drawbacks:
- A little more costly than other formulas;
- Still vulnerable to C safe-error attacks: if $P = (X_1:Y_1:Z_1)$ is the infinity point, then line 10 of algorithm 1 in the paper becomes a dummy operation, so a fault on this operation with no effects means that the entry $P$ is $\mathcal{O}$ (I didn't check the other algorithms on the paper).
Solution 3: Montgomery ladder with XZ formulas
Montgomery ladder is an algorithm where the point addition always occurs between a point $P_1$ and $P_2$ that satisfy the invariant $P_1 - P_2 = P$ where $P$ is the input of the scalar multiplication.
The formulas presented below are taken from the page XZ coordinates for short Weierstrass curves (given by the equation $y^2 = x^3 + ax + b$) in the Explicit-Formulas Database.
There are two types of mixed differential addition. Those do not make use of the protective coordinate $Y$ of the points.
I present the one from mdadd-2002-it-4 and make the assumption that the input $P$ of the scalar multiplication is a point of odd prime order $q$.
An affine point $(x,y)$ is represented as projective coordinates $(X:Z)$ that satisfy $x = X/Z$, and the infinity point $\mathcal{O}$ by $(1:0)$.
Differential addition
The inputs are $P_1$ and $P_2$ given by their XZ representation $(X_1:Z_1)$ and $(X_2:Z_2)$, and $x$ is the affine $x$-coordinate of $P_1 - P_2$. The computation of the addition is given by
$$
\left\{\begin{array}{rcl}
X_3 & = & 2(X_1Z_2 + X_2Z_1)(X_1X_2 + aZ_1Z_2) + 4bZ_1^2Z_2^2 - x(X_1Z_2 - X_2Z_1)^2 \\
Z_3 & = & (X_1Z_2 - X_2Z_1)^2
\end{array}\right.
$$
Now we need to look at the possible exceptions with these formulas:
Case 1: $P_1 = P_2$.
This case means that $P = P_1 - P_2 = \mathcal{O}$, but we assume that $P$ is not the infinity point so it is impossible.
Case 2: $P_1 = -P_2$ and $P_1\neq P_2$.
Then $P_1 + P_2 = \mathcal{O}$. We have $Z_3=0$ and
$$
\frac{X_3}{Z_1^2Z_2^2} = 4\left(\left(\frac{X_1}{Z_1}\right)^3 + a\frac{X_1}{Z_1} + b\right) \neq 0
$$
because $P_1$ is not a point of order $2$. So $P_1+P_2$ is correctly computed as a valid representation of the infinity point.
Case 3: $P_1 \neq \mathcal{O}$ and $P_2 = \mathcal{O}$.
We have $Z_1 \neq 0$, $X_2\neq 0$ and $Z_2=0$.
Then $X_3 = 2X_1Z_1X_2^2 - xX_2^2Z_1^2$, $Z_3 = X_2^2Z_1^2 \neq 0$ and
$$
\frac{X_3}{Z_3} = \frac{2X_1Z_1X_2^2}{X_2^2Z_1^2} - x\frac{X_2^2Z_1^2}{X_2^2Z_1^2} = 2x-x = x,
$$
so $(X_3:Z_3)$ is a correct representation of $P_1+P_2 = P_1 + \mathcal{O} = P_1$.
Other cases:
$Z_3\neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $P_1 + P_2$.
Doubling
The input is $P_1$ given by its XZ representation $(X_1:Z_1)$.
Then $2P_1$ is given by the formulas
$$
\left\{\begin{array}{rcl}
X_3 & = & (X_1^2 - aZ_1^2)^2 - 8bX_1Z_1^3 \\
Z_3 & = & 4Z_1(X_1^3 + aX_1Z_1^2 + bZ_1^3)
\end{array}\right.
$$
Case 1:
$P_1 = \mathcal{O}$. We have $X_1\neq 0$ and $Z_1 = 0$.
Then $X_3 = X_1^4 \neq 0$ and $Z_3 = 0$, which gives a correct representation of the infinity point.
Other cases:
We have $Z_3 \neq 0$ and $X_3/Z_3$ corresponds to the correct $x$-coordinate of $2P_1$.
Recovery of coordinate $y$
At the end of the scalar multiplication, we can reconstruct the complete affine coordinates of the output thanks to the following formulas.
Given $P=(x,y)$, and $(X_1:Z_1)$ and $(X_2:Z_2)$ the XZ representations of $P_1$ and $P_2$ such that $P_2 - P_1 = P$, then the following formulas gives a complete representation of $P_1 = (X'_1 : Y'_1 : Z'_1)$:
$$
\left\{\begin{array}{rcl}
X'_1 & = & 2yX_1Z_1Z_2 \\
Y'_1 & = & 2bZ_1^2Z_2 + Z_2(AZ_1 + xX_1)(xZ_1 + X_1) - X_2(xZ_1 - X_1)^2 \\
Z'_1 & = & 2yZ_1^2Z_2
\end{array}\right.
$$
Case 1: $P_1 = \mathcal{O}$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which gives an incorrect representation of the infinity point. However, in the case of Montgomery ladder it means the scalar is a multiple of the order of the input so it has no cryptographic impact.
Case 2: $P_2 = \mathcal{O}$.
This case means that $P_1 = -P$.
We have $X'_1 = Y'_1 = Z'_1 = 0$ which does not correspond to $P_1$.
Case 3: $y=0$.
It means $P$ has order $2$, so it cannot happen.
Other cases:
We have $Z'_1 \neq 0$ and $(X'_1 : Y'_1 : Z'_1)$ is a correct representation of $P_1$.
Wrap-up
The only cases to manage are:
- The input $P$ of the scalar multiplication is the infinity point;
- The input scalar is a multiple of the order: the coordinate $Z$ at the end is $0$ then the output is $\mathcal{O}$;
- The input scalar is a multiple of $q-1$: only a problem for the recovery of the missing coordinate.
Solution 4: Algorithms that avoid the infinity point
One possibility is to recode the scalar $k$ such that the point additions always occur between two points that can never be the infinity point.
A classic fixed window-based algorithm separate the scalar $k$ in windows of width $w$:
$$
k = \underbrace{k_0 + k_1 2 + \cdots + k_{w-1}2^{w-1}}_{K_0} + \underbrace{k_w 2^w + \cdots + k_{2w-1}2^{2w-1}}_{2^w K_1} + k_{2w}2^{2w} + \cdots
$$
so the scalar can be rewritten as
$$
k = K_0 + K_1 2^w + \ldots + K_{d-1}2^{dw-1}.
$$
where $d$ is the number of windows to cover the whole scalar.
Every $w$ doublings, a point addition with the precomputed point $[K_i]P$ is done. When the window $K_i$ is null, it means it is the infinity point.
To avoid that, several papers proposed to recode the scalar such that the windows are always nonzero. To cite a few:
Personnally, I like the way it is implemented in Mbed TLS. It is a variant of the technique proposed in the first paper above where the windows are in fact combs (the bits of the scalar in a comb are not taken consecutively but separated by a fixed distance).
Advantage:
- No need to manage the infinity point in the point addition.
Drawbacks:
- The scalar must be recoded, so it is a little bit more complicated;
- While the infinity point is managed, does the case $P_1 = P_2$ can appear during the scalar multiplication? (The answer is maybe and depends on the method and other parameters.)
