臺灣博碩士論文加值系統

由於資訊科技之熱烈發展，如何去避免私密資料遭到密碼攻擊而造成資訊外洩損失之相關議題變得相當重要。且由於行動裝置與嵌入式系統快速發展，因此如何在硬軟體資源有限之行動系統中，滿足資訊安全需求成為相當重要之議題，資訊安全則依賴密碼系統的防護，所以密碼系統的發展受到相當多學者專家的注意及興趣。
為防止密碼系統遭受密碼攻擊造成資料外洩的損失，最好的方式即為讓密碼系統本身具有錯誤偵測能力，不讓破解密碼者利用密碼系統輸出錯誤的訊息進而輕易破解密碼系統。另外，亦可使用具高度加密等級之金鑰系統來防護密碼系統如公開金鑰系統。於公開金鑰系統中，RSA雖可提供高度的加密效果，但橢圓曲線密碼系統可利用更短的金鑰長度來達到相較於RSA相同的加密等級，此特性除了可節省加密所需之硬體複雜度，亦能縮短資料在加密過程中運算時間。橢圓曲線密碼系統之核心數值運算為有限場數值運算，於其中，乘法運算尤其重要，因大多數值運算如乘法反元素、指數運算、及除法等皆可利用乘法運算來完成，故乘法運算相對重要，卻也較複雜及耗時。
綜合上述，本論文除了因應資源有限之嵌入式亦或是行動裝置做出滿足低成本與高運算效率需求外，亦針對抵抗植入錯誤式之密碼攻擊法之議題，重新設計有限場乘法器。

Information security is heavily dependent on public key cryptosystems such as RSA. However, RSA is not available for the resource-constrained devices like embedded systems. Recent developed public key cryptosystem, Elliptic Curve Cryptosystem (ECC), is attractive for use in resource-constrained portable devices due to it can achieve the same security level, but uses less key length. Portable devices with restricted resources demand low hardware complexity and short execution time properties.
Galois/Finite field multiplication is the most crucial operation in ECC. There are three popular types of bases for representing elements in finite field, termed polynomial basis (PB), normal basis (NB), and dual basis (DB). This study is focused on PB and DB multipliers.
Recently, fault-based cryptanalysis has been proven to be an effective cryptanalysis method for both private and public key cryptosystems. Several error-detection approaches have been developed for finite field arithmetic architectures. In this dissertation, novel PB and DB multipliers with concurrent error detection capability will be proposed.

摘　要 ….. i
ABSTRACT iii
ACKNOWLEDGEMENTS v
CONTENT vi
LIST OF TABLES ix
LIST OF FIGURES x
Chapter 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Dissertation Contribution 4
1.3 Outline of the Dissertation 5
Chapter 2 MATHEMATICAL BACKGROUND 6
2.1 Algebra 6
2.1.1 Groups 6
2.1.2 Rings 6
2.1.3 Fields 7
2.2 Finite Field and Representation of Field Elements 7
2.2.1 PB Operation over GF(2m) 7
2.2.2 DB Operation over GF(2m) 8
2.2.3 NB Operation over GF(2m) 10
2.3 RESO (Re-computing with Shifted Operands) 11
2.4 SCAL (Self-Checking Alternating Logic) 12
Chapter 3 CONCURRENT ERROR DETECTION IN POLYNOMIAL BASIS MULTIPLIER OVER GF(2m) USING IRREDUCIBLE TRINOMIAL 13
3.1 Proposed PB Multiplier 13
3.1.1 Employing xm=xn+1 15
3.1.2 Utilizing xn=xm+1 15
3.1.3 Combining xm=xn+1 and xn=xm+1 for CED 16
3.2 Proposed PB Multiplier with CED Capability 19
3.2.1 The CED multiplier structure of m=2n 19
3.2.2 The CED multiplier structure of m>2n 21
3.2.3 The CED multiplier structure of m<2n 23
3.3 Comparison 27
3.4 Summary 30
Chapter 4 CONCURRENT ERROR DETECTION IN DUAL BASIS MULTIPLIER OVER GF(2m) 31
4.1 Conventional DB Multiplication 31
4.2 Proposed DB Multiplier Using The Multiplexer Approach 35
4.2.1 Comparison 37
4.3 Design of DB Multiplier with CED Capability Using SCAL Method 39
4.3.1 Self-checking Multiplexer Design 39
4.3.2 Proposed SCAL DB Multiplier 44
4.3.3 Comparison 47
4.4 Proper XOR-Tree Implementation of Low-Complexity Bit-Parallel Dual Basis Multiplier over GF(2m) 52
4.4.1 Proposed Low-Complexity Bit-Parallel Dual Basis Multiplier over GF(2m) 52
4.4.2 Comparison of Various Low-Complexity DB multipliers 54
4.4.3 Simulation Result and Discussion 56
4.5 Summary 57
Chapter 5 CONCLUSIONS AND FUTURE WORK 58
5.1 Conclusions 58
5.2 Future Work 59
BIBLIOGRAPHY 60
APPENDIX A 13-input XOR gate based multiplier source code 70
ABBREVIATIONS AND SYMBOLS 114
Hung Wei Chang, Curriculum Vitae 115

