11
$\begingroup$

I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for doing fast, Point Addition and Doubling operations, and my implementation uses a "window" approach to do scalar multiplication.

But, I do not know, how to implement addition with the point at infinity in such a way, that it takes the same amount of time, as any other point.

void PointAdd(POINT * R, POINT *P, POINT *Q ) // has many more args 
   like curve etc. 
{
     if(zero(P->z)) {
         copy(R, Q);
         return;
     }
     if(zero(Q->z)){
         copy(R, P);
         return;
     }
     /*Do other calculations*/
}

Since the z coordinate is an important entity in the Elliptic curve point addition formulas for projective coordinates, it being zero, makes the equations result in a wrong answer, if we plug such a point for PointAdd function unless both $P=Q=O$. I believe, that this if ... else like checking will crush my implementation's purpose, of being side-channel resistant.

Is there a constant time solution to circumvent this, in a side-channel resistant way, or are there coordinate systems/addition-doubling formulas, that intrinsically, support the operations with the point at infinity $(0:k:0)$, where $k$ is an element of $F_{p}$?

$\endgroup$
  • $\begingroup$ All the answers so far are dealing with this at the level of math, but note that you can also deal with at the level of software, on architectures that have a "conditional move" operation. However, it has similar drawbacks to some discussed in corpsfini's comprehensive answer below (it is effectively a dummy operation.) $\endgroup$ – Glenn Willen Dec 5 '20 at 22:10
14
$\begingroup$

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:

  1. Manage the point addition in constant-time;
  2. 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.)
$\endgroup$
  • 1
    $\begingroup$ Nice, you went the formulas of Montgomery. Does Edwards Curve have an infinity point? $\endgroup$ – kelalaka Dec 5 '20 at 16:06
  • $\begingroup$ Thankyou, for your detailed answer! Where can I get a deeper, mathematical picture about differential addition... ? $\endgroup$ – Vivekanand V Dec 5 '20 at 21:41
  • $\begingroup$ @kelakela There are infinity points on Edwards curves but those are not part of the group: the neutral element is the affine point $(0, 1)$. $\endgroup$ – corpsfini Dec 6 '20 at 8:41
  • 1
    $\begingroup$ @VivekanandV The differential addition was introduced on Montgomery curves (by Montgomery) in this paper (pages 260-261). The reasonning can be extended to Weierstrass curves, see references in the Explicit-Formulas Database. $\endgroup$ – corpsfini Dec 6 '20 at 8:41
  • 1
    $\begingroup$ @corpsfini That is why as asked. You have called it infinity point instead of the neutral element. When talking about the identity of the EC group writing $\mathcal{O}$ as identity is fine, however, that can be a point at infinity or just an affine point as in the Edwards curve. $\endgroup$ – kelalaka Dec 6 '20 at 11:54
6
$\begingroup$

Long to be a comment and this is not going to a perfect answer;

First of all, an early exit is always a bad move. The simple idea is that turning the $\mathbf{If\; Else}$ 's

if S
  then A
else
  then B

into constant time expressions without changing the output by $$Q = (A * S) + (B * S') $$ where $S$ is the binary if condition.

#have a return point RET
RET = 0
S = zero(P->z)
ret = (P * S) + (RET * S')

S = zero(Q->z)
ret = (Q * S) + (RET * S')

The multiplication and addition are integer operations.

Now we got the result of the adding with the point at infinity. The next step is to combine it with the other case and we will see that this is not the case;

The Group Law on projective Coordinates

Let $P_i = (x_i : y_i : z_i ), i = 1, 2$, be points on the elliptic curve $$y^2 z = x^3 + Axz^2 + Bz^3.$$ where the above equation is the homogenous for of Weierstrass equation;

$$y^2 = x^3 +a x + b$$

Then $$(x_1 : y_1 : z_1 ) + (x_2 : y_2 : z_2 ) = (x_3 : y_3 : z_3 ).$$ The formulas are;

  1. $P_1 \neq \pm P_2$

    • $u = y_2 z_1 − y_1 z_2,$
    • $v = x_2 z_1 − x_1 z_2,$
    • $w = u^2 z_1 z_2 − v^3 − 2v^2 x_1 z_2,$ then

    $$x_3 = vw, \quad y_3 = u(v^2 x_1 z_2 − w) − v^3 y_1z_2, \quad z_3 = v^3 z_1 z_2$$

    As we can see, the group law doesn't need to distinguish if one point is $\mathcal{O}$ or not.

  2. $P_1 = P_2$

    • $t = A z_1^2 + 3x_1^2,$
    • $u = y_1 z_1,$
    • $v = u x_1 y_1,$
    • $w = t^2 − 8 v,$

$$x_3 = 2uw, \quad y_3 = t(4v − w) − 8y_1^2 u^2 , \quad z_3 = 8 u^3.$$

The only case we need to consider is doubling. This can be handled by a single if condition to combine the result. Is it clear that these two formulas are different, in double the $t$ has the $A$.

So all we need is

S = (P == Q) # hold the equality
ret = ( (P+Q) * S) + (([2]P) * S')
  • Note: if the curve has a useful birational equivalence to Montgomery Curve ( this means the curve must have a point of order 2 ) and achieve constant-time implementation more naturally with the Montgomery Ladder.
$\endgroup$
  • 1
    $\begingroup$ @VivekanandV I'm on it. The formulas from the handbook of ECC. $\endgroup$ – kelalaka Dec 6 '20 at 11:57
  • 1
    $\begingroup$ What you've described is indeed the approach that I took. $\endgroup$ – Nayuki Dec 7 '20 at 2:02
  • 1
    $\begingroup$ @Nayuki thanks for the info and the library. This idea is common in FHE schemes due to semantic security. $\endgroup$ – kelalaka Dec 7 '20 at 10:05
  • 1
    $\begingroup$ @VivekanandV This answer needs to be updated, I did not find a good way to do so, rather than applying the full If else all around, yet. I've tested with SageMath and yes, the point at infinity doesn't hold. The handbook of ECC doesn't differ from the case, which blundered me. Thanks again for checking the equations. I'm happy that Corpsfini gave an answer and got good points. Corpsfini is good on ECC, and I'm happy Corpsfini is around here. $\endgroup$ – kelalaka Dec 7 '20 at 10:11
  • 1
    $\begingroup$ @VivekanandV no problem on that. There are many great answers that were not accepted. Indeed, we wrote it for ourselves, too. $\endgroup$ – kelalaka Dec 7 '20 at 12:17

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.