橢圓曲線加密是一種非對稱式加密演算法，近年來已受到學術界以及業界的高度注目，和現今廣為使用的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.

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Mathematical Background 5
2.1 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Scalar multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 LR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 LR Algorithm with NAF . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Montgomery Scalar Multiplication . . . . . . . . . . . . . . . . . . . 9
2.3 Modulo Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Bit-Parallel Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Finite Field Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Extended Euclidean Inversion . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Itoh-Tsujii Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Operation Scheduling for Montgomery Scalar Multiplication 21
3.1 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Scheduling Result and Variables Life Time . . . . . . . . . . . . . . 24
3.1.2 Cycles for Scalar Multiplication . . . . . . . . . . . . . . . . . . . . 30
3.2 Itoh-Tsujii for GF(2163) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Schedule for Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Hardware Architecture 36
4.1 ECC Core for Scalar Multiplication . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Finite Field Multiplier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Arithmetic Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.1 Architecture of AU . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.2 Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Finite Field Squarer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 Implementation and Comparison 51
5.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2 Comparison with Related Works . . . . . . . . . . . . . . . . . . . . . . . . 55
6 Conclusion and Future Work 59
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

[1] Guerric Meurice de Dormal and Jean-Jacques Quisquater, “High-Speed Hardware
Implementations of Elliptic Curve Cryptography: A Survey”, Journal of Systems
Architecture, Vol. 53, pp. 72-84, 2007.
[2] F. Sozzani, G. Bertoni, S. Turcato, and L Breveglieri, “A Parallelized Design for an
Elliptic Curve Cryptosystem Coprocessor”, Symposium on Information Technology:
Coding and Computing (ITCC), 1, pp. 626-630, 2005.
[3] C. Shu, K. Gaj, and T. el-Ghazawi, “Low Latency Elliptic Curve Cryptography Accelerators
for NIST Curves on Binary Fields”, IEEE Field-Programmable Technology
(FPT), pp. 309-310, 2005.
[4] Hyun Min Choi, Chun Pyo Hong, and Chang Hoon Kim, “High Performance Elliptic
Curve Cryptographic Processor over GF(2163)”, 4th IEEE International Symposium
on Electronic Design, Test and Applications,23-25, pp. 290-295, Jan. 2008.
[5] Gang Chen, Guoqiang Bai, and Hongyi Chen, “A Dual-Field Elliptic Curve Cryptographic
Processor Based on a Systolic Arithmetic Unit”, IEEE International Symposium
on Circuits and Systems, 18-21, pp. 3289-3301, May. 2008.
[6] Kimmo J¨arvinen and Jorma Skytt¨a, “On Parallelization of High-Speed Processors for
Elliptic Curve Cryptography”, IEEE Transactions on Very Large Scale Integration
(VLSI) Systems, Vol. 16, Issue 9, pp. 1162-1175, Sep. 2008.
[7] Kazuo Sakiyama, Lejla Batina, Bart Preneel, and Ingrid Verbauwhede, “Multicore
Curve-Based Cryptoprocessor with Reconfigurable Modular Arithmetic Logic Units
over GF(2n)”, IEEE Transactions on Computers, Vol. 56, Issue 9, pp. 1269-1282,
Sep. 2007.
[8] Huapeng Wu, “Bit-Parallel Finite Field Multiplier and Squarer Using Polynomial
Basis”, IEEE Transactions on Computers, Vol. 51, Issue 7, pp. 750-758, July 2002.
[9] Tsohiya Itoh and Shigeo Tsujii, “A Fast Algorithm for Computing Multiplicative
Inverses in GF(2m) Using Normal Bases”, Information and Computation, Vol. 78,
Issue 3, pp. 171-177, Sep. 1988.
[10] Bijan Ansari and M. Anwar Hasan, “High-Performance Architecture of Elliptic Curve
Scalar Multiplication”, IEEE Transactions on Computers, Vol. 57, Issue 11, pp. 1443-
1453, Nov. 2008.
[11] Jyu-Yuan Lai and Chih-Tsun Huang, “Elixir: High-Throughput Cost-Effective Dual-
Field Processors and the Design Framework for Elliptic Curve Cryptography”, IEEE
Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 16, Issue 11, pp.
1567-1580, Nov. 2008.
[12] S. Kim, M. Yung, and H.-W Lee, “A Compact Architecture for Montgomery Elliptic
Curve Scalar Multiplication Processor”, WISA 2007, LNCS 4867, pp. 115-127, 2007.
[13] Lee Yong Ki, Sakiyama Kazuo, Batina Lejla, and Verbauwhede Ingrid, “Elliptic-
Curve-Based Security Processor for RFID”, IEEE Transactions on Computer, Vol.
57, Issue 11, pp. 1514-1527, Nov. 2008.
[14] Lejla Batina, Nele Mentens, Kazuo Sakiyama, Bart Preneel, and Ingrid Verbauwhede,
“Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks”, ESAS,
LNCS, Vol. 4357, pp. 6-17, 2006.
[15] Ray C. C. Cheung, Nicolas Jean-baptiste Telle, Wayne Luk, and Peter Y. K. Cheung,
“Customizable Clliptic Curve Cryptosystems”, IEEE Transactions on Very Large
Scale Integration (VLSI) Systems, Vol. 13, Issue 9, pp. 1048-1059, Sep. 2005.
[16] Akashi Satoh and Kohji Takano, “A Scalable Dual-Field Elliptic Curve Cryptographic
Processor”, IEEE Transactions on Computer, Vol. 52, Issue 4, pp. 449-460,
Apr. 2003.
[17] Julio L´opez and Ricardo Dahab, “Fast Multiplication on Elliptic Curves over GF(2m)
without Precomputation”, CHES’99, LNCS 1717, pp. 316-327, 1999.
[18] N. Koblitz, “Elliptic Curve Cryptosystem”, Mathematics of Computation, Vol. 48,
pp. 203-209, 1987.
[19] V. Miller, “Uses of Elliptic Curves in Cryptography”, Cryptology Conference
(CRYPTO), LNCS 218, pp. 417-426, 1985.
[20] IEEE, “IEEE 1363 Standard Specifications for Public-Key Cryptography”, IEEE
Standards Department, Piscataway, Jan. 2000.
[21] Nils Gura, Arun Patel, Arvinderpal Wander, Hans Eberle, and Sheueling Chang
Shantz, “Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs”, Cryptographic
Hardware and Embedded Systems (CHES), pp. 119-132, 2004.
[22] ANSI X9.62, “The Clliptic Curve Digital Signature Algorithm (ECDSA)”, Available
from: http://www.ansi.org.
[23] J. Solinas, “Efficient Arithmetic on Koblits Curves”, Designs, Codes and Cryptography,
Vol. 19, Issue 2-3, pp. 195-249, Mar. 2000.
[24] Jyu-Yuan Lai, Chih-Tsun Huang, “A Highly Efficient Cipher Processor for Dual-
Field Elliptic Curve Cryptography”, IEEE Transactions on Circuits and Systems II:
Express Briefs, Vol. 56, Issue 5, pp. 394-398, May 2009.
[25] Hans Eberle, Nils Gura, Sheueling Chang Shantz, and Vipul Gupta, “A Cryptographic
Processor for Arbitrary Elliptic Curves over GF(2m)”, Application-Specific
Systems, Architectures, and Processors (ASAP), pp. 444-454, May 2003.
[26] Gerardo Orlando and Christof Paar, “A High-Performance Reconfigurable Elliptic
Curve Processor for GF(2m)”, Cryptographic Hardware and Embedded Systems
(CHES), LNCS 1965, pp. 44-56, 2000.
[27] Philip H. W. Leong and Ivan K. H. Leung, “A Microcoded Elliptic Curve Processor
Using FPGA Technology”, IEEE Transactions on Very Large Scale Integration
(VLSI) Systems, Vol. 10, Issue 5, pp. 550-559, Oct. 2002.
[28] Nazar A. Saqib, Francisco Rodr´ıguez-Henriquez and Arturo D´ıaz-P´erez, “A Parallel
Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over
GF(2m)”, Parallel & Distributed Processing Symposium (IPDPS), pp. 144, apr. 2004.
[29] Kazuo Sakiyama, Elke De Mulder, Bart Preneel, and Ingrid Verbauwhede, “A Parallel
Processing Hardware Architecture for Elliptic Curve Cryptosystems”, Acoustics,
Speech and Signal Processing, Vol. 3, pp. 904-907, May 2006.
[30] M. Ernst, M. Jung, F. Madlener, S. Huss, and R. Bl¨umel, “A Reconfigurable System
on Chip Implementation for Elliptic Curve Cryptography over GF(2n)”, Cryptographic
Hardware and Embedded Systems (CHES), LNCS 2523, pp. 381-399, 2002.
[31] Nele Mentens, Siddika Berna ¨Ors, and Bart Preneel, “An FPGA Implementation of
an Elliptic Curve Prodessor over GF(2m)”, ACM Great Lakes Symposium on VLSI,
pp. 454-457, 2004.
[32] Jonathan Lutz and Anwarul Hasan, “High Performance FPGA Based Elliptic Curve
Cryptographic Co-Processor”, Symposium on Information Technology: Coding and
Computing (ITCC), 2, pp. 486-492, 2004.
[33] Souichi Okada, Naoya Torii, Kouichi Itoh, and Masahiko Takenaka, “Implementation
of Elliptic Curve Cryptographic Coprocessor over GF(2m) on an FPGA”, Cryptographic
Hardware and Embedded Systems (CHES), LNCS 1965, pp. 25-40, 2000.
[34] Nghi Nguyen, Kris Gaj, David Caliga, and Tarek El-Ghazawi, “Implementation
of Elliptic Curve Cryptosystems on a Reconfigurable Computer”, IEEE Field-
Programmable Technology (FPT), pp. 60-67, Dec. 2003.
[35] Pradeep Kumar Mishra, “Pipelined Computation of Scalar Multiplication in Elliptic
Curve Cryptosystems”, IEEE Transactions on Computer, Vol. 55, Issue 8, pp. 1000-
1010, Aug. 2006.
[36] Ray C. C. Cheung, Wayne Luk, and Peter Y. K. Cheung, “Reconfigurable Elliptic
Curve Cryptosystems on a Chip”, Design, Automation and Test in Europe (DATE),
1, pp. 24-29, 2005.
[37] RSA Laboratories, PKCS #1 v2.1: RSA Cryptography Standard, RSA Laboratories,
Bedford, June 2002.