[1] Announcing the Standard for Data Encryption Standard (DES), Federal Information Processing Standards Publications (FIPS), Dec. 30, 1993. http://www.itl.nist.gov/fipspubs/fip46-2.htm
[2] Announcing the Standard for Advanced Encryption Standard (AES), Federal Information Processing Standards Publications (FIPS), Nov. 26, 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[3] RSA Cryptography Standard, RSA Laboratories. June 14, 2002. ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf
[4] D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystem,” Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, 1999, pp. 203-2213.
[5] V. Miller, “Uses of Elliptic Curves in Cryptography,” Advances in Cryptology - CRYPTO’85, LNCS 218, 1986, pp.417-426.
[6] W. Stallings, Cryptography and Network Security-Principles and Practice, Prentice Hall, 2010.
[7] R. Schroeppe, H. Orman, S. O’Malley, and O. Spatscheck, “Fast Key Exchange with Elliptic Curve Systems,” Advances in Cryptology-CRYPTO, vol.963, 1995, pp.43-56.
[8] E. D. Win, A. Bosselaers, P. D. Gersem, S. Vandenberghe, and J. Vandewalle, “A Fast Software Implementation for Arithmetic Operations in GF(2n),” Advances in Cryptology-Asiacrypt, vol. 1163, 1996, pp.65-76.
[9] A. J. Menezes, Applications of Finite Fields, Boston: Kluwer Academic, 1993.
[10] F. J. MacWilliams, and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1981.
[11] R. Lidl, and H. Niederreiter, Introduction to Finite Fields and Their Applications,New York: Cambridge Univ. Press, 1994.
[12] R. E. Blahut, Fast Algorithms for Digital Signal Processing. Reading Mass.: Addison-Wesley, 1985.
[13] I. S. Reed, and T. K. Truong, “The Use of Finite Fields to Compute Convolutions,” IEEE Trans. on Information Theory,vol.21, no.2, 1975, pp.208-213.
[14] B. Benjauthrit, and I. S. Reed, “Galois Switching Functions and Their Applications,” IEEE Trans. on Computer, vol.25, 1976, pp.78-86.
[15] C. C. Wang, and D. Pei, ”A VLSI Design for Computing Exponentiation in GF(2m) and Its Application to Generate Pseudorandom Number Sequences,” IEEE Trans. on Computers, vol.39, no.2, 1990, pp.258-262.
[16] E. R. Berlekamp, “Bit-Serial Reed-Solomon Encoder,” IEEE Trans. on Information Theory, vol. 28, 1982, pp.869-874.
[17] M. Morii, M. Kasahara, and D. L. Whiting, “Efficient Bit-Serial Multiplication and The Discrete-Time Wiener-HopfEquation OverFinite Fields,” IEEE Trans. on Information Theory, vol.35, no.6, 1989, pp.1177-1183.
[18] E. Savaş, A. F. Tenca, and C. K. Koc, “A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m),” Proc. of Cryptographic Hardware and Embedded Systems (CHES 2000), LNCS 1965, 2000, pp.277-292.
[19] J. Goodman, and A. P. Chandrakasan, “An Energy-Efficient Reconfigurable Public-Key Cryptography Processor,” IEEE Journal of Solid-State Circuits, vol. 36, no.11, Nov. 2001, pp.1808-1820.
[20] J. Grosschadl, “A Bit-Serial Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m),” Proc. of Cryptographic Hardware and Embedded Systems(CHES 2001), LNCS 2162, 2001, pp.202-219.
[21] J. Wolkerstorfer, “Dual-Field Arithmetic Unit for GF(p) and GF(2m),” Proc. of Cryptographic Hardware and Embedded Systems (CHES 2002), LNCS 2523, 2003, pp.500-514.
[22] E. Savas, A. F. Tenca, M. E. Ciftcibasi, and C. K. Koc, “Multiplier architectures for GF(p) and GF(2n),” IEE Proceedings-Computers and Digital Technology, vol. 151, no. 2, March 2004, pp.147-160.
[23] A. Satoh, and K. Takano, “A Scalable Dual-Field Elliptic Curve Cryptographic Processor,” IEEE Trans. on Computers, vol. 52, no. 4, 2003, pp.449-460.
[24] C. W. Chiou, C.-Y.Lee, and J.-M. Lin, “Unified Dual-Field Multiplier in GF(p) and GF(2k),” IET Information Security, vol.3, no.2, 2009, pp.45-52.
[25] C.-Y. Lee, Y.-H.Chen, C.W. Chiou, and J-M. Lin, “Unified Parallel Systolic Multipliers over GF(2m),” Journal of Computer Science and Technology, vol.22, no.1, 2007, pp.28-38.
[26] C. Y. Lee, “Low Complexity Bit-Parallel Systolic Multiplier Over GF(2m) Using Irreducible Trinomials,” IEE Proc.-Computer Digit Tech, vol.150, no.1, 2003, pp.39-42.
[27] C. Paar, “A New Architecture for AParallel Finite Field Multiplier with Low Complexity Based on Composite Fields,” IEEE Trans. on Computers, vol.45, no.7, 1996, pp.856-861.
[28] C. W. Chiou, L. C. Lin, F. H. Chou, and S. F. Shu, “Low Complexity Finite Field Multiplier Using Irreducible trinomials,” Electronics Letter, vol.39, no.24, 2003, pp.1709-1711.
[29] C. W. Chiou, C. Y. Lee, and J. M. Lin, “Efficient Systolic Arrays for Power-Sum, Inversion, and Division in GF(2m),” International Journal of Computer Sciences and Engineering Systems, vol.1, no.1, 2007, pp.27-41.
[30] C. Y. Lee, J. M. Lin, and C. W. Chiou, “Scalable and Systolic Architecture for Computing Double Exponentiation over GF(2m),” ActaApplicandaeMathematicae, vol.93, no.1-3, 2006, pp.161-178.
[31] C. Y. Lee, C. W. Chiou, and J.M. Lin, “Concurrent Error Detection in Apolynomial Basis Multiplier Over GF(2m),” Journal of Electronic Testing: Theory and Applications, vol.22, no.2, 2006, pp.143-150.
[32] H. W. Chang, C. W. Chiou, F. H. Chou, and W.-Y. Liang, “Concurrent error detection in polynomial basis multiplier over GF(2m) using irreducible trinomial,” Journal of computers (Special issue on Computer Arithmetic and Cryptography), vol.22, no.3, Oct. 2011, pp. 11-25.
[33] C. W. Chiou, W.-T.Huang, C. H. Chang, C.-Y.Lee, J.-M.Lin,and Y.-C. Yeh, “Design of Polynomial Basis Multiplier Over GF(2m) for Resisting Fault-Based Cryptanalysis and Off-Line Testing,” Journal of Computers, vol. 22, no.3, Oct. 2011, pp.26-36.
[34] J. L. Massey, and J. K. Omura, “Computational Method and Apparatus for Finite Field Arithmetic,” U.S.: Patent Number: 4,587,627, May 1986.
[35] A. Reyhani-Masoleh, and M. A. Hasan, “A New Construction of Massey-OmuraParallel Multiplier over GF(2m),” IEEE Trans. on Computers, vol.51, no.5, 2002, pp.511-520.
[36] C. Y. Lee, and C. W. Chiou, “Efficient Design of Low-Complexity Bit-Parallel Systolic HankelMultipliers to Implement Multiplication in Normal and Dual Bases of GF(2m),” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science, vol.E88-A, no.11, 2005, pp.3169-3179.
[37] C. W. Chiou, and C. Y. Lee, “Multiplexer-Based Double-Exponentiation for Normal Basis of GF(2m),” Computers & Security, vol.24, no.1, 2005, pp.83-86.
[38] C. W. Chiou, C.-C.Chang, C.-Y.Lee, T.-W.Hou, and J.-M. Lin, “Concurrent Error Detection and Correction In Gaussian Normal Basis Multiplier over GF(2m),” IEEE Trans. on Computers, vol.58, no.6, 2009, pp.851-857.
[39] J. Cheon, S. Park, C. Park, and S. Hahn, “Scalar Multiplication on Elliptic Curver by Frobenius Expansions,” ETRI Journal, vol. 21, no. 1, 1999, pp. 27-38.
[40] C. Lee, and J. Lee, “A Scalable Structure for a Multiplier and an Inversion Unit in GF(2m),” ETRI Journal, vol.25, no.5, Oct. 2003, pp.315-320.
[41] H. Wu, M. A. Hasan, and I. F. Blake, “New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases,” IEEE Trans. on Computers, vol.47, no.11, 1998, pp.1223-1234.
[42] C. Y. Lee, C. W. Chiou, and J. M. Lin, “Concurrent Error Detection in Abit-Parallel Systolic Multiplier for Dual Basis of GF(2m),” Journal of Electronic Testing: Theory and Applications, vol.21, no.5, 2005, pp.539-549.
[43] C. Y. Lee, J. S. Horng, and I. C. Jou, “Low-Complexity bit-Parallel Multiplier Over GF(2m) Using Dual Basis,” Journal of Computer Science & Technology, vol.21, no. 6, 2006, pp.887-892.
[44] C. W. Chiou, C.-Y.Lee, J.-M.Lin, T.-W.Hou, and C.-C. Chang, “Concurrent Error Detection and Correction in Dual Basis Multiplier Over GF(2m),” IET Circuits, Devices & Systems, vol.3, no.1, 2009, pp.22-40.
[45] C. W. Chiou, W.-Y.Liang, H. W. Chang, J.-M.Lin, and C.-Y. Lee, “Concurrent Error Detection in Semi-Systolic Dual Basis Multiplier Over GF(2m) Using Self-Checking Alternating Logic,” IET Circuits Devices System, vol. 4, no. 5, 2010, pp.382–391.
[46] H. W. Chang, W.-Y. Liang, and C. W. Chiou, “Low Cost Dual-Basis Multiplier Over GF(2m) Using Multiplexer Approach,” 2011 International Conference on Pervasive, Embedded Computing and Communication (ICPECC2011), Hong-Kong, Dec. 2011.
[47] C. Y. Lee, C. W. Chiou, and J. M. Lin, “Low-Complexity Bit-Parallel Dual Basis Multipliers Using The Modified Booth’s Algorithm,” Journal of Computers and Electrical Engineering, vol. 31, no. 7, 2005, pp.444-459.
[48] D. Boneh, R. DeMillo, and R. Lipton, “On TheImportance of Checking Cryptographic Protocols for Faults,” Proc. of Eurocrypt, Springer LNCS 1233, 1997, pp.37-51.
[49] E. Biham, and A. Shamir, “Differential Fault Analysis of Secret Key Cryptosystems,” Proceedings of Crypto, Springer LNCS 1294, 1997, pp. 513-525.
[50] J. Kelsey, B. Schneier, D. Wagner, and C. Hall, “Side-Channel Cryptanalysis of Product Ciphers,” Proc. of ESORICS, Springer, Sept. 1998, pp.97-110.
[51] R. J. Anderson, and M. Kuhn, “Low Cost Attack on Tamper Resistant Devices,” Proceedings 5th International Workshop on Security Protocols, Lecture Notes in Computer Sciences, Springer-Verlag, LNCS 1361, 1997, pp.125-136.
[52] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, “Power Analysis Attacks of Modular Exponentiation in Smartcards,” Proc. of Cryptographic Hardware and Embedded Systems (CHES’99), LNCS 1717, 1999, pp.144-157.
[53] J. S. Coron, “Resistance AgainstDifferential Power Analysis Attacks for Elliptic Curve Cryptosystems,” Proc. Cryptographic Hardware and Embedded Systems (CHES’99), LNCS 1717, 1999, pp.292-302.
[54] R. Karri R, G. Kuznetsov, and M. Goessel, “Parity-Based Concurrent Error Detection ofSubstitution-Permutation Network Block Ciphers,” Proc. Cryptographic Hardware and Embedded Systems (CHES’03), Springer LNCS 2779, 2003, pp.113-124.
[55] G. Bertoni, L. Breveglieri, I. Koren, P. Maistri, and V. Piuri, “Error Analysis and Detection Procedures for a Hardware Implementation of The Advanced Encryption Standard,” IEEE Trans. on Computers, vol. 52, no. 4, 2003, pp.492-505.
[56] M. Joye, A. K. Lenstra, and J. J. Quisquater, “Chinese Remaindering Based Cryptosystems in The Presence of Faults,” Journal of Cryptology, vol. 12, 1999, pp.241-245.
[57] D. Boneh, R. A. DeMillo, R. J. Lipton, “On TheImportance of Eliminating Errors in Cryptographic Computations,” Journal of Cryptology, vol. 14, 2001, pp.101-119.
[58] S. Fenn, M. Gossel, M. Benaissa, and D. Taylor. “On-Line Error Detection for Bit-Serial Multipliers in GF(2m),” Journal of Electronic Testing: Theory and Applications, vol. 13, 2008, pp.29-40.
[59] A. Reyhani-Masoleh, and M. A. Hasan, “Error Detection in Polynomial Basis Multipliers OverBinary Extension Fields,” Proc. of Cryptographic Hardware and Embedded Systems (CHES’02), LNCS 2523, 2002, pp.515-528.
[60] A. Reyhani-Masoleh, and M. A. Hasan, “Fault Detection Architectures for Field Multiplication Using Polynomial Bases,” IEEE Trans. Computers, vol. 55, no. 9, Sept. 2006, pp.1089-1103.
[61] C. W. Chiou, “Concurrent Error Detection in Array Multipliers for GF(2m) Fields,” IEE Electronics Letters, vol. 38, no. 14, 2002, pp.688-689.
[62] C. W. Chiou, C. Y. Lee, A. W. Deng, and J. M. Lin, “Concurrent Error Detection In Montgomery Multiplication Over GF(2m),” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, vol. E89-A, no. 2, 2006, pp.566-574.
[63] H. Yamamoto, T. Watanabe, and Y. Urano, “Alternating Logic and Its Application to Fault Detection,” Proc. 1970 IEEE International Computing Group Conference, Washington, D.C., June 1970, pp.220-228.
[64] D. A. Reynolds, and G. Metze, “Fault Detection Capabilities of Alternating Logic,” Proc. 6th Annual Symposium on Fault Tolerant Computing, June 1976, pp.157-162.
[65] S. E. Woodard, and G. Metze, “Self-Checking Alternating Logic: Sequential Circuit Design,”ISCA’78: Proceedings of the 5th annual symposium on Computer architecture, NY, USA, 1978, pp.114-122.
[66] D. A. Reynolds, and G. Metze, “Fault Detection Capabilities of Alternating Logic,” IEEE Transactions on Computers, vol. C-27, no. 12, 1978, pp. 1093-1098.
[67] T.-P. Chuang, C.W. Chiou, and S.-S. Lin, “Self-Checking Alternating Logic Bit-Parallel Gaussian Normal Basis Multiplier with Type-t,” IET, Information Security, vol. 5, no. 1, 2001, pp. 33-42.
[68] S. Bayat-Sarmadi, and M. A. Hasan, “Concurrent Error Detection in Finite-Field Arithmetic Operations Using Pipelined and Systolic Architectures,” IEEE Trans. on Computers, vol. 58, no. 11, 2009, pp. 1553-1567.
[69] C.-Y. Lee; Y.-H.Chiu, J.-H. Chiu, “Concurrent Error Detection in Shifted Dual Basis Multiplier over GF(2m) Using Cyclic Code Approach,” 2010 IEEE 24th International Conference on Advanced Information Networking and Applications Workshops (WAINA), 2010, pp. 234-239.
[70] C.-Y. Lee, and P. K. Meher, “Fault Tolerant Dual Basis Multiplier Over GF(2m),” IEEE Circuits and Systems International Conference on Testing and Diagnosis, 2009 ( ICTD 2009), 2009, pp.1-4.
[71] A. K. Singh, A. Bera, H. Rahaman, J. Mathew, and D. K. Pradhan, “Error Detecting Dual Basis Bit Parallel Systolic Multiplication Architecture over GF(2m),” IEEE Circuits and Systems International Conference on Testing and Diagnosis 2009 (ICTD 2009), 2009, pp.1-4.
[72] S. T. J. Fenn, M. Benaissa, and D. Taylor, “GF(2m) multiplication and division over the dual basis,” IEEE Trans. Computers, Vol.45, No.3, pp.319-327, March 1996.
[73] C. L. Wang, and J. L. Lin, “Systolic array implementation of multipliers for finite fields GF(2m),” IEEE Trans. on Circuits and Systems, vol.38, no.7, 1991, pp.796-800.
[74] S. E. Woodard, “Design of Digital Systems Using Self-Checking Alternating Logic,” Ph.D. Thesis, University of Illinois at Urbana-Champaign, U.S.A., 1977.
[75] N. H. E. Weste, K. Eshraghian, and M. J. S. Smith, Principles of CMOS VLSI Design: A Systems Perspective with Verilog/VHDL Manual, Addison Wesley, 2000.
[76] M74HC86, Quad Exclusive OR Gate, STMicroelectronics. http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000351.pdf
[77] M74HC08, Quad 2-input AND Gate, STMicroelectronics. http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000249.pdf.
[78] M74HC259, 8-bit Latch, STMicroelectronics. http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000290.pdf.
[79] M74HC32, Quad 2-input OR Gate, STMicroelectronics.
http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000301.pdf.
[80] M74HC11, Triple 3-input AND Gate, STMicroelectronics. http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000254.pdf.
[81] M74HC157, Quad 2 Channel Multiplexer, STMicroelectronics.
http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00000270.pdf.
[82] M74HC4852, 4-to-1 Multiplexer, STMicroelectronics.
http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00002956.pdf.