二元體上橢圓曲線密碼之多核處理器

A Multi-Core ECC Processor over Binary Fields

許遠哲(Yuan-Che Hsu)

指導教授 ： 鄭振牟

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

https://doi.org/10.6342/NTU201800997

摘要

橢圓曲線密碼是公鑰密碼系統中的一大基石，而美國政府將一系列的曲線制定為標準。針對二元體上最高的安全等級，我們提出了一個最快的橢圓曲線密碼多核心處理器，並實作於現場可程式邏輯閘陣列中。演算法的層面上，我們選擇了最具競爭力的一套運算公式，並設法找出對多核心最佳化的排程；數位電路的層面上，我們基於快速相乘算法設計了一個高吞吐量的乘法器作為運算核心，並比較不同形式乘法器之間的差異；計算機組織的層面上，我們採用了一個簡潔的架構，並將其擴充成多核心的版本。總而言之，我們實作了一個極高速的橢圓曲線密碼處理器，讓運算效能達到更高的境界。

關鍵字

橢圓曲線密碼 ； 多核心處理器 ； 快速相乘算法 ； 現場可程式邏輯閘陣列

並列摘要

Elliptic Curve Cryptography (ECC) is a popular building block of public key protocols. A set of curves are standardized by the National Institute of Standards and Technology (NIST). Aiming at the highest security level, we propose the fastest multi-core ECC implementation over binary fields on FPGAs. In the aspect of algorithm, we choose the most competitive laddering formula, and seek the optimal instruction sequences according to different number of cores. In the aspect of digital circuits, we design a high-throughput multiplier based on the Karatsuba-Ofman Algorithm (KOA), and make a thorough comparison among different styles of multipliers. In the aspect of computer architecture, we adopt a compact structure, and extend it to a multi-core version. In conclusion, we implement an extremely high-speed ECC processor for NIST curves, pushing the performance to the limits.

並列關鍵字

ECC ； Multi-Core Processor ； KOA ； FPGA

參考文獻

[1] G. Locke and P. Gallagher, “Fips pub 186-3: Digital signature standard (dss),” Federal Information Processing Standards Publication, vol. 3, pp. 186–3, 2009.

[2] N. Shylashree and V. Sridhar, “Efficient implementation of scalar multiplication for ecc in gf (2m) on fpga,” in Emerging Research in Electronics, Computer Science and Technology (ICERECT), 2015 International Conference on, pp. 472–476, IEEE, 2015.

[3] M. Imran, M. Kashif, and M. Rashid, “Hardware design and implementation of scalar multiplication in elliptic curve cryptography (ecc) over gf (2163) on fpga,” in Information and Communication Technologies (ICICT), 2015 International Conference on, pp. 1–4, IEEE, 2015.

[4] S. Liu, L. Ju, X. Cai, Z. Jia, and Z. Zhang, “High performance fpga implementation of elliptic curve cryptography over binary fields,” in Trust, Security and Privacy in Computing and Communications (TrustCom), 2014 IEEE 13th International Conference on, pp. 148–155, IEEE, 2014.

[5] Z. U. Khan and M. Benaissa, “High speed ecc implementation on fpga over gf (2 m),” in Field Programmable Logic and Applications (FPL), 2015 25th International Conference on, pp. 1–6, IEEE, 2015.