Left-to-Right Double-and-Add-Always Algorithm
The double-and-add-always algorithm was initially proposed by Coron in [31] as a first attempt to avoid if-statements and therefore prevent the identification of different operations. The algorithm performs a point doubling followed by a point addition in a for loop, scanning the scalar bits from the most significant to the least significant one. Both operations are performed in every loop and according to the key bit, the final assignment to R_{0} will be either R_{0} or R_{1}. There are no conditional
Algorithm 1: The left-to-right double-and-add-always algorithm |
Input: P, k = (k_{x}-1, kx-2, ? ??, ВД2 Output: Q = k ? P R0 — P; for i — x — 2 down to 0 do R0 — 2R0; R-i —— R0 + P ; R0 — R-k, ; end return R0 |
statements in the algorithm, but there is one key-dependent assignment, which can leak secret information. Another important remark is that R_{0} is initialized by P instead of O, in order to avoid exceptional cases given by the point at infinity.