Secure 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. Moller proposed an SPA-resistant window method based on 2{sup}w-ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive 1{top}- and it requires 2{sup}w points of table (or 2{sup}(w-1) + 1 points if the signed 2{sup}w-ary is used). The most efficient window method with small memory is the width-w NAF, which requires 2{sup}(w-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{sup}w. Thus the size of the table is 2{sup}(w-1), which is optimal in the construction of the SPA-resistant chain based on width-w NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Moller's scheme for w = 2,3,4, 5, which are relevant choices in the sense of efficiency for 160-bit ECC.