Right-to-Left Double-and-Add-Always Algorithm
The binary right-to-left double-and-add-always algorithm of [32] is shown below as Algorithm 2. The steps of the algorithm are similar to Algorithm 1 with the following differences:
- • The bits of the scalar are scanned from the least significant to the most significant one.
- • Two temporary registers are used instead of three and they are both effectively used, without any dummy operations.
Similar to Algorithm 3.3.1, there are no conditional statements in this algorithm, but there is a key-dependent assignment, which can be vulnerable to attacks. However, there are several attacks that can be mounted on the left-to-right, but not on the right- to-left algorithm (for instance the Doubling attack, described in Sect. 3.4, is only applicable on the left-to-right algorithm).
Algorithm 2: Binary right-to-left double-and-add-always algorithm |
Input: P, k = (k_{x}-1, k_{x}-2, ? ??, ВД2 Output: Q = к ? P R0 — O; R1 — P ; for i —- 0 up to x-1 do b — 1 - ki ; Rb — 2Rb ; Rb — Rb + Rki; end return R0 |