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)
5: T = add(R, P)
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?