臺灣博碩士論文加值系統

橢圓曲線密碼系統 (Elliptic curve cryptography，簡稱ECC) 是
Koblitz 以及Miller 分別於1985 年提出的公開金鑰密碼技 (Public
key cryptography)。和目前被廣泛使用的RSA 加密演算法做比較，在相同的安全強度下，橢圓曲線密碼系統使用的金鑰長度遠低於RSA 加密演算法，因此，橢圓曲線加密系統更適合應用在手持式裝置，例如悠遊卡或是手機等記憶體資源有限的行動裝置。
我們設計出了一套硬體架構，稱為橢圓曲線加密核心 (ECC core)，
可以在二元的伽羅瓦體上快速計算出橢圓曲線數學運算中最重要的純
量乘法。一個純量乘法其實是由多個二元體上的運算組合而成。這個加密核心包括多個算數元件 (Arithmetic unit，簡稱AU)、一個平方器 (Squarer)、一個控制器以及儲存元件。多個算術元件可以平行執行純量乘法中包含的運算。將多個運算平行化處理最大的好處是能夠有效地加速運算的速度。關於使用的演算法，我們利用Montgomery ladder 演算法來計算純量乘法。同時，為了提高算數元件的使用率，我們仔細地針對演算法中的所有運算去做排程。此外，我們在不同的運算元之間使用資料前送(data forwarding)技術，它減少了15%的時脈週期數目；我們也將有餘式化簡 (modular reduction) 獨立在一個時脈週期執行而非和乘法在同一個時脈週期執行，並減少了13%的關鍵路徑延遲時間。在論文中，我們也推導出擁有五個項的既約多項式的位元平行有餘式化簡的算式，能夠快速地將次數超過二元體的多項式減低成另一個次數較小的多項式，這兩個多項式在伽羅瓦體是等效的。
實作的合成結果使用台積電0.13μm 的邏輯閘資料庫。在金鑰長度
為163 位元以及233 位元的伽羅瓦體下，我們的硬體架構能分別在7.7μs 以及11.4μs 以內完成一個橢圓曲線上純量乘法的運算。在同樣的技術下，與其他論文相比較，我們的實作結果在時間方面和面積方面加成來看是目前最好的。

In this paper, we present an Elliptic Curve Cryptographic (ECC) core dedicated to performing point scalar multiplications over GF(2m). The core consists of multiple Arithmetic Units (AUs), a squarer, a controller, and storage devices. Multiple AUs can execute in parallel
to perform the crucial operations of ECC, i.e., the point scalar multiplication. The parallelism efficiently speeds up the performance of the scalar multiplication. The proposed high-performance architecture is based on the Montgomery ladder method. In order to raise the utilization of AUs and achieve high speed by reducing cycles, we carefully schedule the field operations for a single iteration of the point scalar multiplication to make AUs as busy as possible. Besides, we exploit the data forwarding technique between arithmetic devices to decrease approximately 15% of the number of cycles. To reduce the critical path delay, the multiplication and the modular reduction are implemented separately in different cycles.
We reduce about 13% of the critical path delay in our design. We also induce the bit-parallel modular reduction equations for irreducible pentanomials. The developed bit-parallel modular reduction can operate the modular reduction more efficiently than traditional reduction
method.
Using 0.13μm CMOS technology, our ECC core can implement a point scalar multiplication with coordinate conversion in 7.7μs at 243.9MHz and in 11.4μs at 242.6MHz over GF(2^163) and GF(2^233), respectively, exhibiting that our result reaches the best performance among all the other published literatures with the same technology. We also explore our architecture with different configurations, i.e. the number of AUs, the cycles needed for a binary field multiplication, and the field size, to find the optimized one under given constraints.

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Mathematical Background 6
2.1 Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Scalar Multiplications Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 LR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 LR Algorithm with NAF . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Montgomery Point Multiplication . . . . . . . . . . . . . . . . . . . . 11
2.3 Finite Field Arithmetic over GF(2m) . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.2 Squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.3 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Finite Field Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Extended Euclidean Inversion . . . . . . . . . . . . . . . . . . . . . . 21
2.4.2 Itoh-Tsujii Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Schedule Arrangement for Scalar Multiplication 26
3.1 Original Schedule for Scalar Multiplication . . . . . . . . . . . . . . . . . . . 26
3.2 Improved Schedules for Scalar Multiplication . . . . . . . . . . . . . . . . . . 28
3.2.1 Parallelization Employed to Schedules . . . . . . . . . . . . . . . . . 30
3.2.2 Removing Modular Function out of Original Schedule . . . . . . . . . 34
3.2.3 Forwarding Data to Other Components . . . . . . . . . . . . . . . . . 35
3.3 Schedule for Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Schedule for Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Implemented Hardware Design 43
4.1 Elliptic Curve Cryptographic Core . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Design of Arithmetic Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.1 Architecture of Arithmetic Unit . . . . . . . . . . . . . . . . . . . . . 45
4.2.2 Commands of AU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Squarer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Multiplier Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5 Experiment Result 63
5.1 Implementation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Comparison with Related Works . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Conclusion and Future Work 77
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

[1] W. Diffie and M. E. Hellman, ”New Directions in Cryptography,” IEEE Trans. Information Theory, vol. 22, pp. 644-654, June 1976.
[2] IEEE, IEEE 1363 Standard Specifications for Public-Key Cryptography, IEEE Standards Department, Piscataway, Jan. 2000.
[3] RSA Laboratories, PKCS #1 v2.1: RSA Cryptography Standard, RSA Laboratories, Bedford, June 2002.
[4] N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz, ”Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs,” in Cryptographic Hardware and Embedded
Systems (CHES) 2004, Aug. 2004, vol. 3156 of LNCS, pp. 119-132, Springer-Verlag.
[5] A. Cilardo, L. Coppolino, N. Mazzocca, and L. Romano, ”Elliptic Curve Cryptography Engineering,” Proceedings of the IEEE, vol. 94, no. 2, pp. 395-406, Feb. 2006.
[6] H.Wu, ”Bit-Parallel Finite Field Multiplier and Squarer Using Polynomial Basis,” IEEE Trans. Computers, vol. 51, no. 7, pp. 750-758, July 2002.
[7] K. Sakiyama, L. Batina, B. Preneel, and I. Verbauwhede, ” Multicore Curve-based Cryptoprocessor
with Reconfiguarable Modular Arithmetic Logic Units over GF(2^n),” IEEE Trans. Computers, vol. 56, no. 9, pp. 1269-1282, 2007.
[8] J. L´opez and R. Dahab, ”Improved Algorithms for Elliptic Curve Arithmetic in GF(2m),” in Selected Areas in Cryptography: 5th Annual International Workshop (SAC) 1998, Aug. 1998, vol. 1556 of LNCS, pp. 201-212, Springer-Verlag.
[9] J. L´opez and R. Dahab, ”Fast Multiplication on Elliptic Curves over GF(2m) without Precomputation,” in Cryptographic Hardware and Embedded Systems (CHES) 1999,
Aug. 1999, vol. 1717 of LNCS, pp. 316-327, Springer-Verlag.
[10] 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),” in Cryptographic Hardware and Embedded Systems (CHES) 2002, Aug. 2002, vol. 2523 of LNCS, pp. 175-192, Springer-Verlag.
[11] N. Gura, S. C. Shantz, H. Eberle, S. Gupta, V. Gupta, D. Finchelstein, E. Goupy, and D. Stebila, ”An End-to-End Systems Approach to Elliptic Curve Cryptography,” in
Cryptographic Hardware and Embedded Systems (CHES) 2002, Aug. 2002, vol. 2523 of LNCS, pp.349-365, Springer-Verlag.
[12] A. Satoh and K. Takano, ”A Scalable Dual-Field Elliptic Curve Cryptographic Processor,” IEEE Trans. Computers, vol. 52, no. 4, pp. 449-460, Apr. 2003.
[13] J. Lutz and A. Hasan, ”High Performance FPGA based Elliptic Curve Cryptographic Co-Processor,” in Proc. IEEE Int’l Conf. on Information Technology: Coding and Computing (ITCC), Los Vegas, Apr. 2004, vol. 2, pp. 486-492.
[14] S. M. H. Rodr´ıguez and F. Rodr´ıguez-Henr´ıquez, ”An FPGA Arithmetic Logic Unit for Computing Scalar Multiplication using the Half-and-Add Method,” in Proc. IEEE Int’l Conf. Reconfigurable Computing and FPGAs (ReConFig), Puebia, Sept. 2005.
[15] R. C. C. Cheung, N. J.-B. Telle, W. Luk, and P. Y. K. Cheung, ”Customizable Elliptic Curve Cryptosystems,” IEEE Trans. VLSI Systems, vol. 13, no. 9, pp. 1048-1059, Sept.
2005.
[16] K. Sakiyama, E. De Mulder, B. Preneel, and I. Verbauwhede, ”A Parallel Processing
Hardware Architecture for Elliptic Curve Cryptosystems,” in Proc. IEEE Int’l Conf. Acoustics, Speech and Signal Processing (ICASSP), Toulouse, May 2006, vol. 3, pp. 904-907.
[17] B. Ansari and M. A. Hasan, ”High-Performance Architecture of Elliptic Curve Scalar Multiplication,” IEEE Trans. Computers, vol. 57, no. 11, pp. 1143-1153, Nov. 2008.
[18] K. J¨arvinen and J. Skytt¨a, ”On Parallelization of High-Speed Processors for Elliptic Curve Cryptography,” IEEE Trans. VLSI Systems, vol. 16, no. 9, pp. 1162-1175, Sept. 2008.
[19] T. G¨uneysu and C. Paar, ”Ultra High Performance ECC over NIST Primes on Commercial FPGAs,” in Cryptographic Hardware and Embedded Systems (CHES) 2008, vol. 5154 of LNCS, pp. 62-78, Springer-Verlag.
[20] F. Sozzani, G. Bertoni, S. Turcato, and L. Breveglieri, ”A Parallelized Design for an
Elliptic Curve Cryptosystem Coprocessor,” in Proc. IEEE Int’l Conf. on Information Technology: Coding and Computing (ITCC), Los Vegas, Apr. 2005, pp. 626-630.
[21] H. M. Choi, C. P. Hong, and C. H. Kim, ”High Performance Elliptic Curve Cryptographic Processor over GF(2^163),” in Proc. IEEE Int. Symposium on Electronic Design, Test, and Applications (DELTA), Hong Kong, Jan. 2008, pp. 290-295.
[22] F. R. Henr´ıquez, N. A. Saqib, and A. D. P´erez, ”A Fast Parallel Implementation of Elliptic
Curve Point Multiplication Over GF(2m),” in Microprocessors and Microsystems, Aug. 2004, vol. 28, pp. 329-339.
[23] N. A. Saqib, F. R. Henriquez, and A. D. P´erez, ”A Parallel Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over GF(2m),” in International Parallel and Distributed Processing Symposium (IPDPS), Apr. 2004, p. 144.
[24] H. Eberle, N. Gura, and S. C. Shantz, ”A Cryptographic Processor for Arbitrary Elliptic Curves over GF(2^m),” in Application-specific Systems, Architectures and Processors, 2003, ASAP’03, IEEE International Conf., 2003, p. 444.
[25] C. Shu, K. Gaj, and T. El-Ghazawi, ”Low Latency Elliptic Cure Cryptography Accelerators for NIST Curves over Binary Fields,” in IEEE Field-Programmable Technology
(FPT), 2005, pp. 309-310.
[26] W. N. Chelton and M. Benaissa, ”Fast Elliptic Curve Cryptography on FPGA,” IEEE Trans. VLSI Systems, vol. 16, no. 2, Feb. 2008.
[27] K. J¨arvinen and J. Skytt¨a, ”Fast Point Multiplication on Koblitz Cruves: Parallelization
Method and Implementations,” Microprocessors and Microsystems, vol. 33, pp. 106-116, Mar. 2009.
[28] X. Wang and Y. Zhang, ”A Pseudo-pipelined VLSI Architecture of Two Elliptic Curve Scalar Multiplications,” in IEEE Int. Conf. of Electron Devices and Solid-State Circuits, Jan. 2009, pp. 258-261.
[29] W. Mehuron and R. G. Kammer, Digital Signature Standard, National Institute of Standards and Technology (NIST), Gaithersburg, Jan. 2000.
[30] S. Kim, M. Yung, and H. W. Lee, ”A Compact Architecture for Montgomery Elliptic Curve Scalar Multiplication Processor,” in International Workshop on Information Security Application, Berlin, 2007, vol. 4867 of LNCS, pp. 115-127, Springer-Verlag.
[31] Y. K. Lee, K. Sakiyama, L. Batina, and I. Verbauwhede, ”Elliptic-Curve-Based Security Processor for RFID,” IEEE Trans. Computers, vol. 57, no. 11, pp. 1514-1527, Nov. 2008.
[32] L. Batina, N. Mentens, K. Sakiyama, B. Preneel, and I. Verbauwhede, ”Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks,” in Annual European Symposium
on Algorithms. 2006, vol. 4357 of LNCS, pp. 6-17, Springer-Verlag.
[33] D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, Jan. 2003.
[34] T. Itoh and S. Tsujii, ”A Fast Algorithm for Computing Multiplicative Inverses in GF(2^m) Using Normal Bases,” Information and Computation, vol. 78, no. 3, pp. 171-177, Sept. 1988.