低成本橢圓曲線密碼架構之設計

Low-Cost Design for Elliptic Curve Cryptography over Binary Field

張珮玟(Pei-Wen Chang)

指導教授 ： 黃稚存

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

摘要

橢圓曲線加密是一種非對稱式的加密演算法，近年來已受到學術界以及業界的高度注目。在同樣的加密層級下和現今廣為使用的RSA演算法作為比較，橢圓曲線加密擁有較短的金鑰長度，因此，橢圓曲線加密較適合使用在對於面積以及能量消耗有嚴格要求的RFID系統。
在本論文中，我們提出了一種低成本的架構來計算橢圓曲線中重要的運算，也就是純量乘法。我們的架構包含了算術單元、控制器以及儲存設備。其中算術單元是由一個高基數的乘法器、一個加法器以及一個平方器所組成。我們希望藉由減少多工器的數目以及複雜度來達到降低面積的目的，因此將算術單元的各個元件連結在一起來減少各個元件的輸入選擇，此外也利用循環限制暫存器來減少存取。為了降低能量消耗必須在低頻率下運作，我們藉由Montgomery Ladder 演算法配合提出的架構規劃出有效率的排程結果，而在算術單元中使用平方器可以降低47%的週期數。除此之外，我們也探討對於暫存器排程控制給予不同的限制下對面積以及能量消耗的影響。
最後實作的結果所使用的是台積電65nm製程的邏輯閘資料庫，橢圓曲線核心的面積為12,859 gates，而在算一個純量乘法的時間限制為250ms的情況下，在頻率為102kHz執行一個純量乘法需要4.64μW的能量消耗。以此結果與其他設計做比較，可以看出我們在硬體成本的優點比其他橢圓曲線加密的硬體設計來的好。

關鍵字

橢圓曲線密碼 ； 射頻識別 ； 低成本 ； 低能量消耗

並列摘要

Elliptic curve cryptography (ECC) become one of the most popular public-key cryptography recently. On the same security level with RSA, ECC has shorter key length. Base on this property, ECC is more suitable for RFID tags which has limitations in space and power.
In our approach, we propose an low-cost architecture to support the crucial operation over GF(2m) of ECC, that is to say, the point scalar multiplication. The core consists
of Arithmetic Unit (AU), a controller, and storage devices. The proposed AU includes a high-radix multiplier, an adder and a bit-parallel squarer. In order to minimize the space
resource by decreasing complexity of multiplexers, we integrate the components of AU to eliminate selections of input and use circular register file architecture to limit the register access. To attain low power consumption, the design need to work at low clock frequency. Based on the Montgomery ladder algorithm, we carefully schedule the field operation of point scalar multiplication to simplify register management. Also, the use of bit-parallel squarer decreases about 47% of the number of cycles. Besides, we find trade-off between space and power with register management restrictions.
The implementation result with TSMC 65nm CMOS technology shows that the proposed design requires an area of 12,859 gates, and has a power consumption of 4.64 μW to perform
a scalar multiplication over GF(2163) in 250ms at 102kHz. The advantage of hardware cost is much favorable compared with previous similar works.

並列關鍵字

Elliptic Curve Cryptography ； radio frequency identification (RFID) ； Low cost ； Low power

參考文獻

[3] N. Koblitz, “Elliptic Curve Cryptosystems,” in Mathematics of Computation, vol. 48, pp. 203-209, 1987.

[4] V. Miller, “Uses of elliptic curves in cryptography,” in Advances in Cryptology: proceedings of Crypto’85, Lecture Notes in Computer Science, vol. 218, pp. 417-426, 1986.

[5] E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid, Recommendation for Key Management - Part 1: General, National Institute of Standards and Technology (NIST), Mar. 2007.

[6] ANSI X9.62: The Elliptic Curve Digital Signature Algorithm (ECDSA), Sep. 1998.

[8] ISO/IEC 18000-3: Information Technology - Radio Frequency Identification (RFID) for Item Management - Part 3: Parameters for air interface communications at 13.56