高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

高性能Ed25519算法硬件架构设计与实现

于斌 黄海 刘志伟 赵石磊 那宁

于斌, 黄海, 刘志伟, 赵石磊, 那宁. 高性能Ed25519算法硬件架构设计与实现[J]. 电子与信息学报. doi: 10.11999/JEIT200876
引用本文: 于斌, 黄海, 刘志伟, 赵石磊, 那宁. 高性能Ed25519算法硬件架构设计与实现[J]. 电子与信息学报. doi: 10.11999/JEIT200876
Bin YU, Hai HUANG, Zhiwei LIU, Shilei ZHAO, Ning NA. High-performance Hardware Architecture Design and Implementation of Ed25519 Algorithm[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200876
Citation: Bin YU, Hai HUANG, Zhiwei LIU, Shilei ZHAO, Ning NA. High-performance Hardware Architecture Design and Implementation of Ed25519 Algorithm[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT200876

高性能Ed25519算法硬件架构设计与实现

doi: 10.11999/JEIT200876
基金项目: 黑龙江省自然科学基金(YQ2019F010),黑龙江省博士后科研启动基金(LBH-Q18065),中央引导地方科技发展专项(ZY20B11)
详细信息
    作者简介:

    于斌:男,1984年生,讲师,研究方向为密码算法、密码芯片设计和数字集成电路设计等

    黄海:男,1982年生,硕士生导师,研究方向为信息安全、可重构技术、集成电路设计等

    刘志伟:男,1987年生,讲师,研究方向为可重构计算、高速密码算法、并行加密技术、密码芯片的安全设计等

    赵石磊:男,1979年生,硕士生导师,研究方向为信息安全、高速密码算法、密码芯片的安全设计等

    那宁:男,1995年生,博士生,研究方向为信息安全和集成电路设计等

    通讯作者:

    黄海 ic@hrbust.edu.cn

  • 中图分类号: TP309

High-performance Hardware Architecture Design and Implementation of Ed25519 Algorithm

Funds: The Natural Science Foundation of Heilongjiang (YQ2019F010), Heilongjiang Postdoctoral Funds for Scientific Research Initiation (LBH-Q18065), Science and Technology Development Special Project of Central Guide the Local Government of China (ZY20B11)
  • 摘要: 针对签名验签速度难以满足特定应用领域需求的问题,该文设计了一种高性能Ed25519算法的硬件实现架构。采用宽度为2位的窗口法实现标量乘运算,减少了标量乘所需的总周期数;通过优化点加倍点操作步骤,提高了乘法器的硬件使用率;使用低计算复杂度的快速模约简实现模乘,提高了整体运算速度。为了使模L运算可复用标量乘中的快速模约简,该文提出一种基于Barrett约简的模L算法。通过优化解压过程中模幂操作过程,精简了步骤并使其可复用模乘。对所提架构做硬件实现,在TSMC的55 nm CMOS工艺下,面积为746×103等效门,最高频率360 MHz,每秒能够执行公钥生成9.06×104次、签名8.82×104次和验签3.99×104次。
  • 图  1  Ed25519完整结构图

    图  2  模运算单元

    图  3  模约简整体结构

    图  4  b的2252–3次模幂操作步骤图

    表  1  Ed25519公钥生成算法流程

     (1)选择256 bit私钥sk=(sk255, sk254,···, sk1, sk0)2
     (2)对sk做SHA-512运算,即H(sk)= (h511,h510,···,h1,h0)2
     (3)取H(sk)的低256位,并整理为s=(0,1,h253,h252,···,h3,0,0,0)2
     (4)做标量乘A=sB=(x,y),其中x=(x254,x253,···,x1,x0)2,
       y=(y254,y253,···,y1,y0)2
     (5)压缩sB结果,得公钥pk=(x0,y254,y253,···,y1,y0)2
    下载: 导出CSV

    表  2  Ed25519签名算法流程

     (1)取H(sk)的高256位h=(h511,h510,···,h257,h256)2
     (2)做SHA-512运算,r=H(h||M) mod L
     (3)做标量乘R'=rB=(x,y),其中x=(x254,x253,···,x1,x0)2, y=(y254,
       y253,···,y1,y0)2
     (4)压缩rB结果,得R=(x0,y254,y253,···,y1,y0)2
     (5)做SHA-512运算,k=H(R||pk||M) mod L
     (6)计算S= (r+ks) mod L
     (7)返回签名结果(R||S)。
    下载: 导出CSV

    表  3  Ed25519验签算法流程

     (1)解压R为点坐标R'
     (2)解压pk为点坐标A
     (3)做SHA-512运算,k=H(R||pk||M) mod L
     (4)验证SB=R'+kA是否成立,若成立则验签成功。
    下载: 导出CSV

    表  4  宽度为2的窗口法

     输入:255位二进制数k={k254k253···k1k0},点加标志位n,
        n∈{0,1},椭圆曲线上任意点P1, P2
     输出:标量乘Q=kP1+nP2
     (1)预计算2P1,3P1,共2个点坐标;
     (2)若k254=0,则令Q=0,为无穷远点,若k254=1,则令Q=P1
     (3)对于i从126~0,循环计算:
      Q=4Q
      Q=Q+{k2i+1,k2i}P1
     (4)若n=1,则计算:Q=Q+P2 //为适应验签算法;
     (5)返回Q值。
    下载: 导出CSV

    表  5  点加和倍点操作流程[14]

     输入:P(X1,Y1,Z1,T1), Q(X2,Y2,Z2,T2)
     输出:Q(X3,Y3,Z3,T3)=P+Q, Q(X3,Y3,Z3,T3)=2P
     (1) A=(Y1X1)·(Y2X2) A=(X1)2
     (2) B=(Y1+X1)·(Y2+X2) B=(Y1)2
     (3) C=T1·2·d·T2 C=2·(Z1)2
     (4) D=Z1·2·Z2 H=A+B
     (5) E=BA E=H–(X1+Y1)2
     (6) F=DC G=AB
     (7) G=D+C F=C+G
     (8) H=B+A X3=E·F
     (9) X3=E·F Y3=G·H
     (10) Y3=G·H T3=E·H
     (11) T3=E·H Z3=F·G
     (12) Z3=F·G
    下载: 导出CSV

    表  6  倍点操作流程

     输入:点坐标P(X1,Y1,Z1,T1), Q(X2,Y2,Z2,T2)
     输出:Q(X3,Y3,Z3,T3)=2P
     步骤 模乘 模加减
     (1) A=X1·X1
     (2) t1=Z1·Z1
     (3) B=Y1·Y1 t2=X1+Y1
     (4) t2=t2·t2 C=t1+t1, H=A+B, G=AB
     (5) Y2=G·H E=Ht2, F=C+G
     (6) X2=E·F
     (7) Z2=F·G
     (8) T2=E·H
     (9) 等待T2约简
    下载: 导出CSV

    表  7  点加操作流程

     输入:点坐标P(X1,Y1,Z1, T1),Q(X2,Y2,Z2,T2)
     输出:Q(X3,Y3,Z3,T3)=P+Q
     步骤 模乘 模加减
     (1) A1Y1X1, B1Y1+X1
     (2) A2Y2X2, B2Y2+X2
     (3) AA1·A2
     (4) BB1·B2 t1=T1+T1
     (5) t1t1·d t2=Z1+Z1
     (6) Dt2·Z2
     (7) Ct1·T2 EBA, HB+A
     (8) X3E·H FDC, GD+C
     (9) Y3G·H
     (10) Z3F·G
     (11) T3E·H
     (12) 等待Z3约简
    下载: 导出CSV

    表  8  Ed25519快速约简算法

     输入:A=(A254||A253||A252||···||A2||A1||A0)
     输出:Q=A mod p
     (1) T=(A127|| A126|| A125|| ···|| A2|| A1|| A0)
     (2) S1=(A252|| A251|| A250|| ···|| A129|| A128||5′h0)
     (3) S2=(A253|| A252|| A251|| ···|| A129|| A128||3′h0)
     (4) S3=(247′h0|| A254|| A254||4′h0)
     (5) S4=(249′h0|| A253|| A253||2′h0)
     (6) S5=(249′h0|| A254|| 4′h0)
     (7) D1=(A254|| A253|| A252|| ···|| A129|| A128||1′h0)
     (8) D2=(253′h0|| A254)
     (9) D3=(253′h0|| A253)
     (10) Q=(T+S1+S2+S3+S4+S5D1D2D3)mod p
    下载: 导出CSV

    表  9  基于Barrett约简的模L算法

     输入:素数L, 512位数值a, T=[2512/(8L)]
     输出:r=a mod L
     (1)q1=[a/2255T
     (2)q2=[ q1/2257]·(8L);
     (3)r=(a mod 2257)–(q2 mod 2257);
     (4)若果r<0,则r=r+2257
     (5)如果r≥8L,则r=r–11L,否则r=r–3L;//可复用快速模约简
     (6)计算r=r mod L并返回r值。
    下载: 导出CSV

    表  10  Ed25519性能参数

    时钟周期主频面积等效门数
    参数值2.78 ns360 MHz1.433×106746×103
    注1:按工艺库提供的系数1.92从面积折算
    下载: 导出CSV

    表  11  周期及运算次数

    平均周期理论最大
    周期
    平均运算
    次数
    理论最慢
    运算次数
    公钥生成32373975111.2×103次/s90.6×103次/s
    签名33454083107.6×103次/s88.2×103次/s
    验签7488902048.1×103次/s39.9×103次/s
    下载: 导出CSV

    表  12  Ed25519运算速度对比(μs)

    公钥生成签名验签
    本文9.09.320.8
    文献[8]2109.71610.33676.5
    下载: 导出CSV

    表  13  标量乘单元性能对比

    器件硬件开销Slices/LUT/FF/DSP/BRAM周期数Cycles折算值Slices×Cycles×10–6
    本文Zynq-703514759/52512/9342/225/0389557.5
    文献[8]Zynq-7020775/2707/962/15/012026093.2
    文献[9]1Zynq-70002170/8680/3472/0/086348187.4
    文献[9]2Zynq-70002193/8770/3729/0/074783189.3
    文献[11]Zynq-70206161/17939/21077/175/01046564.5
    文献[12]Zynq-70201006/0/0/20/2114980115.7
    文献[13]Zynq-70201029/2783/3592/20/27940081.7
    注1:采用D&A算法;2:采用NAF算法
    下载: 导出CSV
  • [1] RESCORLA E. IETF RFC 8446 The Transport Layer Security (TLS) protocol version 1.3[S]. 2018.
    [2] LANGLEY A, HAMBURG M, and TURNER S. IRTF RFC 7748 Elliptic curves for security[S]. 2016.
    [3] FAZ-HERNÁNDEZ A, LÓPEZ J, and DAHAB R. High-performance implementation of elliptic curve cryptography using vector instructions[J]. ACM Transactions on Mathematical Software, 2019, 45(3): 25.1–25.35. doi:  10.1145/3309759
    [4] ISLAM M M, HOSSAIN M S, HASAN M K, et al. FPGA implementation of high-speed area-efficient processor for elliptic curve point multiplication over prime field[J]. IEEE Access, 2019, 7: 178811–178826. doi:  10.1109/ACCESS.2019.2958491
    [5] 戴紫彬, 易肃汶, 李伟, 等. 椭圆曲线密码处理器的高效并行处理架构研究与设计[J]. 电子与信息学报, 2017, 39(10): 2487–2494. doi:  10.11999/JEIT161380

    DAI Zibin, YI Suwen, LI Wei, et al. Research and design of efficient parallel processing architecture for elliptic curve cryptographic processor[J]. Journal of Electronics &Information Technology, 2017, 39(10): 2487–2494. doi:  10.11999/JEIT161380
    [6] KIM J, PARK J H, KIM D C, et al. Complete addition law for Montgomery curves[C]. The 22nd International Conference on Information Security and Cryptology– ICISC 2019, Seoul, South Korea, 2019: 260–277. doi: 10.1007/978-3-030-40921-0_16.
    [7] SALARIFARD R and BAYAT-SARMADI S. An efficient low-latency point-multiplication over curve25519[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2019, 66(10): 3854–3862. doi:  10.1109/TCSI.2019.2914247
    [8] TURAN F and VERBAUWHEDE I. Compact and flexible FPGA implementation of Ed25519 and X25519[J]. ACM Transactions on Embedded Computing Systems, 2019, 18(3): 24. doi:  10.1145/3312742
    [9] MEHRABI M A and DOCHE C. Low-cost, low-power FPGA implementation of ED25519 and CURVE25519 point multiplication[J]. Information, 2019, 10(9): 285. doi:  10.3390/info10090285
    [10] 魏伟, 陈佳哲, 李丹, 等. 椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究[J]. 电子与信息学报, 2020, 42(8): 1820–1827. doi:  10.11999/JEIT190845

    WEI Wei, CHEN Jiazhe, LI Dan, et al. Research on the bit security of elliptic curve Diffie-Hellman[J]. Journal of Electronics &Information Technology, 2020, 42(8): 1820–1827. doi:  10.11999/JEIT190845
    [11] KOPPERMANN P, DE SANTIS F, HEYSZL J, et al. Low-latency X25519 hardware implementation: Breaking the 100 microseconds barrier[J]. Microprocessors and Microsystems, 2017, 52: 491–497. doi:  10.1016/j.micpro.2017.07.001
    [12] SASDRICH P and GÜNEYSU T. Exploring RFC 7748 for hardware implementation: Curve25519 and Curve448 with side-channel protection[J]. Journal of Hardware and Systems Security, 2018, 2(4): 297–313. doi:  10.1007/s41635-018-0048-z
    [13] SASDRICH P and GÜNEYSU T. Implementing Curve25519 for side-channel--protected elliptic curve cryptography[J]. ACM Transactions on Reconfigurable Technology and Systems, 2015, 9(1): 3. doi:  10.1145/2700834
    [14] JOSEFSSON S and LIUSVAARA I. IRTF RFC 8032 Edwards-curve digital signature algorithm (EdDSA)[S]. 2017.
    [15] VENGALA D V K, KAVITHA D, and KUMAR A P S. Secure data transmission on a distributed cloud server with the help of HMCA and data encryption using optimized CP-ABE-ECC[J]. Cluster Computing, 2020, 23(3): 1683–1696. doi:  10.1007/s10586-020-03114-1
    [16] LI Hui. Pseudo-random scalar multiplication based on group isomorphism[J]. Journal of Information Security and Applications, 2020, 53: 102534. doi:  10.1016/j.jisa.2020.102534
    [17] ZHANG Neng, YANG Bohan, CHEN Chen, et al. Highly efficient architecture of NewHope-NIST on FPGA using low-complexity NTT/INTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020, 2020(2): 49–72. doi:  10.13154/tches.v2020.i2.49-72
    [18] HOSSAIN M S, KONG Yinan, SAEEDI E, et al. High-performance elliptic curve cryptography processor over NIST prime fields[J]. IET Computers & Digital Techniques, 2017, 11(1): 33–42. doi:  10.1049/iet-cdt.2016.0033
    [19] KNEZEVIC M, VERCAUTEREN F, and VERBAUWHEDE I. Faster interleaved modular multiplication based on Barrett and Montgomery reduction methods[J]. IEEE Transactions on Computers, 2010, 59(12): 1715–1721. doi:  10.1109/TC.2010.93
  • [1] 严迎建, 刘敏, 邱钊洋.  一种面向粗粒度可重构阵列的硬件木马检测算法的设计与实现, 电子与信息学报. 2019, 41(5): 1257-1264. doi: 10.11999/JEIT180484
    [2] 张猛, 徐茂智, 胡志, 侯英.  构造小嵌入次数的椭圆曲线参数化族, 电子与信息学报. 2018, 40(1): 35-41. doi: 10.11999/JEIT170261
    [3] 戴紫彬, 易肃汶, 李伟, 南龙梅.  椭圆曲线密码处理器的高效并行处理架构研究与设计, 电子与信息学报. 2017, 39(10): 2487-2494. doi: 10.11999/JEIT161380
    [4] 马英然, 彭延军.  一种融合曲线演化与模糊C均值聚类算法的快速图像分割模型, 电子与信息学报. 2017, 39(6): 1379-1386. doi: 10.11999/JEIT160786
    [5] 禹思敏, 吕金虎, 李澄清.  混沌密码及其在多媒体保密通信中应用的进展, 电子与信息学报. 2016, 38(3): 735-752. doi: 10.11999/JEIT151356
    [6] 陈泽华, 马贺.  基于粒矩阵的多输入多输出真值表快速并行约简算法, 电子与信息学报. 2015, 37(5): 1260-1265. doi: 10.11999/JEIT141129
    [7] 李进, 冯大政, 刘文娟.  快速QAM信号多模盲均衡算法, 电子与信息学报. 2013, 35(2): 273-279. doi: 10.3724/SP.J.1146.2012.00609
    [8] 王一木, 潘赟, 严晓浪.  基于颜色的粒子滤波算法的改进与全硬件实现, 电子与信息学报. 2011, 33(2): 448-454. doi: 10.3724/SP.J.1146.2010.00294
    [9] 李倩, 姬红兵, 郭辉.  拟蒙特卡罗-高斯粒子滤波算法研究及其硬件实现, 电子与信息学报. 2010, 32(7): 1737-1741. doi: 10.3724/SP.J.1146.2009.01002
    [10] 陈光化, 朱景明, 刘名, 曾为民.  双有限域模乘和模逆算法及其硬件实现, 电子与信息学报. 2010, 32(9): 2095-2100. doi: 10.3724/SP.J.1146.2009.01258
    [11] 孟艳, 汪晋宽, 朱俊.  基于子空间的线性约束最小二乘恒模算法, 电子与信息学报. 2009, 31(1): 49-52. doi: 10.3724/SP.J.1146.2007.01191
    [12] 杨威, 黄刘生, 王启研.  基于椭圆曲线的三方比特承诺, 电子与信息学报. 2009, 31(5): 1049-1053. doi: 10.3724/SP.J.1146.2008.00443
    [13] 洪少华, 史治国, 陈抗生.  用于纯方位跟踪的简化粒子滤波算法及其硬件实现, 电子与信息学报. 2009, 31(1): 96-100. doi: 10.3724/SP.J.1146.2007.01166
    [14] 邹谊, 魏文龙, 李斌, 肖金超, 庄镇泉.  多目标量子编码遗传算法, 电子与信息学报. 2007, 29(11): 2688-2692. doi: 10.3724/SP.J.1146.2006.00457
    [15] 郝林, 罗平.  椭圆曲线密码体制中点的数乘的一种快速算法, 电子与信息学报. 2003, 25(2): 275-278.
    [16] 张方国, 王常杰, 王育民.  GF(p)上安全椭圆曲线及其基点的选取, 电子与信息学报. 2002, 24(3): 377-381.
    [17] 刘胜利, 郑东, 王育民.  域GF(2n)上安全椭圆曲线及基点的选取, 电子与信息学报. 2000, 22(5): 824-830.
    [18] 刘胜利, 杨波, 王育民.  基于椭圆曲线密码体制的投票协议, 电子与信息学报. 2000, 22(1): 84-89.
    [19] 韩雁, 姚庆栋.  数字专用集成电路中平方运算的硬件实现, 电子与信息学报. 1996, 18(6): 649-651.
    [20] 潘建强.  数字图象几何变换的B样条算法和硬件实现, 电子与信息学报. 1985, 7(4): 288-296.
  • 加载中
图(4) / 表(13)
计量
  • 文章访问数:  84
  • HTML全文浏览量:  30
  • PDF下载量:  11
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-10-12
  • 修回日期:  2021-01-29
  • 网络出版日期:  2021-03-01

目录

    /

    返回文章
    返回

    官方微信,欢迎关注