【作者】 庞世春；

【导师】 刘淑芬；

【作者基本信息】 吉林大学 ， 计算机系统结构， 2010， 博士

【摘要】 目前,椭圆曲线标量乘法是椭圆曲线密码研究的热点问题之一。椭圆曲线标量乘法运算是基于椭圆曲线的数据加密、数字签名和密钥协商的主要的操作,因而,其计算算法直接影响各种椭圆曲线密码系统的实现效率,尤其是在智能卡、手机等计算能力、存储空间、网络带快受限的应用,标量乘法的实现效率问题显得更为重要。边信道攻击是利用密码设备的边信道泄露,攻击密钥的一种新的攻击手段,对很多原来的标量乘算法是一个巨大威胁。今天,所有的椭圆曲线密码实现都开始重视采取对边信道攻击的防范措施。提高提高椭圆曲线标量乘法的计算效率的技术很多,如:有符号二进制表示,非邻接表示型,混合坐标系策略,预计算,加法链等,一些特殊的椭圆曲线具有的特性也有助于提高标量乘的运算效率。对抗边信道攻击的方法主要是三类。统一加法公式,归一化点乘算法和随机化技术,但这些对抗措施都会带来标量乘法运算速度的损失,一个合理的标量乘法应当均衡考虑密码系统的计算速度和安全性上。综合利用各种提高标量乘法计算效率和安全性的多种技术,才能得到理想的椭圆曲线密码系统实现方案。本文深入分析了各种标量乘法的实现算法和对抗边信道攻击的措施,提出了一些能抵御边信道攻击的椭圆曲线标量乘算法。本文的主要贡献和研究成果如下:1.提出了一种基于二叉树加法链的椭圆曲线标量乘法。提出了二叉树加法链的概念,丰富了加法链方法的内涵,并基于该加法链提出了标量乘算法。算法利用了一种新的点加速度快的混合坐标系策略,提高了计算效率,二叉树加法链具有的特殊结构又使它天然地具有抵御边信道攻击的能力。2.提出了一种改进的安全的椭圆曲线标量乘法。针对一般的二进制方法安全性不高的特点,提出了一种简单的有符号二进制编码方案,并将其应用于二进制窗口方法的标量乘法中,该方法能够抵御简单边信道攻击。该方法弥补了一些安全性缺陷,并提出了在点加运算中使用某些随机变量来对抗差分边信道攻击的方法。3.提出了一种改进的Montgomery阶梯算法。算法继承了基本Montgomery阶梯算法能对抗简单边信道攻击的安全性,同时,对安全性作了进一步提高,算法是一个并行的算法,特别适合于多处理器的密码设备,算法还采用了y坐标恢复的技术,进一步提高了计算效率。4.提出了一种新的抵抗边信道攻击的Montgomery曲线标量乘法。提出了斐波那契型数列的概念,斐波那契型数列结构上的特点使得它能够充分发挥Montgomery型曲线运算速度快的优势,算法采用了加法链方法来抵御简单边信道攻击,采用了黄金比率加法链方法减少加法链的长度,进一步提高了运算效率。5.提出了一种新的基于随机投影表示的标量乘算法随机投影表示是抵御边信道攻击的重要手段之一,本算法提出了利用随机投影表示对基点P进行随机化的方法,当该方法用于Montgomery曲线,且采用不使用y坐标的点加公式,标量乘法的运算效率同不使用随机化技术的算法相同,不需要额外的域操作。该方法还可以应用于其他类型的曲线,如Weierstrass曲线,Jacobian曲线。该方法应用于Montgomery曲线时,能高效地抵御简单边信道攻击,比其他能抵御简单边信道攻击的方法运算效率要高。.6.提出了一种新的基于随机乘数的安全标量乘算法。算法对标量k的非邻接表示型(NAF)进行了随机化再编码,隐藏了作为密钥的标量k的信息,能够抵御差分边信道攻击。另外,算法采用了能抵御简单边信道攻击的加减链标量乘算法。并且由于每次循环执行时的时间与具体的随机数有关,因而算法能够抵御时间攻击。更多还原

