Non-Adjacent-Form-accelerated Scalar Multiplication

[mratsim]

Currently scalar multiplication is using the raw canonical bigEndian representation of the scalar (a.k.a. octet string).
Depending on 0 or 1 bit, after the mandatory doubling, we either do nothing or add the original point.
On average, for scalars that are non-differentiable from a random oracle (which is the case for all private keys) we do an addition half the time.

Each integer has a unique Non-Adjacent-Form, that uses a ternary vase {-1 0 1} https://en.wikipedia.org/wiki/Non-adjacent_form with the interesting property that non-zero-values cannot be adjacent.

This form can be used to double and add-or-substract with an upper-bound of 1/3 addition/substraction.

The most interesting part for a constant-time implementation is that it allows using bigger window sizes for the same storage requirement as the binary representation since we have redundancy:

• "-1 0 1 0" and "0 0 0 0" and "1 0 -1 0" ... can lookup in the same table slot

Current speed with window sizes effect:

[mratsim]

Alternatives representation include:

• Fibonacci representation
• Zeckendorf representation (see http://meloni.univ-tln.fr/articles/NewPointAddition.pdf)

[mratsim]

In-depth analysis in the context of side-channel resistance (advanced side-channel attacks and fault analysis)

• There is something about m-ary
  Benoit Feix and Vincent Verneuil, 2013
  http://vverneuil.net/doc/FV13_Mary.pdf

[mratsim]

Closed by #44, we use GLV-SAC (Sign-Aligned Column) representation