# In ECC scalar multiplication, how do add(Q, Q) exceptions occur?

Consider some scalar multiplication algorithm for a prime order (Weierstrass) curve $$E$$ with order $$\ell$$. Bernstein and Lange's SafeCurves: Completeness page mentions:

The problem is that the standard Weierstrass "addition formulas" don't always work: in particular, they fail for the doublings Q+Q.

Now let's say my scalar multiplication properly "clamps" any secret scalars $$k$$ such that it is ensured that $$0 < k < \ell$$. We also check that $$P$$ lies on the curve and $$P \ne \infty$$. Then we implement the scalar multiplication using a standard left-to-right DoubleAndAdd algorithm:

1: function DoubleAndAdd(k, P)
2:     R = ∞
3:     for i from n-1 down to 0 do
4:         R = double(R)
6:         R = select([R, T], k[i])
7:     end for
8:     return R
9: end function


Now my intuition thinks that add(Q, Q) will never occur in this algorithm.

Observation. First observe that in $$m$$ loop iterations we can only compute points $$R \in \{∞, P, \ldots, [2^m-1] P\}$$.

Argumentation. Now, assume that add(Q, Q) indeed occurs in this algorithm. In the algorithm, P is constant, so this will happen only when R == P before executing line 5. In the same iteration, R has just been doubled in line 4. During that same iteration before the doubling in line 4, R had the value [1/2]P $$=\left[\frac{\ell + 1}{2}\right] P$$. This means that we can always compute $$R = \left[\frac{\ell + 1}{2}\right] P$$ in $$(n-1)$$ loop iterations.

For example, if $$\ell$$ is the Mersenne prime $$2^n-1$$, then we have computed $$R = \left[\frac{2^n - 1 + 1}{2}\right] P = \left[2^{n-1}\right] P$$ in $$n-1$$ loop iterations. After filling in $$m = n-1$$ we realize that $$R = [2^m] \cdot P$$. But this contradicts our Observation. So add(Q, Q) can indeed not occur. □

Now I am not really sure if my gut is right, or if I should trust the SafeCurves page. Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

• Are you sure your "add" will work when one of your input is $\infty$ ? Are you sure you will never hit a $P+(-P)$ ? Jan 11, 2019 at 16:36

In ECC scalar multiplication, how do add(Q, Q) exceptions occur?

Probability that it occurs when performing multiplication for large random $$k$$ (allowed to exceed $$l$$) and $$P$$ a generator is $$\mathcal O\left(\dfrac{\log(k)}l\right)$$ for a random $$n$$-bit curve, thus negligible when using actual curve parameters. Thus it can occur only when fed incorrect parameters; the cryptosystem or hardware is under attack; or using toy-size parameters making the crytosystem insecure.

So add(Q, Q) can indeed not occur. □

I see no gap in the question's proof, now that it is explicitly stated that $$P$$ is on the curve, thus itself has prime order $$l$$.

Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

No for correct execution (including, no induced fault attack) and parameters: $$P$$ on the curve of prime order $$l$$, $$P\ne\infty$$, $$0\le k.

• You make a good point, during the $P \ne \infty$ check I also mean to check if $P$ is on the curve. Edit incoming.
– dusk
Jan 11, 2019 at 17:08