High-Performance Architecture for Elliptic Curve Cryptography over Binary Field

高效能橢圓曲線密碼架構之設計

楊凱翔(Kai-Hsiang Yang)

指導教授 ： 黃稚存

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

摘要

橢圓曲線加密是一種非對稱式加密演算法，近年來已受到學術界以及業界的高度注目，和現今廣為使用的RSA演算法作為比較，橢圓曲線加密擁有較短的公鑰以及私鑰長度，卻能提供與RSA相同的加密層級，因此，橢圓曲線加密較適合用在手持式裝置，是因能減少儲存公私鑰的容量以及傳輸上所消耗的能量。

在本論文中，我們設計出一套硬體架構用來快速計算出橢圓曲線純量乘法，這是在橢圓曲線加密中相當重要的運算，除此之外，我們藉由Montgomery Ladder演算法配合不同個數的算術元件，規劃出最少暫存器的排程結果。橢圓曲線加密是建立在伽羅瓦體之上，在我們的設計中所使用到的伽羅瓦體是GF(2163)，當運算出的結果長度超過163位元就必須與一不可因式分解的多項式做模數運算，我們也推導出五個項的位元平行模數算式。

在硬體架構中，我們仔細設計運算元件使得在做純量乘法的過程中，不會有閒置的時間以便能達到高使用率，我們更在橢圓曲線核心中放入不同個數的算術元件，在比較之下找出最佳算術元件個數的橢圓曲線核心。最後的實作結果所使用的是台積電0.13m製成的邏輯閘資料庫，在擁有一個以及三個運算元件的橢圓曲線核心去計算一個純量乘法所花費的時間分別為20.9s以及11.1s；最終我們以計算一次純量乘法時間與硬體面積的乘積跟其他設計做比較，所得到的結果可以看出我們所設計的硬體架構在單位面積的使用效率上來的比其他橢圓曲線加密的硬體設計來的好。

關鍵字

橢圓曲線加密

並列摘要

Elliptic curve cryptography (ECC), a public-key cryptography, has raised much interests
and attentions recently. Compared with RSA, ECC has short key length but provides
the same security level as RSA. With this property, ECC is more suitable for the small
and portable devices. Because the short key length reduces the storage and transmission
power.
In our approach, we try to accelerate the performance of scalar multiplication, which
is an important point operation in ECC. Based on the Montgomery ladder method over
binary field GF(2n), we address the operation scheduling results for different number of
Arithmetic Units (AUs) with optimized amount of registers during the scalar multiplication.
In order to do the modular reduction over GF(2163), we derive the closed form
equations for pentanomial bit-parallel reduction. The AU is for the basic finite field operations,
such as field multiplication, field squaring, and field addition. The multiplication
inside the AU and the data transmission are well scheduled to speed up the critical operation
effectively. Multipliers with various word lengths are designed and evaluated in
terms of performance and area. The smaller word length makes the multiplier smaller
but introduces more extra cycles, and vice versa. We also present an ECC core with
different numbers of AU for the scalar multiplication. The implementation result with
TSMC 0.13μm CMOS technology shows that we can perform a scalar multiplication in
20.9μs and 11.1μs with one-AU and three-AU ECC cores over GF(2163), respectively. At
the last, the AT comparison between our approach and related works also shows that our
approach is better than others.

參考文獻

Implementations of Elliptic Curve Cryptography: A Survey”, Journal of Systems

[2] F. Sozzani, G. Bertoni, S. Turcato, and L Breveglieri, “A Parallelized Design for an

[3] C. Shu, K. Gaj, and T. el-Ghazawi, “Low Latency Elliptic Curve Cryptography Accelerators

[4] Hyun Min Choi, Chun Pyo Hong, and Chang Hoon Kim, “High Performance Elliptic

Curve Cryptographic Processor over GF(2163)”, 4th IEEE International Symposium