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 R0 will be either R0 or R1. There are no conditional

Algorithm 1: The left-to-right double-and-add-always algorithm

Input: P, k = (kx-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 R0 is initialized by P instead of O, in order to avoid exceptional cases given by the point at infinity.

 
Source
< Prev   CONTENTS   Source   Next >