二元扩域超奇异 Koblitz曲线的标量乘计算

摘要

Supersingular Koblitz curves over binary extension field are the widely used curves in current dual pairings calculation .In this paper we study the fast implementation algorithm of scalar multiplication algorithms on supersingular Koblitz curves over binary extension field.Since on Koblitz curves there are the special endomorphism map τ, this makes it possible to alter the scalar multiplication algorithm from the“double-and-add” algorithm to the “τ-and-add” algorithm, therefore the operation efficiency of scalar multiplication can be improved largely.Based on this thought, in this paper we present the implementation algorithm of τ-adic NAF (TNAF) window scalars multiplication on supersingular Koblitz curves over binary extension field .Meanwhile, in order to resist SPA ( simple power analysis ) attack, we further improve TNAF algorithm to regular sequence TNAF algorithm .Taking ω=4 as the example , the scalar multiplication algorithm based on TNAF4 is 50% faster than the one based on binary NAF 4 and 23% faster than the traditional Montgomery scalar multiplication in same security strength.%二元扩域超奇异Koblitz曲线是目前双线性对计算中被广泛采用的曲线。研究二元扩域超奇异Koblitz曲线上标量乘的快速实现算法。由于Koblitz曲线存在特殊的自同态映射τ，使得标量乘算法可以由“double-and-add”算法变成“τ-and-add”算法，因此可以大大提高标量乘的运算效率。基于这个思想，提出了二元扩域超奇异Koblitz曲线上基于τ的非相邻表示型TNAF （τ-adic Non-Adjacent Form）窗口标量乘的实现算法；同时，为了抵御简单功耗分析SPA（Simple Power Analysis）攻击，将TNAF算法进一步改进为规则序列TNAF算法。以窗口取4为例，在同等安全强度下，规则序列TNAF4算法的运算效率比传统的二进制规则序列NAF4标量乘算法提高50％，比传统的Montgomery标量乘算法提高23％。