在FPGA上實作快速恆定時間之模反元素計算

Fast constant-time modular inversion on FPGA

白暐辰(Wei-Chen Pai)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201902901

摘要

由於量子電腦的發明,現行密碼系統越來越趨於不安全,為此美國國家標準暨技術研究院已開始徵求並篩選,致力於制定一套或多套的後量子公鑰密碼系統演算法標準,NTRU Prime 即為其中一篇成功闖進第二回合的密碼系統演算法。本論文將此密碼系統演算法實作在FPGA 上。在其計算過程中,需要一求多項式的模反元素的計算,此計算耗時極長,幾乎佔了整個公鑰產生過程的絕大多數時間,我們也嘗試著利用一輾轉相除法的變形來改善此問題,以達到加速之目的。

關鍵字

美國國家標準暨技術研究院 ； 後量子密碼學 ； NTRU ； FPGA實作 ； 多項式模反元素 ； 輾轉相除法

並列摘要

Because of the development of the quantum computer, current cryptographic algorithms are getting insecure. The NIST has initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. NTRU Prime is one of the submissions that have advanced into the 2nd round of the project. This thesis implements the algorithm on FPGA. Furthermore, inside the algorithm, the function used to compute the reciprocal of the polynomial cost most of the time in key generation. We try to use the variant of Euclid’s algorithm to optimize the function for accelerating.

並列關鍵字

NIST ； post-quantum cryptography ； NTRU ； FPGA implementation ； polynomial reciprocal ； Euclid’s algorithm

參考文獻

[1] Jeffrey Hoffstein, Jill Pipher, and Joseph H Silverman. Ntru: A ring-based public key cryptosystem. In International Algorithmic Number Theory Symposium, pages 267–288. Springer, 1998.

[2] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange—a new hope. In 25th {USENIX} Security Symposium ({USENIX} Security 16), pages 327–343, 2016.

[3] Erdem Alkim, Roberto Avanzi, Joppe Bos, Léo Ducas, Antonio de la Piedra, Thomas Pöppelmann, Peter Schwabe, and Douglas Stebila. Newhope-algorithm specifications and supporting documentation. First Round NIST PQC Project Submission Document, 2017.

[4] Niels Möller. On schönhage’s algorithm and subquadratic integer gcd computation. Mathematics of Computation, 77(261):589–607, 2008.

[5] Emmanuel Thomé. Subquadratic computation of vector generating polynomials and improvement of the block wiedemann algorithm. Journal of symbolic computation, 33(5):757–775, 2002.