簡易檢索 / 詳目顯示

研究生: 莊臺寶
Tai-Pao Chuang
論文名稱: 高斯正規基底有限場乘法器具容錯架構之電路設計
Fault-Tolerant Gaussian Normal Basis Multiplier over GF(2m)
指導教授: 林順喜
Lin, Shun-Shii
邱綺文
Chiou, Che-Wun
學位類別: 博士
Doctor
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2011
畢業學年度: 99
語文別: 英文
論文頁數: 72
中文關鍵詞: 橢圓曲線密碼系統植入錯誤式破解密碼攻擊法即時錯誤偵測即時錯誤修正自我偵測交互邏輯電路N個模組冗餘
英文關鍵詞: elliptic curve cryptosystem, fault-based cryptanalysis, concurrent error detection, concurrent error correction, self-checking alternating logic circuit, N-modular redundancy
論文種類: 學術論文
相關次數: 點閱:217下載:7
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • Miller 與 Koblitz曾提出橢圓曲線密碼系統(ECC)的使用。在相同安全等級下,ECC密碼系統的金鑰位元數要比RSA密碼系統少很多。例如:在相同安全等級下,RSA密碼系統的金鑰需使用1024個位元,但ECC密碼系統只需使用160個位元。ECC密碼系統計算速度比RSA密碼系統快。在計算資源有限的設備下,這項優點使得ECC密碼系統的選用,更具吸引力,如:行動智慧型手機。不幸的是智慧型手機上的密碼系統,對於側通道攻擊非常脆弱,包括植入錯誤式破解密碼攻擊法。
    ECC密碼系統高度依賴有限場算術運算,特別是伽羅瓦有限場GF(2m)。這些算術運算包括:加法、乘法、乘法反元素與次方。使用互斥或閘,很容易達成加法運算。乘法反元素與次方,比加法與乘法需要耗用更多的時間,但是可以用迭代式乘法達成。因此一個有效率的有限場乘法器是密碼系統應用的基本工具。
    近來發展的植入錯誤式破解密碼攻擊法,是針對對稱式與非對稱式加密演算法,將錯誤植入密碼系統,己經被證明是一種有效的破解密碼攻擊方法。側通道攻擊是使用特定故意植入的錯誤,加諸於加密設備中,進行錯誤分析。只要少量的側通道資訊,就能破解這種設備的安全性。加密設備的錯誤輸出,會引起主動攻擊。因此從攻擊者角度思考,最簡單的保護加/解密電路的方法,就是確定是正確的值,才由加密設備輸出。
    針對對稱式與非對稱式密碼系統,很多錯誤偵測的機制被提出來,能輸出正確的值。針對有限場算術運算,也有很多錯誤偵測的機制被發展出來,如:同位元預測函數,時間冗餘方式等。然而一些單一錯誤不能被激發,以及對於現有設備已存在的錯誤無法偵測出來。
    超大型積體電路(VLSI)通常不易測試,其理由之一,如:高比率的設備接點,這使得在VLSI晶片中的內部訊號線,可控制性與可觀察性非常有限。為解決此測試問題,可測試性設計是常用的方式。所以我們提出自我偵測交互邏輯位元並列輸入並列輸出高斯正規基底乘法器,來達成即時錯誤偵測、即時錯誤修正與離線測試能力。
    更進一步,我們需要即時錯誤偵測與即時錯誤修正能力。針對抵抗植入錯誤式破解密碼攻擊法的有限場算術運算,有很多錯誤偵測的機制被發展出來。雖然現存的高斯正規基底乘法器,具有錯誤偵測的能力,但在同一時間,都僅能容忍一個模組發生錯誤,都無法容忍多個模組發生錯誤。
    我們提出位元並列輸入並列輸出高斯正規基底容錯乘法器。其容錯機制是利用資料冗餘技術來達成CED、CEC能力,乘法器並沒有經過特殊電路設計。其容錯設計,可適用於N個模組冗餘,而且系統的穩定度能隨著t增加而增加。

    Miller and Koblitz proposed the use of Elliptic Curve Cryptosystem (ECC). ECCs can use much smaller key bits than RSA to deliver the same level of security. For instance, ECC with a 160-bit key and RSA with a 1024-bit key have the same security level. ECC computes faster than RSA. These benefits make ECC more attractive than RSA for use as cryptosystems on devices with limited resources such as portable smart phones. Unfortunately, cryptosystems on smart phones are highly vulnerable to side-channel attacks, including fault-based attacks.
    ECC strongly depends on finite field arithmetic operations, especially GF(2m). These GF(2m) operations include addition, multiplication, multiplicative inversion, and exponentiation. Addition in GF(2m) is easily performed using XOR gates. Multiplicative inversion and exponentiation are much more time-consuming than the other two basic operations, addition and multiplication, but can be performed using iterative multiplications. Hence, efficient implementation of multiplication is fundamental in cryptographic applications.
    Recently developed fault-based cryptanalysis, in which faults are injected into cryptosystems, has been proven to be an effective method of attack against symmetrical and asymmetrical encryption algorithms. The side-channel attacks using differential fault analysis will typically deliberate fault injection into cryptographic devices. The security on these devices can be broken by a small amount of side-channel information. The faulty outputs of cryptographic devices can lead to an active attack. Hence, simple methods for protecting the encryption/decryption circuitry from an attacker are required to confirm accurate outputs of cryptographic devices.
    Many error-detection schemes have been presented for symmetrical and asymmetrical cryptosystems to output corrected values. Numerous error-detection schemes have been developed for finite field arithmetic operators. For instances: parity prediction function, time-redundancy approach, etc. However, some single faults are not excited and are undetectable by existing error detection approaches.
    VLSI circuits are usually very difficult to test for various reasons, such as their high device-to-pin ratio, which seriously limits the controllability and observability of internal signal lines in a VLSI chip. To solve this testing problem, design-for-testability (DFT) approaches are commonly employed. So we propose self-checking alternating logic (SCAL) bit-parallel GNB multiplier with type-t over GF(2m) which has both concurrent error detection and off-line testing capabilities.
    Furthermore, not only concurrent error detection (CED) but also concurrent error correction (CEC) capabilities are needed. Numerous error-detection schemes have been developed for finite field arithmetic operations for resisting fault-based cryptanalysis. Although existing GNB multipliers with CEC capability can correct errors, they only tolerate one module fault at one time; that is, they cannot tolerate multiple module faults. So we propose a fault-tolerant bit-parallel GNB multiplier with type-t over GF(2m). The proposed fault-tolerant scheme utilizes data redundancy technology to achieve CED and/or CEC capabilities without specially designed circuit in multiplier. The proposed GNB multiplier works in NMR and its system reliability increases as t increases.

    Acknowledgment iv 摘 要 v Abstract vii List of Figures xi List of Tables xii Chapter 1 Introduction 1 Chapter 2 Gaussian Normal Basis 5 2.1 Finite Field 5 2.2 Normal Basis 6 2.3 Gaussian Normal Basis 7 2.4 Optimal Normal Basis 8 Chapter 3 Self-Checking Alternating Logic Bit-Parallel Gaussian Normal Basis Multiplier with Type-t 10 3.1 Self-Checking Alternating Logic 10 3.2 The Proposed Bit-Parallel GNB Multiplier with Type-t 11 3.3 The Proposed SCAL GNB Multiplier with Type-t 22 3.4 Probability of Error Detection 29 3.5 Research Results 30 Chapter 4 Fault-Tolerant Bit-Parallel Gaussian Normal Basis Multiplier with Type-t 32 4.1 Hardware Redundancy Structures 33 4.2 The Proposed Bit-Parallel GNB Multiplier 34 4.3 The Proposed Bit-Parallel GNB Multiplier with CED Capability 43 4.4 Fault-Tolerant GNB Multiplier 46 4.4.1 The Fault-Tolerant GNB Multiplier with Type-3 by Using TMR 47 4.4.2 The Fault-Tolerant GNB Multiplier with Type-t (t>3) by NMR 50 4.5 Fault Coverage and System Reliability for the Proposed Fault-Tolerant GNB Multiplier Using NMR 54 4.6 Research Results 58 Chapter 5 Conclusion and Future Work 60 5.1 Conclusion 60 5.2 Future Work 61 References 62 List of Publications 68 Appendix : Published Paper 72

    [1] V. S. Miller, “Use of elliptic curves in cryptography,” Advances in Cryptology Crypto’85, LNCS 218, Springer-Verlag, pp.417-426, 1986.
    [2] N. Koblitz, “Elliptic curve cryptosystems,” Math. Comput., Vol.48, pp.203-209, 1987.
    [3] W. Caelli, E. Dawson, S. Rea, “PKI, Elliptic curve cryptography and digital signatures,” Computer & Security, Vol.18, No.1, pp.47-66, 1999.
    [4] S. Vanstone, “Elliptic curve cryptosystem – the answer to strong, fast public-key cryptography for securing constrained environments,” Information Security Technical Report, Vol.2, No.2, Elsevier, pp.78-87, 1997.
    [5] D. Boneh, R. DeMillo, R. Lipton, “On the importance of checking cryptographic protocols for faults,” Proc. of Eurocrypt, Springer LNCS 1233, pp.37-51, 1997.
    [6] E. Biham, A. Shamir, “Differential fault analysis of secret key cryptosystems,” Proceedings of Crypto, Springer LNCS 1294, pp. 513-525, 1997.
    [7] J. Kelsey, B. Schneier, D. Wagner, C. Hall, “Side-channel cryptanalysis of product ciphers ,” Proc. of ESORICS, Springer, pp.97-110, Sep. 1998.
    [8] R.J. Anderson, 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.
    [9] I. Biehl, B. Meyer, V. Müller, “Differential fault attacks on elliptic curve cryptosystems,” CRYPTO 2000, LNCS, Vol.1880, Springer-Verlag, pp.131-146, 2000.
    [10] M. Ciet, M. Joye, “Elliptic curve cryptosystems in the presence of permanent and transient faults,” Cryptology ePrint Archive, 2003/028, 2003, http://eprint.iacr.org/2003/028.pdf.
    [11] J. Blömer, M. Otto, J.P. Seifert, “Sign change fault attacks on elliptic curve cryptosystems,” FDTC 2006, LNCS 4236, pp.36-52, 2006.
    [12] S. Fenn, M. Gossel, M. Benaissa, D. Taylor, “On-line error detection for bit-serial multipliers in GF(2m),” Journal of Electronic Testing: Theory and Applications, Vol.13, pp.29-40, 1998.
    [13] A. Reyhani-Masoleh, M.A. Hasan, “Error detection in polynomial basis multipliers over binary extension fields,” Proc. of Cryptographic Hardware and Embedded Systems-CHES 2002, LNCS 2523, pp.515-528, 2003.
    [14] A. Reyhani-Masoleh, M.A. Hasan, “Fault detection architectures for field multiplication using polynomial bases,” IEEE Trans. Computers, Vol.55, No.9, pp.1089-1103, Sep. 2006.
    [15] C.-Y. Lee, C.W. Chiou, J.L. Lin, “Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m),” Journal of Electronic Testing: Theory and Applications, Vol.21, No.5, pp.539-549, 2005.
    [16] C.W. Chiou, “Concurrent error detection in array multipliers for GF(2m) fields,” IEE Electronics Letters, Vol.38, No.14, pp.688-689, Jul. 2002.
    [17] C.W. Chiou, C.-Y. Lee, J.M. Lin, “Concurrent Error Detection in a Polynomial Basis Multiplier over GF(2m),” Journal of Electronic Testing: Theory and Applications, Vol.22, No.2, pp.143-150, Apr. 2006.
    [18] C.W. Chiou, C.-Y. Lee, A.W. Deng, 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, pp.566-574, Feb. 2006.
    [19] C.W. Chiou, C.C. Chang, C.-Y. Lee, T.W. Hou, J.M. Lin, “Concurrent Error Detection and Correction in Gaussian Normal Basis Multiplier over GF(2m),” IEEE Trans. Computers, Vol.58, No.6, pp.851-857, Jun. 2009.
    [20] C.-Y. Lee, C.W. Chiou, J.M. Lin, “Concurrent Error Detection in Multiplexer-Based Multipliers for Normal Basis of GF(2m) Using Double Parity Prediction Scheme,” Journal of Signal Processing Systems, Vol.58, No.2, pp.233–246, Apr. 2010.
    [21] C.-Y. Lee, “Concurrent Error Detection architectures for Gaussian normal basis multiplication Over GF(2m),” Integration, the VLSI journal, Vol.43, pp.113-123, 2010.
    [22] A. Bark, C. Kinne, “The application of pulse position modulation to digital computers,” Proc. National Electronics Conference, pp.656-664, Sep. 1953.
    [23] H. Yamamoto, T. Watanabe, Y. Urano, “Alternating logic and its application to fault detection,” Proc. 1970 IEEE International Computing Group Conference, Washington, D.C., pp. 220-228, Jun. 1970.
    [24] D.A. Reynolds, G. Metze, “Fault detection capabilities of alternating logic,” Proc. 6th Annual Symposium on Fault Tolerant Computing, pp. 157-162, Jun. 1976.
    [25] D.A. Reynolds, G. Metze, “Fault detection capabilities of alternating logic,” IEEE Trans. Computers, Vol.c-27, No.12, pp.1093-1098, Dec. 1978.
    [26] 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.
    [27] C.W. Chiou, T.C. Yang, “Self-purging redundancy with adjustable threshold for tolerating multiple module failures,” Electronics Letters, Vol.31, No.11, pp.930-931, May 1995.
    [28] A. Reyhani-Masoleh, “Efficient algorithms and architectures for field multiplication using Gaussian normal bases,” IEEE Trans. Computers, Vol.55, No.1, pp.34-47, Jan. 2006.
    [29] S. Kwon, “A low complexity and a low latency bit parallel systolic multiplier over GF(2m) using an optimal normal basis of type II,” Proc. of the 16th IEEE Symposium on Computer Arithmetic, Santiago de Compostela, Spain, pp.196-202, Jun. 2003.
    [30] N. Takagi, J.-I. Yoshiki, K. Takagi, “A fast algorithm for multiplicative inversion in GF(2m) using normal basis,” IEEE Trans. Computers, Vol.50, No.5, pp.394-p.398, May 2001.
    [31] C.H. Kim S. Kwon, C.P. Hong, “FPGA implementation of high performance elliptic curve cryptographic processor over GF(2163),” Journal of Systems Architecture, 54, pp.893-900, Mar. 2008.
    [32] W.N. Chelton and M. Benaissa, “Fast Elliptic Curve Cryptography on FPGA,” IEEE Transactions on Very Large Scale Integration Systems, Vol.16, No.2, pp.198-205, Feb. 2008.
    [33] A.J. Menezes, Applications of finite fields, Kluwer Academic Publications, 1993.
    [34] T.C. Bartee, D.J. Schneider, “Computation with finite fields,” Information and Computing, Vol.6, pp.79-98, Mar. 1963.
    [35] E.D. Mastrovito, “VLSI architectures for multiplication over finite field GF(2m),” Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, pp.297-309, Jul. 1988.
    [36] Ç.K. Koç, B. Sunar, “Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields,” IEEE Trans. Computers, Vol.47, No.3, pp. 353-356, Mar. 1998.
    [37] T. Itoh, S. Tsujii, “Structure of parallel multipliers for a class of fields GF(2m),” Information and Computation, Vol.83, pp.21-40, 1989.
    [38] C.-Y. Lee, E.H. Lu, J.Y. Lee, “Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials,” IEEE Trans. Computers, Vol.50, No.5, pp.385-393, May 2001.
    [39] C. Paar, “A new architecture for a parallel finite field multiplier with low complexity based on composite fields,” IEEE Trans. Computers, Vol.45, No.7, pp.856-861, Jul. 1996.
    [40] H. Wu, “Bit-parallel finite field multiplier and squarer using polynomial basis,” IEEE Trans. Computers, Vol.51, No.7, pp.750-758, Jul. 2002.
    [41] H. Fan, M.A. Hasan, “A new approach to subquadratic space complexity parallel multipliers for extended binary fields,” IEEE Trans. Computers, Vol.56, No.2, pp.224-233, Feb. 2007.
    [42] H. Wu, M.A. Hasan, I.F. Blake, “New low-complexity bit-parallel finite field multipliers using weakly dual bases,” IEEE Trans. Computers, Vol.47, No.11, pp.1223-1234, Nov. 1998.
    [43] S.T.J. Fenn, M. Benaissa, D. Taylor, “GF(2m) multiplication and division over the dual basis,” IEEE Trans. Computers, Vol.45, No.3, pp.319-327, Mar. 1996.
    [44] M. Wang, I.F. Blake, “Bit serial multiplication in finite fields,” SIAM J. Disc. Math., Vol.3, No.1, pp.140-148, Feb. 1990.
    [45] E.R. Berlekamp, “Bit-serial Reed-Solomon encoder,” IEEE Trans. Inform. Theory, Vol.IT-28, pp.869-874, Nov. 1982
    [46] C.-Y. Lee, C.W. Chiou, “Efficient Design of Low-Complexity Bit-Parallel Systolic Hankel Multipliers to Implement multiplication in Normal and Dual Bases of GF(2m),” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, Vol.E88-A, No.11, pp.3169-3179, Nov. 2005.
    [47] J.L. Massey, J.K. Omura, “Computational method and apparatus for finite field arithmetic,” U.S. Patent Number 4,587,627, May 1986.
    [48] C.C. Wang, T.K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, I. S. Reed, “VLSI architectures for computing multiplications and inverses in GF(2m),” IEEE Trans. Computers, Vol.C-34, No.8, pp.709-717, Aug. 1985.
    [49] C.W. Chiou, C.-Y. Lee, “Multiplexer-Based Double-Exponentiation for Normal Basis of GF (2m),” Computers & Security, Vol.24, No.1, pp.83-86, 2005.
    [50] G.B. Agnew, R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone, “An implementation for a fast public-key cryptosystem,” Journal of Cryptology, Vol.3, pp.63-79, 1991.
    [51] M.A. Hasan, M.Z. Wang, V.K. Bhargava, “A modified Massey-Omura parallel multiplier for a class of finite fields,” IEEE Trans. Computers, Vol.42, No.10, pp.1278-1280, Oct. 1993.
    [52] H. Fan, M.A. Hasan, “Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases,” IEEE Trans. Computers, Vol.56, No.10, pp.1435-1437, Oct. 2007.
    [53] N. Weste, K. Eshraghian, Principles of CMOS VLSI Design: A System Perspective, Reading, Mass.: Addison-Wesley, 1985.
    [54] ‘M74HC86, Quad Exclusive OR Gate,” STMicroelectronics, 2001, http://www.st.com/stonline/books/pdf/docs/2006.pdf
    [55] ‘M74HC08, Quad 2-Input AND Gate,” STMicroelectronics, 2001, http://www.st.com/stonline/books/pdf/docs/1885.pdf
    [56] ‘M74HC279, Quad Latch,” STMicroelectronics, 2001, http://www.st.com/stonline/books/pdf/docs/1937.pdf
    [57] ‘M74HC00: Quad 2-input NAND Gate,” 2001 STMicroelectronics, http://www.st.com/stonline/products/literature/ds/1879/m74hc00.pdf
    [58] S.C. Fang, J.M. Wang, W.S. Feng, “A New Direct Design for Three-Input XOR Function on the Transistor Level,” IEEE Trans. on Circuits and System-I: Fundamental Theory and Applications, Vol.43, No.4, pp. 343-348, Apr. 1996.
    [59] T.-P. Chuang, C.W. Chiou, S.-S. Lin, “Self-checking alternating logic bit-parallel Gaussian normal basis multiplier with Type-t”, IET Information Security, Vol.3, Iss. 1, pp.33-42, Mar. 2011.
    [60] F.P. Mathur, P.T. de Sousa, “Reliability Modeling for Analysis of General Modular Redundant Systems,” IEEE Trans. Reliability, Vol.R-24, No.5, pp.296-299, Dec. 1975.
    [61] J.L. Bricker, “A Unified Method for Analyzing Mission Reliability for Fault-Tolerant Computer,” IEEE Trans. Reliability, Vol.R-22, No.2, pp.72-77, Jun. 1973.
    [62] Y.-W. Ng, Reliability Modeling and analysis for Fault-Tolerant Computers, Ph. D. Thesis, University of California at Los Angeles, printed by University Microfilms International, USA, 1981.
    [63] I.F. Blake, R.M. Roth, G. Seroussi, “Efficient arithmetic in GF(2n) through palindromic representation,” HPL-98-134, Aug. 1998.
    [64] C.W. Chiou, C.-Y. Lee, J.-M. Lin, "Unified Dual-Field Multiplier in GF(P) and GF(2k)", IET Information Security, Vol.3, No.2, pp.45-52, Jun. 2009.
    [65] C.-Y. Lee , Y.-H. Chen, C. W. Chiou, J.-M. Lin, “Unified Parallel Systolic Multipliers over GF(2m)”, Journal of Computer Science and Technology, Vol.22, No.1, pp.28-38, Jan. 2007.
    [66] C.-Y. Lee, C. W. Chiou, “New Bit-Parallel Systolic Architectures for Computing Multiplication, Multiplicative inversion and Division in GF(2m) under the Polynomial Basis and the Normal Basis,” Journal of Signal Processing Systems, Vol.52, No.3, pp.313-324, Sep. 2008.
    [67] C.-Y. Lee, C.W. Chiou, J.-M. Lin, “Low-Complexity Bit-Parallel Dual Basis Multipliers Using the Modified Booth’s Algorithm,” Computers & Electrical Engineering, Vol.31, No.7, pp.444-459, Oct. 2005.
    [68] C.-Y. Lee, Y.H. Chiu, C.W. Chiou, “New Bit-Parallel Systolic Multiplier over GF(2m) using the Modified Booth's Algorithm,” 2006 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS 2006), Singapore, pp.611-614, Dec. 2006.

    下載圖示
    QR CODE