橢圓曲線密碼系統於有限場GF(p)和GF(2^m)之硬體實現

Abstract

近年來廣為使用的RSA密碼系統，為了保持一定的安全性，其金鑰位元長度不斷的增加，進而加重了RSA的運算複雜度。相對於RSA，橢圓曲線密碼系統 ( ECC ) 逐漸被重視。在西元1985年，Koblitz與Miller提出橢圓曲線密碼系統，其安全性是建立在橢圓曲線離散對數問題 ( ECDLP )。目前已經被廣泛地制定於國際標準如 ISO 11770-3、ANSI X9.62、IEEE P1363、FIPS 186-2等。

橢圓曲線密碼系統的優點是，在相同的安全性下，其所使用的金鑰長度比RSA密碼系統短 ( 1024位元RSA密碼系統的安全強度等於155位元的ECC )。這個好處可以應用在智慧卡或行動電話這種記憶體跟運算能力有限的系統上面。

本論文在實作方面是利用Verilog硬體描述語言來撰寫橢圓曲線密碼系統。我們採用A.F. Tenca和C.K. Koc所提出的用於蒙哥馬利乘法的可擴充性架構 [32]，並改良使之可以支援有限場GF(p)和GF(2m)的運算。另外我們採用Projective座標系統，將除法運算轉變為乘法運算，進而降低運算結果的時間。我們利用Synopsys的合成軟體來將Verilog codes合成成電路，並加以模擬驗證。

The RSA cryptosystem used widely in recent years, for keeping the certain security degree, continuous to increase the length of public key, and aggravated the RSA to operate the complicacy. Opposite to RSA, the Elliptic Curve Cryptosystem (ECC) attracts more and more attention. In 1985, Koblitz and Miller proposed a higher security public key cryptosystem, based on ECDLP, called ECC. At present, there are several international standards proposed in ISO 11770-3, ANSI X9.62, IEEE P1363, FIPS 186-2.

The advantages of ECC are that its key sizes are smaller than RSA with equivalent levels of security (1024 bits RSA is equal to 155 bits ECC) so that it can be implemented in smart card or mobile phone.

In this thesis, we developed the hardware implementation of ECC by using Verilog HDL. We adopted the scalable architecture for Montgomery multiplication proposed by F.A. Tenca and C.K. Koc [32], and modified it to support the operations over dual-field GF(p) and GF(2m). Also, the inversion is designed in the projective coordinates that will save much computation time. We synthesize our verilog codes by software of Synopsys, and confirm by simulation.