SCA-Resistant and Fast Elliptic Scalar Multiplication Based on wNAf

摘要

The side channel attack (SCA) is a serious attack on wearable devices that have scarce computational resources. Cryptographic algorithms on them should be efficient using small memory―we have to make efforts to optimize the trade-off between efficiency and memory. In this paper we present efficient SCA-resistant scalar multiplications based on window method. Moeller proposed an SPA-resistant window method based on 2~ω-ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive 1 and it requires 2~ω points of table (or 2~(ω-1) + 1 points if the signed 2~ω-ary is used). The most efficient window method with small memory is the width-ω NAF, which requires 2~(ω-2) points of table. In this paper we convert the width-w NAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. ∣0 ··· 0x∣0 ··· 0x∣··· ∣0 ··· 0x∣, where x is positive odd points < 2~ω. Thus the size of the table is 2~(ω~1), which is optimal in the construction of the SPA-resistant chain based on width-ω NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Moeller's scheme for ω = 2,3,4,5, which are relevant choices in the sense of efficiency for 160-bit ECC.