請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/1127
標題: | 現代電腦中的有限體乘法及其應用 Multiplication in Binary Fields on Modern Computers and its Applications |
作者: | Ming-Shing Chen 陳明興 |
指導教授: | 鄭振牟(Chen-Mou Cheng) |
關鍵字: | 乘法,有限體,磁碟陣列,多變量公鑰密碼,快速傅立葉變換,Boolean多項式, Multiplication,Finite Field,RAID,MPKC,FFT,Boolean Polynomial, |
出版年 : | 2018 |
學位: | 博士 |
摘要: | 本論文旨在研究使用現代電腦的向量指令集及無進位乘法來建構特徵值為二的有限體乘法,以及各種不同有限體乘法的應用。我們討論了有限體的不同表示法,以及在這些表示法之下,基於現代電腦考量下的有限體乘法的實現方法。
我們呈現了四種應用,分別對應到不同的有限體乘法實現方式。 最先呈現的應用是設計給磁碟陣列(RAID)使用的錯誤更正碼(erasure correcting code),此種錯誤更正碼現在標準磁碟陣列的錯誤更正碼的推廣,並且能有效的提昇標準編碼在四個冗餘(checksum)時的磁碟數量,從最大支援二十八磁碟推展到可支援九十六個磁碟。在這裡我們展示了使用向量指令實現有限體乘法的標準作法。 第二個應用是實作一種可以抵抗量子電腦攻擊的多變量公鑰密碼系統(MPKCs)--Rainbow,在這應用中我們主要討論在安全軟體的要求下時,有限體乘法的實現方式,以及實現多變量密碼時的矩陣乘法,多元二次多項式組的求值,和求解線性方程組時的程式寫法。 第三是討論加法性快速傅立葉變換(additive FFT)的程式實現,我們介紹使用additive FFT來求多項式的值的方法,以及如何實作一個高效率的additive FFT的方式。在這裡我們使用了乘有限體的子體(subfield)中的元素的加速方法。 最後一個應用是實作係數只能為一或零的多項式(Boolean Polynomial)的乘法器,在這裡我們結合了additive FFT及Frobenius FFT的技巧,提出了一個可以帶比較少的點至多項式就能計算乘法的的方法,並且展示了在additive FFT上帶那樣的點,就等於刪節了一些計算的FFT(truncated additive FFT),還有這些演算法的實現方式。這裡使用的有限體乘法是單純的使用硬體的無進位乘法來實現。這個應用同時也是我們再做更大的有限體乘法的關鍵元件。 We study the multiplication in the extension fields of characteristic 2 with the vector instruction set and carryless multiplication on modern computers and their applications. We describe the representations of fields in polynomial forms and vector spaces and the implementations for these representations. We present four applications corresponding to 4 different implementations of field multiplication. The first application is an erasure correcting code-- RAIDq, an extension of currently standard code in RAID-6, for the RAID. It supports a RAID system of 96 disks for the case of 4 checksums while it can only be 28 disks for current code. We show the standard implementations for multiplication in binary fields in the application. In the second application, we implement the Rainbow, a derivate of MPKCs which is believed a candidate of post-quantum cryptography. We discuss the implementation of multiplication under the requirement of secure software. We also present matrix-vector multiplication, evaluating quadratic systems, and solving linear equations under the crypto consideration. In the third application, we introduce the additive FFT for evaluating polynomials at a particular set and implement an efficient additive FFT as well. We utilize the acceleration for multiplying subfield elements in the implementation. The last application presents a multiplier for Boolean polynomials. We give a specific set for evaluating polynomials with the additive FFT, allowing to derive other values of polynomials by Frobenius map. We show the multiplication of Boolean polynomials by evaluating polynomials at the particular set. The evaluation can be performed with a truncated additive FFT. We implement the field multiplication with the instruction of carrayless multiplication here. The last application can also be a critical component for multiplication in the fields of larger size. |
URI: | http://tdr.lib.ntu.edu.tw/handle/123456789/1127 |
DOI: | 10.6342/NTU201801305 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf | 1.29 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。