Exploiting Collisions in Addition Chain-Based Exponentiation Algorithms
Public key cryptographic algorithms are typically based on group exponentiation algorithms, and many algorithms have been proposed in the literature based on addition chains. The authors describe attacks based on collisions of variables manipulated in group operations extending attacks described in the literature. These collisions are visible where one is able to acquire information through some suitable side channel that provides a trace during the computation of a group exponentiation algorithm, for example, through measuring the instantaneous power consumption or the electromagnetic emanations of a microprocessor. The advantage of their attacks over previous work is that the attacks can be applied to a single trace and do not require any knowledge of the input to the exponentiation algorithm.