2
$\begingroup$

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?

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

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.