论文部分内容阅读
Koblitz和Miller分别独立提出的椭圆曲线密码体制（ECC），是基于椭圆曲线离散对数问题的。在ECC的实现中，标量乘（点乘）dP的计算是基本的运算，通常用“倍点-点加”的方法来计算，其中d表示一个标量而P表示椭圆曲线上的一个点。在会议CRYPTO 1991上，Koblitz提出了在特征为2的子域曲线上实现ECC，利用Frobenuis影射的运算在正规基下只是移位操作，然后用Frobenuis运算代替倍点操作，大大提高了标量乘算法的运算效率。在CRYPTO 1997上，Solinas提出了Koblitz曲线上的τ-NAF算法，如果在有限域F2m上进行运算，标量d的海明重量将会降低到m／3，这也就是在标量乘运算中需要的点加运算的次数。用（?）表示一个复数τ的共轭复数，Avanzi通过利用（（?），1）-double展开，第一次将半点操作与τ-NAF相结合，在不增加存储要求的情况下，将标量的海明重量降低到了2n／7。后来，Avanzi等人又提出了wide-double-NAF的方法，将标量的海明重量进一步降低到了n／4。本文中，我们利用Lucas序列，在Koblitz曲线上使用数位集合，其中w是任意整数，将Avanzi等人的wide-double-NAF方法推广到wide-w-NAF。由于这种方法不需要窗口的预计算和存储，所以实现了在没有增加存储需求的情况下，大大提高了Koblitz曲线上标量乘计算的速度。分析表明当60＜n＜216时取w=5，wide-w-NAF方法就会比wide-double-NAF方法快13％-28％，比τ-NAF方法快35％-46％。由于这种算法同时具有时间和空间上的高效，所以非常适合在小型设备如智能卡中应用。在某些密码设备上实现基于离散对数问题的公钥密码算法时，比如在智能卡上，边带信道攻击会成为一个特别有效和方便攻击。边带信道攻击通过分析密码设备的功耗，或者是分析与功耗相关的信息，来得到与密钥有关的信息。这种分析方法不仅对基于“模幂”操作的公钥密码构成了威胁，对对称密码也是很大的威胁。所以，设计可以抵抗边带信道攻击的高效算法，成为当务之急，各种抵抗算法也曾出不穷。在Koblitz曲线上，由于标量乘算法与一般曲线的上算法有所不同，所以，对于边带信道攻击的分析和抵抗方法也会有所差异。但是，以往出现的Koblitz曲线上的抵抗算法只有抵抗SPA和DPA的方法，却没有针对Doubling攻击和RPA的分析。本文分析了如何改造Doubling攻击来攻击Koblitz曲线上的标量乘算法，而后提出了一种利用半点操作对输入的点进行随机化的方法，然后将其与Koblitz曲线上的固定窗口算法结合起来，来抵抗上面提到的各种边带信道攻击。分析表明，构造的算法不仅具备了可以抵抗SPA、DPA、RPA、ZPA和Doubling攻击的性质，而且保持了运算的高效，在实现中具有实际意义。