二进制域上椭圆曲线密码ECC的高性能FPGA实现

doi:10.11896/jsjkx.200600112

摘要/Abstract

摘要： 近年来, 通信领域得到了巨大的发展, 网上银行、移动通信等应用增加了资源受限环境下的安全需求。与传统密码算法相比, 椭圆曲线密码体制(Elliptic curve cryptography, ECC)提供了更好的安全标准, 为优化性能参数提供了更大的空间。为此, 文中提出了一种高效的椭圆曲线密码硬件设计方案。该方案在已有研究的基础上, 利用投影坐标系LD Montgomery阶梯算法对ECC中最核心的标量乘运算进行了研究, 并对群运算层采用并行调度来缩短延迟;对于有限域运算, 采用位并行乘法算法和改进的Euclidean求逆算法来实现;基于Xilinx Virtex-5和Virtex-7FPGA器件, 在二进制域域长分别为163, 233和283时实现了该体系结构。实验结果表明, 该方案所需现场可编程门阵列(Field-Programmable Gate Array, FPGA)资源消耗更少, 运算速度更快, 与其他方法相比, 硬件资源消耗减少了52.9%, 标量乘法运算速度提高了5倍, 能更好地适用于资源受限设备的应用。

关键词: 标量乘法, 二进制域, 求逆, 椭圆曲线密码体制, 现场可编程门阵列

Abstract: In recent years, the communications field has achieved tremendous development.Applications such as online banking and mobile communications have increased the security requirements in resource-constrained environments.Compared with traditional cryptographic algorithms, elliptic curve cryptosystem(ECC) provides better security standards and more space for optimizing performance parameters.Therefore, an efficient elliptic curve cipher hardware design scheme is proposed.Based on the exis-ting research, the proposed scheme uses the projected coordinate system LD Montgomery ladder algorithm to study the core scalar multiplication operation in ECC, and uses parallel scheduling to reduce delay in the group operation layer.For finite field ope-rations, the bit-parallel multiplication algorithm and improved Euclidean inverse algorithm are adopted.Based on Xilinx Virtex-5 and Virtex-7 FPGA device, the architecture is implemented on the binary domains with lengths of 163, 233 and 283 respectively.The experimental results show that the proposed scheme requires less FPGA resource consumption and faster calculation speed.Compared with other methods, the hardware resource consumption is reduced by 52.9% and the scalar multiplication operation speed is increased by 3.7times, so it is better suitable for the application of resource-constrained devices.

Key words: Binary extension field, Elliptic curve cryptography, Field-programmable gate array, Inversion, Scalar multiplication

中图分类号:

TP309

尤文珠, 葛海波. 二进制域上椭圆曲线密码ECC的高性能FPGA实现[J]. 计算机科学, 2020, 47(8): 127-131. https://doi.org/10.11896/jsjkx.200600112

YOU Wen-zhu, GE Hai-bo. High-performance FPGA Implementation of Elliptic Curve ECC on Binary Domain[J]. Computer Science, 2020, 47(8): 127-131. https://doi.org/10.11896/jsjkx.200600112

参考文献

