The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks
The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks
复制标题
DOI：
10.1007/3-540-36563-x_23
复制
发表时间：
2003-04
期刊：
影响因子：
--
通讯作者：
K. Okeya;T. Takagi
中科院分区：
文献类型：
--
作者：
K. Okeya;T. Takagi
侧信道攻击（SCA）是对具有稀缺计算资源的可穿戴设备的严重攻击。它们上的加密算法应该使用小内存高效-我们必须努力优化效率和内存之间的权衡。本文提出了一种基于窗口方法的高效抗SCA标量乘法算法。Möller在2 w进制窗口方法的基础上提出了一种抗SPA窗口方法，该方法将w-连续0替换为1 + w-连续1，需要2 w个表点（如果使用带符号的2 w进制，则需要2 w-1+1个表点）。最有效的窗口方法是宽度-wNAF，它需要2 w-2个表点。在本文中，我们转换的宽度wNAF到一个抗SPA加成链。事实上，我们生成一个标量序列与固定的模式，例如0。0x0.. 0x... 0.. 0x，其中x为正奇数点<2 w。因此，表的大小为2 w-1，这在基于宽度-wNAF的抗SPA链的构造中是最优的。对于w = 2，3，4，5，所提出的方案的表大小比Möller方案的表大小小6%到50%，这是160位ECC的效率意义上的相关选择。
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. Möller proposed an SPA-resistant window method based on 2w-ary window method, which replacesw-consecutive zeros to 1 plusw-consecutive 1 and it requires 2wpoints of table (or 2w-1+1 points if the signed 2w-ary is used). The most efficient window method with small memory is the width-wNAF, which requires 2w-2points of table. In this paper we convert the width-wNAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. 0..0x0..0x...0..0x, wherexis positive odd points < 2w. Thus the size of the table is 2w-1, which is optimal in the construction of the SPA-resistant chain based on width-wNAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Möller’s scheme forw= 2, 3, 4, 5, which are relevant choices in the sense of efficiency for 160-bit ECC.