- 學位論文
在現場可程式化邏輯閘陣列上實作有效率的流線型吾乃數論家別版
An efficient FPGA implementation of Streamlined NTRU Prime
摘要
隨著量子電腦的出現，現有的公鑰密碼演算法已不安全，因此美國國家標準暨技術研究院(NIST)開始徵集能抵抗量子電腦攻擊的後量子密碼演算法，其徵集的演算法分為公鑰加密(密鑰交換)和數位簽章，在第三輪的NIST後量子密碼學標準化進程中，NTRU Prime是其中一種公鑰加密的備選者。本篇論文在被NIST所接受的Xilinx Artix-7 FPGA上實作Streamlined NTRU Prime密碼系統。我們實現了一個脈動架構的多項式模反元素計算和Good’s trick 數論轉換多項式乘法，它們分別是密鑰生成和封裝/解封裝的核心功能。對於NIST安全級別3，密鑰生成的實作使用915個slices、10.5個BRAMs和8個DSPs；封裝/解封裝的實作使用 3270個slices，16.5個BRAMs和7個DSPs。密鑰生成的最高實現頻率為111MHz，而封裝/解封裝為77MHz，受雜湊函數所限。密鑰生成、封裝和解封裝分別需要8404μs、645μs和1523μs。據我們所知，這是首個在Xilinx Artix-7 FPGA上的硬體實作。為了與Streamlined NTRU Prime的其他最新實作進行比較，我們也在Xilinx Zynq Ultrascale+ FPGA上實作其核心功能。在幾乎相同的執行時間下，多項式模反元素計算的slice數量減少47%，而多項式乘法的slice數量減少20%且執行時間減少62%。
並列摘要
With the advent of quantum computers, the existing public key cryptographic algorithms are no longer secure. Therefore, National Institute of Standards and Technology (NIST) began soliciting proposals for post-quantum cryptographic algorithms that can resist quantum computer attacks. The soliciting algorithms are divided into public-key encryption(key exchange) and digital signature. NTRU Prime is one of the alternate Candidates of public-key encryption in the third round of the NIST Post-Quantum Cryptography Standardization Process. This paper implements Streamlined NTRU Prime cryptosystem on Xilinx Artix-7 FPGA, which is accepted by NIST. We implement a systolic architecture of polynomial inversion and Good’s trick NTT polynomial multiplication, which are the core functions of key generation and encapsulation/decapsulation respectively. For the NIST security level 3, key generation implementation uses 915 slices, 10.5 BRAMs and 8 DSPs; encapsulation/decapsulation implementation uses 3270 slices, 16.5 BRAMs and 7 DSPs. The maximum achieved frequency of key generation is 111 MHz, while encapsulation/decapsulation is 77 MHz, which is limited by the hash function. Key generation, encapsulation and decapsulation take 8404μs, 645μs and 1523μs respectively. To our knowledge, this work is the first hardware implementation on Xilinx Artix-7 FPGA. In order to compare with the state-of-art implementation of Streamlined NTRU Prime, we also implement the core functions on on Xilinx Zynq Ultrascale+ FPGA. The slices of polynomial inversion are reduced by 47% with almost the same execution time, and the slices of polynomial multiplication are reduced by 20% and the execution time is reduced by 62%.