[1] HOSSAIN M R, HOSSAIN M S.Efficient FPGA implementation of modular arithmetic for elliptic curve cryptography[C]∥2019 International Conference on Electrical, Computer and Communication Engineering(ECCE).IEEE, 2019:7-9.
[2] KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics ofComputation, 1987, 48(177):203-209.
[3] MILLER V S.Use of elliptic curves in cryptography[C]∥Conference on the Theory and Application of Cryptographic Techniques.Springer, Berlin, Heidelberg, 1985:417-426.
[4] RIVEST R L, SHAMIR A, ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the Acm, 1978, 21(2):120-126.
[5] RASHIDI B, SAYEDI S M, FARASHAHI R R.High-speedhardware architecture of scalar multiplication for binary elliptic curve cryptosystems[J].Microelectronics Journal, 2016, 52(jun.):49-65.
[6] YANG Z H, ZHOU P, LIU J, et al.Design and implementation of elliptic curve dot multiplication algorithm based on FPGA[J].Chinese Journal of Scientific Instrument, 2009, 30(7):1546-1551.
[7] SUTTER G D, DESCHAMPS J P, IMANA J L.Efficient ellipticcurve point multiplication using digit-serial binary field operations[J].IEEE Transactions on Industrial Electronics, 2013, 60(1):217-225.
[8] CUI X N, YANG J W, YE H, et al.Optimized design method on elliptic curve cryptography[J].Journal of Xidian University, 2015, 42(1):69-74.
[9] RASHIDI B, SAYEDI S M, FARASHAHI R R.High-speedhardware architecture of scalar multiplication for binary elliptic curve cryptosystems[J].Microelectronics Journal, 2016, 52:49-65.
[10]IMRAN M, SHAFI I, JAFRI A R, et al.Hardware design and implementation of ECC based crypto processor for low-area-applications on FPGA[C]∥International Conference on Open Source Systems & Technologies.IEEE, 2017.
[11]RASHIDI B, FARASHAHI R R, SATEDI S M.High-performance and high-speed implementation of polynomial basis Itoh-Tsujii inversion algorithm over GF(2m)[J].IET Information Security, 2017, 11(2):66-77.
[12]RASHIDI B.Low-cost and fast hardware implementations ofpoint multiplication on binary edwards curves[C]∥Iranian Conference on Electrical Engineering(ICEE).IEEE, 2018:17-22.
[13]DASON I B M, KASTHURI N.Low latency scheduling of point multiplication featuring high speed GF(2m) multiplier suitable for FPGA implementation[C]∥2018 International Conference on Intelligent Computing and Communication for Smart World(I2C2SW).IEEE, 2018:9-13.
[14]GRALE T J, SWARTZLANDER E E.Parallel GF(2n) modular squarers[C]∥2019 IEEE 62nd International Midwest Sympo-sium on Circuits and Systems(MWSCAS).IEEE, 2019:872-875.
[15]LI L, LI S.High-performance pipelined architecture of elliptic curve scalar multiplication over GF(2m)[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2016, 24(4):1223-1232.
[16]IMRAN M, KASHIF M, RASHID M.Hardware design and implementation of scalar multiplication in elliptic curve cryptography(ECC) over GF(2¹⁶³, ) on FPGA[C]∥International Conference on Information & Communication Technologies.IEEE, 2015:1-4.
[17]KHAN Z U A, BENAISSA M.High-speed and low-latency ECC processor imple-mentation over GF(2m) on FPGA[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2017, 25(1):165-176.
[18]LIU S, JU L, CAI X, et al.High performance FPGA implementation of elliptic curve cryptography over binary fields[C]∥IEEE International Conference on Trust.IEEE, 2014:148-155.
[19]LOPEZ J, DAHAB R.Fast multiplication on elliptic curves over GF(2m) without precomputation[M]∥Cryptographic Hardware and Embedded Systems.Heidelberg:Springer, 1999.
[20]MONTGOMERY P L.Speeding the pollard and elliptic curve methods of factorization[J].Mathematics of Computation, 1987, 48(177):243-264.
[21]HARB S, AHMAD M, SWAMY M.High-performance pipelined FPGA implementation of the elliptic curve cryptography over GF(2n)[C]∥International Conference on e-Business and Telecommunications(ICETE).IEEE, 2019:15-24.
[22]SCHROEPPEL R, ORMAN H, OMALLEY S, et al.Fast keyexchange with elliptic curve systems[C]∥International Cryptology Conference.1995:43-56.
[23]ITOH T, TSUJII S.A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases[J].Information & Computation, 1988, 78(3):171-177.
[24]BENSELAMA Z A, BENCHERIF M A, KHORISSI N, et al.Low cost reconfigurable elliptic crypto-hardware[C]∥IEEE/ACS 11th International Conference on Computer Systems and Applications(AICCSA).2014:788-792.
[25]KHAN Z BENAISSA M.Throughput/area-efficient ECC processor using montgomery point multiplication on FPGA[J].IEEE Transactions on Circuits & Systems II Express Briefs, 2015, 62(11):1078-1082.
[26]REBEIRO C, ROY S S, MUKHOPADHYAY D.Pushing the limits of high-speed GF(2m) elliptic curve scalar multiplication on FPGAs[M]∥Pushing the Limits of High-Speed GF(2, m, ) Elliptic Curve Scalar Multiplication on FPGAs.Indiana University Press, 2012.
[27]IMRANI M, RASHID M, JAFRI A R, et al.Throughput/areaoptimised pipelined architecture for elliptic curve crypto processor[J].IET Computers & Digital Techniques, 2019, 5(13):361-368.

相关文章 15

[1]	何璐蓓,厉俊男,杨翔瑞,孙志刚. RESSP:基于FPGA的可重构SDN交换结构 RESSP:An FPGA-based REconfigurable SDN Switching Architecture 计算机科学, 2018, 45(1): 205-210. https://doi.org/10.11896/j.issn.1002-137X.2018.01.036
[2]	路琪,黄芝平,鲁佳琪. 基于深度包检测的防火墙系统设计 System Design of Firewall Based on Deep Packet Inspection 计算机科学, 2017, 44(Z11): 334-337. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.070
[3]	李宜珂,王旃. 基于不同排序方法的快速霍夫曼编码硬件实现 Hardware Implementation of Fast Huffman Coding Based on Different Sorting Methods 计算机科学, 2017, 44(Z11): 476-479. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.101
[4]	李忠. 抗SPA攻击的快速标量乘法 Fast Scalar Multiplication with Resistance Against SPA Attacks 计算机科学, 2014, 41(Z6): 374-376.
[5]	张双悦, 李硕, 王红, 杨士元. FPGA芯片的链结构LUT自测试方法研究 Study on Chain-based BIST Architecture of LUTs in FPGA 计算机科学, 2014, 41(5): 37-40. https://doi.org/10.11896/j.issn.1002-137X.2014.05.008
[6]	李忠,彭代渊. 基于滑动窗口技术的快速标量乘法 Fast Scalar Multiplication Based on Sliding Window Technology 计算机科学, 2012, 39(Z6): 54-56.
[7]	贺毅朝,寇应展,曲文龙. 基于w-NNAF的快速Edwards曲线标量乘法 Fast Scalar Multiplication on Edwards Curves Based on w-NNAF 计算机科学, 2010, 37(11): 70-74.
[8]	唐玉兰，刘战，于宗光，陈建慧. 一种改进的伪布尔可满足性算法用于FPGA布线 New Improved Pseudo-boolean Satisfiability Algorithm for FPGA Routing 计算机科学, 2010, 37(10): 297-301.
[9]	. GF（3^m）椭圆曲线群快速算术运算研究计算机科学, 2009, 36(5): 96-98.
[10]	. 基于双基数的快速标量乘算法计算机科学, 2008, 35(6): 186-189.
[11]	郝艳华范欣欣王育民. 亏格为3的超椭圆曲线除子加法的并行算法计算机科学, 2007, 34(8): 114-119.
[12]	. 基于GDH群可证安全的门限签名方案计算机科学, 2007, 34(10): 110-111.
[13]	张玲邓巍何伟宋炎翼胡又文. 基于FPGA的嵌入式SNMP代理设计与实现计算机科学, 2006, 33(B12): 175-177.
[14]	刘航戴冠中李晖晖陈赞锋. 基于FPGA的IPSec协议安全算法硬件单元设计计算机科学, 2006, 33(2): 97-99.
[15]	张宁牛志华肖国镇. 基于域GF（2^m）上的椭圆曲线中标量乘的快速算法计算机科学, 2006, 33(1): 64-65.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed