因為不同的應用需要不同的規格，如在電腦網路安全系統中較強調高輸出率，而應用在攜帶式電子上的系統則對面積和功率有比較嚴格的限制，因此，我們針對個別需求分別提出具低面積或高輸出率橢圓曲線密碼系統的架構。首先，基於改良的除法演算法，我們提出結合乘法與除法的演算法，利用此演算法可以得到低面積的橢圓曲線密碼系統。根據我們提出的改良除法演算法，位元串列式(bit-serial)的除法器能運作的與位元串列式的乘法器一樣地快速。而且，使用反置多項式(reciprocal polynomial)的概念，我們證明有限場乘法能以我們提出的改良除法演算法有效的實現。因此基於演算法基本層面的改變，只需付出極少的硬體作運算元的選擇，有限場乘法即能被有效率的嵌入除法器裡面。因為在使用affine座標的橢圓密碼系統中，乘法和除法是分開的執行，因此非常適合採用我們所提出的結合乘法與除法的硬體架構。與之前文獻提出的成果做比較，我們的架構擁有AT(面積乘以時間)的優勢。
　　針對高輸出率的有限場乘法器設計方面，我們延伸Hasan所提出的基於查表的群串列式(group-serial)的乘法演算法，進一步減少建表所需的時間，然後在我們發展的乘法器中有效的併入平方運算。由於在使用projective座標的橢圓曲線密碼系統中，乘法與平方是交替運算，特別適用此架構。由實驗的結果顯示及與Hasan的演算法作比較，使用本論文所提出之子群多重查表方案(sub-group, multiple table scheme)的乘法器能夠減少約29%的乘法運算時間。當使用在橢圓曲線密碼系統中，因為平方運算無需建表之動作，我們能減少更多橢圓倍數點的運算時間而達到約26% AT的改善。

　　We present two different hardware architectures for cost-efficient and high throughput ECC systems, respectively, because different applications require different specifications. For example, computer network security systems put emphasis on high throughput rate, while portable applications demand security hardware with more restrictions on area and power. For cost-efficient design we present a combined multiplication/division (CMD) algorithm based on the modified division algorithm. The resulting bit-serial divider based on our modified division algorithm can operate as fast as the bit-serial multiplier. Moreover, using the concept of reciprocal polynomial, this thesis shows that a field multiplication over GF(2m) can be implemented by the modified division algorithm. With a fundamental change at the algorithmic level, the field multiplication can be efficiently embedded into a divider with very little hardware overhead for operand selection. When applying the developed CMD algorithm/architecture to Elliptic Curve Cryptography (ECC) using affine coordinates, in which the multiplication and division are sequentially executed, we achieve the AT (area毕time) advantage in comparison with previous work.
　　For the high-throughput multiplier design over finite field GF(2m) with large m, we extend the group-serial look-up table (LUT) based multiplication algorithm presented by Hasan to reduce the LUT generation time and then showed how to effectively incorporate the squaring operation into the developed multiplier. The unified multiplication/squaring module is very suitable for ECC using projective coordinates in which these two types of operations are operated in a ping-pong fashion. Experimental results exhibit that using the presented sub-group, multiple look-up tables (SG-MLUT) based scheme, up to 29% improvement in the total computation time of multiplication can be achieved in comparison with that using Hasan’s algorithm. When employing the unified multiplication/squaring module instead of Hasan’s design in ECC applications, we can gain further improvement in the scalar multiplication time because no LUT generation is needed when squaring is executed using our design, and obtain about 26% reduction on the resulting AT complexity.

