能對抗功率分析攻擊之橢圓曲線純量乘法演算法

EFFICIEN ALGORITHMS OF ECC SCALAR MULTIPLICATION WITH RESISTANCE AGAINST POWER ANALYSIS ATTACK

洪志揚(Zhi-Yang Hong)

指導教授 ： 汪順祥

大同大學/電機資訊學院/通訊工程研究所/碩士(2011年)

摘要

橢圓曲線加密系統 (ECC) 是一種高效能的公鑰加密系統，它是建構在橢圓曲線離散對數演算法以及橢圓曲線運算之上。橢圓曲線離散對數問題比起其他有限場的乘法群要難很多，因此在相同的安全性上，橢圓曲線加密系統的公鑰長度是比其他系統的公鑰長度來的簡短許多，所以橢圓曲線加密系統 (ECC) 非常適合在像是智慧卡 (Smart Card) 這種有限記憶體的環境下實現。然而，在智慧卡執行的同時，旁通道攻擊 (SCA) 如簡單功率分析攻擊 (SPA) 與差分功率分析攻擊 (DPA) 會使得安全性遭受嚴重的威脅。如果在實現方法上沒有小心謹慎考慮，則容易被有心人士利用旁通道攻擊 (SCA) 來偵測破壞具有橢圓曲線加密系統裝置的密鑰。 在此篇論文中，我們提出一些能對抗功率分析攻擊之有效率橢圓曲線加密純量乘法，與文獻所提出的方法比較得知我們提出的方法可以減少一些橢圓曲線加倍(EC doubling)及橢圓曲線加法(EC addition)的運算。

關鍵字

功率分析 ； 橢圓曲線加密 ； 純量乘法 ； 旁通道攻擊

並列摘要

Elliptic curve cryptosystem (ECC) is one of the effectively public key cryptography systems. It is based on the difficulty to solve the discrete logarithm problem over the points on an elliptic curve (ECDLP). The discrete logarithm problem over an elliptic curve (EC) seems to be much harder than in other groups such as the multiplicative group of a finite field. Compared with other existing public key cryptosystems, the key size of ECC is smaller than other cryptosystems in equal security level. Therefore, ECC is well-suited for the implementation on memory constraint environments such as smart card due to its small key size. However, in the execution on a smart card, side cannel attacks (SCA) such as simple power analysis (SPA) and the differential power analysis (DPA) have become serious threat. SCA can break the secret key of ECC on such devices, if the implementation method is not carefully considered. In this thesis, we propose some efficient algorithms of ECC scalar multiplication with resistance against power analysis. Compared with the algorithm proposed by Kim et al [1], our algorithm can reduce some operations of EC doubling and EC addition.

並列關鍵字

ECC ； scalar multiplication ； Side channel attack ； power analysis

參考文獻

[1] C. K. Kim, J. C. Ha, S. J. Moon, S. M. Yen, W. C. Lien, and S. M. Kim, "An improved and efficient countermeasure against power analysis attacks," Cryptology ePrint Archive, Report 2005/022, January 2005

[3] N. Koblitz, “Elliptic curve cryptosystems,” In Mathematics of Computation, vol. 48, no. 177, pp. 203-209, Jan. 1987.

[4] Darrel Hankerson, Alfred Menezes, and Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer, London, 2004.

[6] J. S. Coron, “Resistance against differential power analysis for elliptic curve cryptosystems,” Proceedings of CHES 1999, pp. 292-302, August 1999.

[7] L. Goubin, “A refined power-analysis attack on elliptic curve cryptosystems,” Proceedings of PKC2003, LNCS 2567, pp. 199-210, 2003.