利用多位元處理方法之高速高斯正規基底乘法器

A High-Speed Gaussian Normal Basis Multiplier of GF (2m) Using Multiple Bits Approach

李郁谷(Yu-Ku Li)

指導教授 ： 邱綺文

健行科技大學/電資學院/資訊工程系碩士班/碩士(2015年)

https://doi.org/10.6824/UCH.2015.00042

摘要

隨著智慧型行動裝置及無線上網普及化，越來越多人使用智慧型行動裝置如智慧型手機購物，突顯資訊安全管理的重要。建立行動商務安全則需依賴密碼系統提供的安全。公開金鑰密碼系統如橢圓曲線密碼系統(Elliptic Curve Cryptosystem (ECC))都非常依賴二進制延伸場(GF(2m))算術運算。乘法是二進制延伸場裡最重要的運算，因此有許多專家學者研究如何讓二進制延伸場乘法器能夠更省成本及更省時間，好讓橢圓曲線密碼系統更有效率地執行。二進制延伸場乘法運算的效率和其元素的表示法有很深的關係，正規基底(Normal Basis)表示法是此種元素的三種常用元素表示法之一，正規基底表示法適合用在除法、乘法反元素和指數等複雜運算上，因為這些運算至少有一半的時間需花在平方運算上。
橢圓曲線密碼系統對於智慧型行動裝置如智慧型手機有致命的吸引力，因為它的金鑰長度不到RSA密碼系統的金鑰長度五分之一，即可達到相同的安全強度。智慧型行動裝置的資源較為有限，因此附屬之元件必須符合低硬體成本及快速執行時間原則。而二進制延伸場乘法運算又是橢圓曲線密碼系統最重要的部份，因此快速及低硬體成本的二進制延伸場乘法器是最近二十年來許多專家學者的研究重心，所以本論文是希望導出快速位元-並列高斯正規基底乘法器(Gaussian Normal Basis (GNB) Multiplier)。高斯正規基底表示法是正規基底表示法的一支，幾乎是成本最節省的一個分支。雖說只是正規基底表示法的一支，但是很幸運的是，高斯正規基底表示法存在於任何正整數，除了那些可被8整除外，而且高斯正規基底表示法也適合所有美國NIST建議的m值，所以本論文導出之快速高斯正規基底乘法器極具實用性。

關鍵字

行動商務 ； 公開金鑰密碼系統 ； 橢圓曲線密碼系統 ； 乘法器 ； 高斯正規基底表示法

並列摘要

Information security on intelligent portable devices becomes more and more important as more and more intelligent portable devices are used by peoples. M-commerce is thus drastically increased among people. Secured M-commerce is based on cryptosystems. Public-key cryptosystems such as elliptic curve cryptosystem (ECC) are heavily relied on arithmetic operations in binary extension fields GF(2m). Multiplication is the most important operation among arithmetic operations in GF(2m). The efficiency of the binary extension field multiplication heavily depends on how to specify the field element representation. Normal basis (NB) is one of three popular bases. NB architectures are suitable for realizing division, multiplicative inversion, and exponentiation because such complicated circuits need square operations and NB architectures perform square operation very easily.
The elliptic curve cryptosystem is very attractive for use in intelligent portable devices owing to its small key size. The multiplier over GF(2m) is the most important part of the arithmetic that is associated with the elliptic curve cryptosystem. Intelligent portable devices with restricted resources should have low hardware cost and short execution time properties. Efficient implementation of multiplier in GF(2m) has been in the focal point of major research efforts for the last two decades. Different metrics such as execution time and hardware space are used to quantitatively measure the performance of multiplier in GF(2m). Thus, this study will develop a novel Gaussian normal basis multiplier over GF(2m) to achieve short execution time purpose. Gaussian normal basis is one special case and has almost the lowest hardware complexity of normal basis. Gaussian normal basis also almost exists for all positive integers, except those that are divisible by eight. Gaussian normal basis is available for all NIST suggested values. The proposed high-speed Gaussian normal basis multiplier can be widely applied in information security products.

並列關鍵字

M-commerce ； Public-key cryptosystem ； elliptic curve cryptosystem ； multiplier ； Gaussian normal basis

參考文獻

1. 粘添壽， 資訊與網路安全技術， 第二版， 旗標出版， 台北， 民國97年10月

2. P. - S. Chen, S.-A. Hwang, C.- W. Wu, "A Systolic RSA Public Key Cryptosystem, " ISCAS , Atlanta, GA, 12-15 May, 1996.

3. R.L. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, vol. 21, no. 2, pp. 158-164, February 1978.

4. V.Miller, “Use of elliptic curves in cryptography”, CRYPTO 85, 1985.

5. 馬季廷， 「多項式基底之心臟型陣列Mastrovito 乘法器設計」， 清雲科技大學， 碩士論文， 民國一百年。