【Abstract】 At present, elliptic curve scalar multiplication is one of the important practical problems. Elliptic curve scalar multiplication is the main operation of elliptic curve cryptography (ECC) based protocols, such as ECIES, ECDSA, and ECDH. Computation speed of elliptic curve scalar multiplication will directly case affect implementation efficiency of ECC based cyptosystem, which is more considerable for smart card or cell phone, where the computing power, storage spaces, width of network is limited.Side-channel analysis (SCA) or information leakage analysis (ILA) refers to a new and emerging type of cryptanalysis that uses leaked side-channel information frome a cryptographic device to determine the secret key. It is a great threat to original elliptic curve scalar multiplication. Today, more and more attention has been driven to take countermeasure to defend SCA attack.Many mothds can be applied to enhance computing efficiency of elliptic curve scalar multiplication, such as signed binary presentation, non-adjacant form (NAF), mixed coordinates strategy, precomputation, addition chain and so on. Some special kind of elliptic curv, such as Koblitz curve, hyperelliptic curve, Montgomery-form elliptic curve, who possesses some special features, have more efficient scalar multiplication. There are three kinds of countermeasures to defend side channel analysis, unified addition formulae, regular point multiplication algorithm, and randomization techniques. Each such method will reduce the computation efficiency of elliptic curve scalar multiplication. A reasonable scalar multiplication should balance the computing speed and computing efficiency of cryptosystem. An ideal elliptic curve cryptosystem can be obtained only by integrateing and optimizing different methods to inhance computing efficiency and computing speed. This paper deeply analizes different kinds of implementation algorithm of elliptic curve scalar multiplication and countermeasurs to defend side channel analysis, and proposed some side channel analysis resistant elliptic curve scalar multiplication algorithms.The main contributions and accomplishments of this dissertation are as follows:1. Proposing an bintree addition chain based elliptic curve scalar multiplication.The concept of bintree was proposed, which enrich addition chain theory. A new scalar multiplication algorithm was proposed basing bintree addition chain. The algorithm adoppted a new mixed coordinate strategy and got the most fast point addition formulae , which enhances computing efficiency. Special structure of bintree addition chain maks it can defend side channel analysis naturally.2. Proposing a improved algorithms for securing elliptic scalar multiplication against side channel attacks.Considering the general binary method is not secure, the paper proposd a simple signed binary encoding scheme, wich is applied to binary window based scalar multiplication. The algorithm can resist side channel analysis and make up some secure flaw. In the end, An efficient randomization technique, using some random variables within the point addition operation, has also been proposed as a possible countermeasure against a DPA-style attack on the window-family algorithm.3. Proposing a improved Montgomery ladder based algorithm.The algorithm inherits secure feature of resisting side channel analysis from basis of Montgomery ladder algorithm. Meanwhile the secure level is further improved. The algorithm, which is to get high computing speed, is particularly applicable to multi-processor cyptophic devices. A y -coordinate recovery method is also apllied to improve computation speed further.4. Proposing a new SCA resistant scalar multiplication of Montgomery-form curve.The concep of Fabonacci-form series was proposed. Special structure of Fabonacci-form series takes full advantages of high computing speed of Montgomery-form curve. Addition chain method is also applied to resist simple side channle analysis. The length of addition chain was optimized by golden ratio addition chain, which improved computing efficiency deeply.5. Proposing a new scalar multiplication algorithm based on randomized projective coordinate expression.Randomized projective coordinate expression is one of the main measures to SCA attack. In the algorithm, base point P is randomized, and the its computational cost is the same as the computational cost of an operation of points without randomized expression. In the case of a Montgomeryform elliptic curve, we compute addition of two points in randomized projective coordinates using these difference points in unrandomized projective coordinates, namely, the Z-coordinate of the point to be 1, the resultant point is in randomized projective coordinates, and no extra field operations are required. The scalar multiplication method with randomized projective coordinates on a Montgomery-form elliptic curve is applicable to other types of elliptic curve, such as the Weierstrass form, and other coordinate systems, such as Jacobian coordinate. The scalar multiplication method on a Montgomery-form elliptic curve is effective against the simple power analysis (SPA) attack and is much faster than other scalar multiplication methods which prevent SPA.6. Proposing a new scalar multiplication algorithm based on randomized projective coordinate expression.The algorithm provides a differently randomized signed-scalar representation at every multiplication execution so that it makes DPA infeasible. In addition it uses an addition-subtraction multiplication algorithm to resist SPA. It also seems to be able to defeat timing attacks because every execution time of a scalar multiplication changes according to every differently randomized signed-scalar representation. The result shows that it needs no additional computation load compared to the ordinary binary scalar multiplication.更多还原