【作者】 刘双根；

【导师】 胡予濮；

【作者基本信息】 西安电子科技大学 ， 密码学， 2008， 博士

【摘要】 椭圆曲线密码是一种杰出的公钥密码体制。它具有众所周知的优势,在智能卡、无线网络和嵌入式系统等资源受限的设备中有广泛的应用。边信道攻击作为物理安全的一个重要部分严重威胁了智能卡的安全,其中能量攻击对椭圆曲线的标量乘运算尤为有效。本文主要研究了标量乘运算在能量攻击下的安全性和效率,旨在给出快速安全的标量乘算法。本论文主要得到以下结果:1.深入分析总结了最常见的边信道攻击-简单能量攻击,在此基础上提出了一种改进的简单能量攻击-基于马尔科夫链的能量攻击。这种方法把马尔科夫链模型运用于分析从AD序列推出密钥过程中,具体分析时把椭圆曲线标量乘算法看作马尔科夫链。理论上证明,它比简单能量攻击更有效。2.提出了一个新的抵抗简单能量攻击的椭圆曲线标量乘算法。这个算法在Comb算法[149]基础上进行改进,得到标量k的比特串序列,序列特征是所有的比特位都不为0,这个性质保证了标量乘算法的统一计算形式,进而可以抵抗简单能量攻击。结合随机化技术,这个算法可以抵抗差分能量攻击等其他边信道攻击。与其他抵抗边信道攻击的方案相比,这个算法没有牺牲效率,仅比Comb算法多一次点加和倍点运算。3.提出了一个新型快速安全的标量乘算法。该算法是一种基于仅有点加运算的特殊加法链,可自然地抵抗简单能量攻击。此外,在新型点加运算公式中利用特殊加法链的性质,可以在一定程度上提高标量乘算法的运算效率:对于长度为160比特的整数,其特殊加法链长度为260时,仅仅需要1719次乘法运算。特殊加法链长度从280到260,运行标量乘算法比倍点-点加算法效率上提高26%~31%;比NAF算法快16%~22%;比4-NAF算法快7%~13%;比目前最好的方法-双基链算法也要快1%~8%。4.将一个数学上的运算“( a + b)2 ?a2?b2=2ab”运用到Jacobian坐标系下点之间的运算,使用相对运算量稍低的平方运算代替乘法运算,可以使得点加、倍点、混加和三倍点运算的运算量减少,尤其是计算三倍点运算时,效率提高的更多。这种方法为最近使用多基链标量展开方法做快速标量乘提供了保障。5.提出了一个新的基于原子块结构的椭圆曲线标量乘算法。相比以前的原子块结构,我们的算法不但可以抵抗简单边信道攻击,而且在效率上有较大提高:使用NAF的标量展开,我们这种结构的原子块结构相比以前的方案可以提高30%。6.提出了一种高效灵活的抵抗能量攻击的方案-分拆窗口方法。该方法以改进的NAFw算法[128]为基础,不仅可以抵抗SPA而且可以抵抗SPA/DPA联合攻击和抵抗SPA/二阶DPA联合攻击,可以根据需要选择合适的窗口宽度,而且适用于存储受限的设备中。这种方法比整体窗口方法效率较高。更多还原

【Abstract】 Elliptic Curve Cryptosystem is a kind of outstanding public-key cryptosystem. It is well known for its advantages like which has wide application in smart card, wireless network and embedded systems with limited resources. As an important part of physical security, side channel attacks menace the security of these systems. Especially, the power attack is very severe for the security of scalar multiplication on Elliptic Curve. This thesis for doctor’s degree focuses on the security and efficiency of scalar multiplication on power attack and is to propose fast and secure scalar multiplications. The thesis obtains main results as follows:1. We do detailed analysis on the side channel attacks commonly used. We also propose an improved simple energy attack based on Markov Chain. This method applies the modle of Markov Chain to the anlysis of the processes of secret key from AD sequence, in which Elliptic Curve Cryptosystem scalar multiplication algorithm is used as Markov Chain. Theoretical proofs show that method is more efficient than the normal side-channel attacks.2. This thesis presentes a new SCA resistant Elliptic Curve scalar multiplication algorithm. The proposed algorithm, which builds a sequence of bit-strings representing the scalar k, is characterized by the fact that all bit-strings are different from zero. This character will ensure a uniform computation behavior for the algorithm, and thus make it secure against SPA. Combied with other randomization techniques, this algorithm can resist against other side channel attacks including differential power attack. By compare with other schemes resisting against side chanel atacks,this algorithm does not penalize the computation time and needs only one more point adding and doubling than the comb algorithm.3. A new fast and secure scalar multiplication algorithm is proposed. The algorithm is a particular addition chains based on only additions, which providing a natural protection against side channel attacks. Moreover, new addition formulae which take into account the specific structure of those chains making point multiplication very efficient are proposed. The scalar multiplication algorithm only needs 1719 multiplication for the SAC260 of 160-bit integers. From chains of length 280 to 260, our method outperforms all the previous methods with a increased efficency from 26% to 31% over the double-and-add, from 16% to 22% over NAF, from 7% to 13% over 4-NAF and from 1% to 8% over the best algorithm presently-double base chain. 4. Appling a mathematical operation“( a + b)2 ?a2?b2=2ab”on the computation between points of Jacobian coordinates, and the substitution of multiplication with squaring which is more cheaper than multiplication. Especially, these techniques can reduce the computation of doubling, addition, mixed addition and tripling. Particularly, the efficiency is improved a lot for tripling computation, providing a guarantee for fast scalar multiplication by using multi-base chains methods nowadays.5. We modify the ECC scalar multiplication to achieve a faster atomic structure when applying side channel atomicity protection. In contrast to previous atomic operations that assume squarings are indistinguishable from multiplications, our new atomic structure offers true SSCA-protection resulted from the squaring in its formulation. In the scalar multiplication using NAF, the computational efficency of our atomic blocks is increased by 30% than that of previous atomic implementations.6. Based on the improved NAFw algorithm, we present an efficient and flexible scheme resisting power attacks-the fractional windows. The fractional windows are able to resist not only SPA but also SPA /DPA combined attacks and SPA/2nd-order DPA combined attacks. The fractional windows allow us to select the appropriate window width and offer great advantages in the frame of resource-constrained devices. The fractional windows are more efficent than integral windows更多还原