抗SPA的多点乘算法

A SPA-Resistant Multiple Scalar Multiplication Algorithm

SPA(Simple Power Analysis)攻击可能通过泄露的信息获取内存受限制的设备中的密钥,它是通过区分一次点乘运算中点加运算和倍点运算进行的。抗SPA攻击的点乘算法较多,但对于多点乘算法相关措施较少。Sharmir-NAF多点乘算法是一个时间和空间效率都非常优秀的多点乘算法。为此提出一种基于Sharmir-NAF的抗SPA攻击的多点乘算法。新的算法在内存空间消耗和计算速度上较原算法负担增加可以忽略不计,而且能够抗SPA攻击。

The Simple Power Analysis（SPA） attack might break the implementation of elliptic curve cryptosystem on memory constraint devices such as smart cartagainst. It attacks elliptic curve cryptosystem by distinguishing between point doubling and point addition in a single execution of scalar multiplication. Although there have been many SPA- resistant scalar multiplication algorithms, there are few countermeasures for multiple scalar multiplication. The Sharmir- NAF algorithm is an excellent algorithm in efficiency and memory. A new SPA- resistant multiple seahr multiplication algorithm is proposed, which is based on the Sharmir- NAF algorithm. The computational and memory overheads of the new algorithm are almost negligible, but it is SPA resistant.