Efficient Counter-measures for Thwarting the SCA Attacks on the Frobenius Based Methods

摘要

The Frobenius endomorphism r is known to be useful for efficient scalar multiplication on elliptic curves defined over a field with small characteristic (E(F_(q~m))). However, on devices with small resources, scalar multiplication algorithms using Frobenius are, as the usual double-and-add algorithms, vulnerable to Side Channel Attacks (SCA). The more successful countermeasure for thwarting the SCA attacks on the Frobenius-based τ—adic method seems to be the multiplier randomization technique introduced by Joye and Tymen. This technique increases the computational time by about 25%. In this paper, we propose two efficient counter-measures against SCA attacks, including the powerful RPA and ZPA attacks. First, we propose to adapt the Randomized Initial Point technique (RIP) to the τ — adic method for Koblitz curves with trace 1 by using a small precomputed table (only 3 points stored). We present also an efficient fixed base τ — adic method SCA-resistant based on the Lim and Lee technique. For this purpose we modify the τ — NAF representation of the secret scalar in order to obtain a new sequence of non-zero bit-strings. This, combined with the use of Randomized Linearly-transformed coordinates (RLC), will prevent the SCA attacks on the fixed base τ — adic method, including RPA and ZPA. Furthermore, our algorithm optimizes both the size of the precomputed table and the computation time. Indeed, we only store 2~(w-1) points instead of ((3~w-1)/2) for the fixed-base τ — adic method, with a more advantageous running time.