[1] NIST, Recommended Elliptic Curves for Government Use, Available: http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf.
[2] SECG, SEC 2: Recommended Elliptic Curve Domain Parameters, Available: www.secg.org/collateral/sec2_final.pdf
[3] ISO/IEC 14888-3, Information Technology – Security Techniques – Digital Signatures with Appendix – Part 3: Certificate Based-Mechanisms, 1998.
[4] ANSI X9.38, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), 1999.
[5] ISO/IEC 15946-4, Information Technology – Security Techniques – Cryptographic Techniques Based on Elliptic Curves – Part 4: Digital signatures giving message recovery, 2004.
[6] IEEE Std-1363-2000: Standard Specifications for Public Key Cryptography, Jan. 2000.
[7] ANSIX9.63-2001, Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. Working Draft, May 8, 2001.
[8] Certicom Corporation, The Basics of ECC 2006 [Online], Available: http://www.certicom.com/index.php?action=res,ecc_faq.
[9] National Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186-2 , Feb. 2000.
[10] R. C. C. Cheung, N. J. Telle, W. Luk, and P. Y. K. Cheung, "Customizable Elliptic Curve Cryptosystems," IEEE Trans. Very Large Scale Integration Systems, vol. 13, pp. 1048-1059, Sept. 2005.
[11] Y. Eslami, A. Sheikholeslami, P. G. Gulak, S. Masui, and K. Mukaida, "An Area-Efficient Universal Cryptography Processor for Smart Cards," IEEE Trans. Very Large Scale Integration Systems, vol. 14, pp. 43-56, Jan. 2006.
[12] P. H. W. Leong and I. K. H. Leung, "A Microcoded Elliptic Curve Processor using FPGA Technology," IEEE Trans. Very Large Scale Integration Systems, vol. 10, pp. 550-559, Oct. 2002.
[13] M. Bednara, M. Daldrup, J. von zur Gathen, J. Shokrollahi, and J. Teich, "Reconfigurable Implementation of Elliptic Curve Crypto Algorithms," Proc. IEEE International Parallel and Distributed Processing Symposium, pp. 157-164, 2002.
[14] N. A. Saqib, F. Rodriguez-Henriquez, and A. Diaz-Perez, "A Parallel Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over GF (2m)," Proc. IEEE International Parallel and Distributed Processing Symposium, 2004.
[15] M. Morales-Sandoval and C. Feregrino-Uribe, "On the Hardware Design of an Elliptic Curve Cryptosystem," Proc. IEEE the Fifth Mexican International Conference, pp. 64-70, 2004.
[16] S. B. Wicker, Error Control Systems for Digital Communication and Storage: Prentice Hall, Inc, N.J., 1995.
[17] C. H. Wu, C. M. Wu, M. D. Shieh, and Y. T. Hwang, "High-Speed, Low-Complexity Systolic Designs of Novel Iterative Division Algorithms in GF(2m)," IEEE Trans. Computers, vol. 53, pp. 375-380, Mar. 2004.
[18] C. L. Wang and J. L. Lin, "Systolic Array Implementation of Multipliers for Finite Fields GF(2m)," IEEE Trans. Circuits and Systems, vol. 38, pp. 796-800, July 1991.
[19] S. K. Jain, L. Song, and K. K. Parhi, "Efficient semisystolic architectures for finite-field arithmetic," IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol. 6, pp. 101-113, Mar. 1998.
[20] H. Brunner, A. Curiger, and M. Hofstetter, "On Computing Multiplicative Inverses in GF(2m)," IEEE Trans. Computers, vol. 42, pp. 1010-1015, Aug. 1993.
[21] J. H. Kim and D. H. Lee, "A Compact Finite Field Processor over GF(2m) for Elliptic Curve Cryptography," Proc. IEEE International Symposium on Circuits and Systems, pp. 340-343, 2002.
[22] M. A. Hasan, "Look-Up Table-Based Large Finite Field Multiplication in Memory Constrained Cryptosystems," IEEE Trans. Computers, vol. 49, pp. 749-758, July 2000.
[23] S. Liu, F. Bowen, B. King, and W. Wang, "Elliptic Curves Cryptosystem Implementation based on a Look-Up Table Sharing Scheme," Proc. IEEE International Symposium on Circuits and Systems, pp. 2921-2924, 2006.
[24] W. W. Peterson and E. J. Weldon, Error-Correcting Codes: MIT Press, Cambridge, MA, 1972.
[25] E. Al-Daoud, R. Mahmod, M. Rushdan, and A. Kilicman, "A New Addition Formula for Elliptic Curves over GF(2n)," IEEE Trans. Computers, vol. 51, pp. 972-975, Aug. 2002.
[26] A. Reyhani-Masoleh and M. A. Hasan, "Low Complexity Word-Level Sequential Normal Basis Multipliers," IEEE Trans, Computers vol. 54, pp. 98-110, Feb. 2005.
[27] G. B. Agnew, R. C. Mullin, I. M. Onyszchuk, and S. A. Vanstone, "An Implementation for a Fast Public-Key Cryptosystem," Journal of Cryptology, vol. 3, pp. 63-79, 1991.
[28] N. Takagi, J. Yoshiki, and K. Takagi, "A Fast Algorithm for Multiplicative Inversion in GF(2m) Using Normal Basis," IEEE Trans. Computers, vol. 50, pp. 394-398, May 2001.
[29] J. Park, J. T. Hwang, and Y. C. Kim, "FPGA and ASIC Implementation of ECC Processor for Security on Medical Embedded System," Proc. IEEE the Third International Conference on Information Technology and Applications, pp. 547-551, 2005.
[30] A. F. Tenca and C. K. Koc, "A Scalable Architecture for Modular Multiplication Based on Montgomery's Algorithm," IEEE Trans. Computers, vol. 52, pp. 1215-1221, Sept. 2003.