臺灣博碩士論文加值系統

本論文研製之重點是構建運用於行動密碼系統之有限場數值函數，並實現於嵌入式Linux系統上。嵌入式系統應用範圍非常廣泛，包括微處理機控制器、信號處理器、工業用電腦、資訊家電等，嵌入式系統目前更廣泛用在手機和PDA等行動計算系統上，所以在嵌入式系統建立有限場數值函數程式庫是非常必要的。通訊技術日臻成熟，透過無線網路之安全議題更受到關注。一個可為大家信賴的網路交易環境，必須滿足幾項基本的安全需求：(1) 訊息隱密性(Confidentiality)，(2)訊息完整性(Integrity)，(3)身分辨識性(Authentication)，(4)交易不可否認性(Non-Repudiation)。要符合這些條件的密碼系統只有公開金鑰密碼系統(Public-key cryptosystem)，目前最為常用的是RSA密碼系統，但因為RSA密碼系統需要極長之鑰匙長度才能維持其保密性，需要極為複雜之運算電路，所以對於資源非常有限之行動計算系統是非常沉重之負擔。由於行動計算系統的普遍而引起之行動商務愈來愈盛行，因此行動商務極為依賴之電子商務安全所依靠之公開金鑰密碼系統變得非常重要。所以比RSA密碼系統更為節省電路的橢圓曲線密碼系統(金鑰長度至少節省80%)，非常適合在行動計算系統上運用。橢圓曲線密碼系統又依賴有限場數值運算，因此本研究的主題是在行動計算系統上建立有限場數值核心運算之程式庫，以提供橢圓曲線密碼系統使用。

This thesis is to develop finite field arithmetic libraries for Elliptic Curve cryptosystems in embedded Linux systems. The embedded systems were frequently desired in microprocessor controllers, digital signal processing, industrial computers, information appliances. Furthermore, the embedded systems have received attention because of their important and practical applications in areas of mobile computing systems such as smart phones and PDAs. Therefore, it is very essential to set up the finite field arithmetic libraries for the embedded systems. Communication technology is ripe day by day, paid close attention to even more through the security topic of the wireless network. The information security should fulfill the following properties: (1) authenticity, (2) integrity, (3) privacy, and (4) security. The Public-key cryptosystems can satisfy these properties, and the commonly most used is the RSA cryptosystem at present. But the RSA cryptosystem needs the extremely long key length to maintain its security, and thus needs extremely complicated circuits. Such complicated circuit is a heavy burden for the resource-limited mobile computing systems. Recently, Elliptic Curve Cryptosystem (ECC) which saves 80% key length at least rather than that of RSA provides an alternative solution for mobile computing systems. ECC relies on finite field arithmetic operations, so the goal of this research is to establish finite field arithmetic libraries for the mobile computing systems.

中文摘要 ………………………………………………………………… i
英文摘要 ………………………………………………………………… ii
誌謝 ……………………………………………………………………… iii
目錄 ……………………………………………………………………… iv
表目錄 …………………………………………………………………… vi
圖目錄 …………………………………………………………………… vii
第一章 前言 …………………………………………………………… 1
1.1研究背景及目的 …………………………………………………… 1
1.2動機 ………………………………………………………………… 3
1.3章節安排……………………………………………………………… 4
第二章 背景 ……………………………………………………………… 5
2.1 數學基礎 ………………………………………………………… 5
2.1.1環(ring)………………………………………………………… 5
2.1.2群(Groups)……………………………………………………… 6
2.1.3有限場 …………………………………………………………… 7
2.2 有限場類型及其數學運算 ………………………………………… 8
2.2.1 多項式基底……………………………………………………… 8
2.2.1.1多項式基底GF(2m)加法 ……………………………………… 8
2.2.1.2多項式基底GF(2m)乘法 (Multiplication) ………………… 9
2.2.1.3多項式基底GF(2m)反元數(Inversion) …………………… 10
2.2.1.4多項式基底GF(2m)除法(Division) ……………………… 11
2.2.2 正規基底………………………………………………………… 12
2.2.3 雙重基底…………………………………………………………… 13
第三章 有限場乘法 ……………………………………………………… 15
3.1有限場 乘法 …………………………………………………………… 15
3.2乘法演算法……………………………………………………………… 18
3.3硬體架構與軟體環境 ………………………………………………… 20
3.3.1硬體架構 …………………………………………………………… 20
3.3.2軟體環境…………………………………………………………… 20
3.3.3系統架構…………………………………………………………… 20
3.4實例 ………………………………………………………………… 21
3.4.1 PC版本的程式例子……………………………………………… 21
3.4.2 PC程式與嵌入式Linux系統上的執行結果…………………… 23
第四章 有限場反元素…………………………………………………… 26
4.1有限場 反元素 ……………………………………………………… 26
4.2反元素演算法………………………………………………………… 27
4.3實例 …………………………………………………………………… 29
4.3.1 PC版本實例………………………………………………………… 29
4.3.2 PC程式與嵌入Linux上的執行結果……………………………… 31
第五章 有限場除法………………………………………………………… 34
5.1有限場 除法…………………………………………………………… 34
5.2除法演算法……………………………………………………………… 35
5.3實例 …………………………………………………………………… 37
5.3.1 PC版本實例………………………………………………………… 37
5.3.2 PC程式與嵌入Linux上的執行結果……………………………… 39
第六章 討論和結論 ……………………………………………………… 43
參考文獻 ………………………………………………………………… 46
附錄一 有限場乘法的完整程式碼 ……………………………………… 48
附錄二 有限場反元素的完整程式碼 …………………………………… 60
附錄三 有限場除法的完整程式碼 ……………………………………… 66
簡歷 ……………………………………………………………………… 72

[1]R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol.21, No.2, pp.120-126, Feb.1978.
[2]R. Lidl, H. Niederreiter,” Introduction to Finite Fields and Their Applications”, New York: Cambridge Univ. Press, 1994.
[3]N. Kobliz, “Elliptic Curve Cryptography,” Math. Computation, Vol.48, pp.203-209, 1987.
[4]R. Schroeppel, H. Orman, S. O’Malley, and O. Spatscheck, “Fast key exchange with Elliptic Curve Systems,” Advances in Cryptology-CRYPTO 95, D. Coppersmith, ed., Berlin: Springer-Verlag, pp.43-56, 1995.
[5]E. De Win, A. Bosselaers, S. Vandenberghe, P. De Gersem, and J. Vandewalle, “A fast software implementation for arithmetic operations in GF(2n),” Advances in Cryptology-ASIACRYPT’96, K. Kim and T. Matsumoto, eds., Berlin: Springer-Verlag, pp.65-76, 1996.
[6]A. J. Menezes, “Elliptic Curve Public Key Cryptosystems”, Boston, MA: Kluwer Academic Publishers, 1993.
[7]F. Fekri, M.Sartipi, R.M.Mersereau, R.W.Schafer, “Convolutional codes using finite-field wavelets: time-varying codes and more,” IEEE Trans. Signal Processing, Vol.53, Issue 5, pp.1881–1896, May 2005.
[8]F. J. MacWilliams and N. J. A. Sloane, “The Theory of Error-Correcting Codes,” Amsterdam: North-Holland, 1977.
[9]S. Gallacher, P. S. Gallacher, “Different Channel Coding Strategies for OFDM-CDMA,” Proc. of 1997 IEEE 47th Vehicular Technology Conference, Vol. 2, 4-7, pp.845-849, May 1997.
[10]http://csrc.nist.gov/CryptoToolkit/aes/
[11]E. R. Berlekamp, “Bit-serial Reed-Solomon encoders,” IEEE Trans. Inf. Theory, Vol. IT-28, pp.869-874, 1982.
[12]C. Y. Lee, “Low complexity bit-parallel systolic multiplier over GF(2m) using irreducible trinomials,” IEE Proc.-Comput. Digit. Tech., Vol.150, No.1, pp.39-42, Jan. 2003.
[13]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, July 1996.
[14]C.W. Chiou, L.C. Lin, F.H. Chou, and S.F. Shu, “Low complexity finite field multiplier using irreducible trinomials,” Electronics Letters, Vol.39, No.24, pp.1709-1711, 27th Nov. 2003.
[15]J. L. Massey, J. K. Omura, “Computational method and apparatus for finite field arithmetic,” U.S. Patent Number 4,587,627, May 1986.
[16]A. Reyhani-Masoleh and M. A. Hasan, “A new construction of Massey-Omura parallel multiplier over GF(2m),” IEEE Trans. Computers, Vol.51, No.5, pp.511-520, May 2002.
[17]H. Wu, M. A. Hasan, and 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, November 1998.
[18]張真誠，電腦密碼學與資訊安全，初版，松崗電腦圖書公司，民國78年。
[19]賴溪松，韓亮，張真誠，近代密碼學及其應用，初版，旗標出版股份有限公司，民國92年。
[20]F. Gerd, “The Proof of Fermat's Last Theorem by R. Taylor and A. Wiles,” Notices of the AMS, Vol.42, No.7, pp.743-746, July 1995.
[21]W. Andrew, “Modular elliptic curves and Fermat's Last Theorem,” Annals of Mathematics, Vol.141, pp.443-551, 1995.
[22]G. Seroussi, “Table of Low-Weight Binary Irreducible Polynomials,” HP Labs Technical Report HPL-98-135, August 1998.