Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
高级搜索

留言板

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

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

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

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

张广驰, 顾泽霖, 崔苗. 空地协同通信感知一体化系统的轨迹与资源分配联合优化[J]. 电子与信息学报, 2024, 46(6): 2382-2390. doi: 10.11999/JEIT230716
引用本文: 于斌, 黄海, 刘志伟, 赵石磊, 那宁. 高性能Ed25519算法硬件架构设计与实现[J]. 电子与信息学报, 2021, 43(7): 1821-1827. doi: 10.11999/JEIT200876
ZHANG Guangchi, GU Zelin, CUI Miao. Joint Trajectory and Resource Allocation Optimization for Air-ground Collaborative Integrated Sensing and Communication Systems[J]. Journal of Electronics & Information Technology, 2024, 46(6): 2382-2390. doi: 10.11999/JEIT230716
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 & Information Technology, 2021, 43(7): 1821-1827. doi: 10.11999/JEIT200876

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

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

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

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

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

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

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

    通讯作者:

    黄海 ic@hrbust.edu.cn

  • 中图分类号: TN918; 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), The Science and Technology Development Special Project of Central Guide the Local Government of China (ZY20B11)
  • 摘要: 针对签名验签速度难以满足特定应用领域需求的问题,该文设计了一种高性能Ed25519算法的硬件实现架构。采用宽度为2 bit的窗口法实现标量乘运算,减少了标量乘所需的总周期数;通过优化点加倍点操作步骤,提高了乘法器的硬件使用率;使用低计算复杂度的快速模约简实现模乘,提高了整体运算速度。为了使模L运算可复用标量乘中的快速模约简,该文提出一种基于Barrett约简的模L算法。通过优化解压过程中模幂操作过程,精简了步骤并使其可复用模乘。对所提架构做硬件实现,在TSMC的55 nm CMOS工艺下,面积为746×103等效门,最高频率360 MHz,每秒能够执行公钥生成9.06×104次、签名8.82×104次和验签3.99×104次。
  • 近年来,自动驾驶、远程医疗和增强现实等一系列新兴业务和产业蓬勃发展,这对无线网络的信息处理能力提出了更高要求,促使无线网络逐步发展成为通信网络、感知网络和计算网络的融合体[13]。与单纯的无线通信技术相比,通信感知一体化技术不仅具有原生的通信功能,而且还具有对环境的感知功能。此外,系统中的资源被通信和感知功能共享,如何协调分配系统资源成为性能优化的新挑战[4]

    无人机(Unmanned Aerial Vehicle, UAV)具有按需部署、机动可控等优点[5]。无人机辅助通信感知一体化系统可以充分利用无人机的机动性,动态调整无人机的位置,提高通信用户或者感知目标的信道质量,更好地实现通信和感知性能的优化[610]。文献[6]联合优化无人机位置和发射功率来最大化通信感知一体化系统的网络效用。文献[7]联合设计无人机的飞行轨迹和发射波束赋形,最大化通信用户的通信速率。文献[8]联合优化无人机轨迹、发射波束赋形和感知任务执行时刻,最大化通信用户的通信速率。文献[9]提出一种联合无人机基站和地面基站预测和跟踪用户位置的通信感知一体化方法,并联合优化无人机轨迹以及无人机和用户的关联来最大化用户通信速率和位置克拉美罗下界的加权和。文献[10]考虑概率视距信道模型,在通信和感知服务质量的约束下,联合优化波束赋形和无人机轨迹来提高系统吞吐量。

    然而,在上述工作中,空地信道模型大多采用视距信道模型,并忽略了无人机与回程基站之间的回程链路,具有一定的局限性。具体而言,无人机与地面用户或者感知目标的视距信道模型在城市或山区环境下是不准确的,因为它忽略了随机阴影和小尺度衰落[11]。为了更加准确地建模实际信道,空地信道模型可以采用莱斯信道模型。莱斯信道模型由一个确定性的视距分量和一个由障碍物的反射、散射和衍射引起的随机多路径分量组成,考虑了小尺度衰落等实际因素,对实际信道建模更加准确。同时,当无人机中继回程链路的信道质量较差或者可用带宽受限时,可能会导致用户通信速率下降[12]

    解决回程链路问题的一种有效方法是在系统中考虑空地协同网络。将无人车(Unmanned Ground Vehicle, UGV)基站作为无人机中继的回程基站和能源补给站,二者协同构建空地通信感知协同网络,提升通信感知一体化系统的性能和服务范围。文献[13]提出一种无人车基站和无人机基站集群组成空地合作应急网络帮助灾区快速重建通信。文献[14]提出了一种空地协同车载组网体系结构。然而,在上述空地协同工作中,空地协同的方式集中在通信或者感知单一方面,因此其无法直接应用在通信感知一体化系统上。

    基于上述工作的局限性,本文研究空地协同通信感知一体化系统,由无人车基站和无人机中继集群组成空地协同网络。采用更加精确且与高度角相关的莱斯信道模型建模空地信道。在莱斯信道下,无人机中继与回程基站、用户或者感知目标的高度角越大,传输过程中遇到的障碍物越少[11],所以空地协同网络的通信感知性能不仅与传输距离有关,还受高度角的影响。因此,本文提出面向空地协同通信感知一体化系统的资源分配和轨迹联合优化方法,在保证系统感知性能的同时,提高通信性能。

    图1所示,本文考虑一个由无人车基站和无人机中继集群组成的空地协同通信感知一体化系统,其中,1个单天线无人车基站作为K个无人机中继的回程基站,无人机中继集群接收无人车基站发送的数据,然后将其发送给G个单天线用户,并感知R个目标区域。假设无人车、无人机和用户天线各个方向的增益相同[5,11,15]。在任务开始时,无人车基站搭载并发射无人机集群执行通信感知任务,在任务结束后,无人车回收无人机集群,获取无人机集群对目标区域的回声感知信息。

    图 1  空地协同通信感知一体化系统

    为了减少链路之间的干扰,系统采用频分复用的方式,不同链路的信号带宽相互正交且相等[6],即Bc,k=Bk=Bsum/(2K),k,其中Bsum表示系统总带宽,Bc,k表示无人车与无人机k链路所使用的信号带宽,Bk表示无人机k与关联用户以及目标区域链路所使用的信号带宽。

    将任务周期T离散化为N个时隙,每个时隙的长度为δt=T/N。设无人车初始时刻和时隙n的水平位置分别为qIqc[n],无人机k在时隙n的水平位置和垂直高度分别为qk[n]hk[n],则无人车和无人机集群的水平位置约束和速度约束分别为

    qk[0]=qc[0]=qI,qk[N]=qc[N],k (1)
    (2)
    \left| {{h_k}[n] - {h_k}[n - 1]} \right| \le {\delta _t}V_{k,\max }^z,\forall n,k (3)

    其中,\left\| \cdot \right\|表示欧几里得函数,V_{i,\max }^{xy},i \in \{ {\text{c}},k\} 表示无人车c或者无人机k最大水平行驶速度。V_{k,\max }^z表示无人机k垂直方向最大行驶速度。

    假设用户g、目标区域r和障碍物j的位置已知[9],分别为{{\boldsymbol{u}}_g}, {{\boldsymbol{u}}_r}{{\boldsymbol{u}}_j},则无人车防碰撞约束表示为

    {d_i} + {d_{{\text{c}},\min }} \le \left\| {{{\boldsymbol{q}}_{\text{c}}}[n] - {{\boldsymbol{u}}_i}} \right\|,\forall n,i \in \{ g,r,j\} (4)

    其中, {d_{{\text{c,min}}}} 表示无人车的防碰撞安全距离,{d_i}[n], \forall i \in \{ g,r,j\} 表示用户g,目标区域r或者障碍物j边界与其中心位置的最大距离。

    {h_{k,{\text{I}}}}为无人机k在时隙0和时隙N的垂直高度,最大最小飞行高度分别为{H_{\max }}{H_{\min }},则

    {h_k}[n] = {h_{k,{\text{I}}}},n \in \{ 0,N\} ,\forall k (5)
    {H_{\min }} \le {h_k}[n] \le {H_{\max }},\forall n,k (6)

    {d_{\min }}表示无人机集群的最小安全距离,则无人机集群的防碰撞约束为

    \begin{split} {({d_{\min }})^2}\,& \le {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]} \right\|^2} + {\left| {{h_k}[n] - {h_{k'}}[n]} \right|^2},\\ & \,\forall n,k \ne k' \end{split} (7)

    定义物体集合{{I}} \triangleq \{ {\text{c}},g,r\} 。本文采用莱斯信道模型。在时隙n,无人机k到物体i的信道功率增益

    {h_{k,i}}[n] = \sqrt {{\beta _{k,i}}[n]{f_{k,i}}[n]} ,\forall n,k,i \in {{I}} (8)

    其中,{\beta _{k,i}}[n] = {\beta _0}{({d_{k,i}}[n])^{ - 2}}{\beta _0}表示参考距离为1 m时的信道功率增益,{d_{k,i}}[n]表示无人机k到物体i的距离。{f_{k,i}}[n]表示无人机k到物体i的有效衰落功率。

    因为{f_{k,i}}[n]可以用logistic函数(“S”形状)近似[5,11,15,16],即

    \begin{split} {f_{k,i}}[n]& = \left({C_1} + \frac{{{C_2}}}{{1 + \exp ( - ({B_1} + {B_2}{v_{k,i}}[n]))}}\right),\\ &\, \forall n,k,i \in {{I}} \end{split} (9)

    其中, {B_1} , {B_2}, {C_1}, {C_2}是最大最小莱斯因子决定的常数。{v_{k,i}}[n]表示无人机k与物体i高度角的正弦值 1

    设无人车c和无人机k的峰值发射功率和平均发射功率分别为{P_{{\text{c}},\max }}, {\bar P_{\text{c}}}, {P_{k,\max }}{\bar P_k}。在时隙n,设无人车c向无人机k发射的信号功率为{p_{{\text{c}},k}}[n],无人机k的发射功率为{p_k}[n],则

    \sum\limits_{k = 1}^K {{p_{{\text{c}},k}}[n]} \le {P_{{\text{c}},\max }},{p_k}[n] \le {P_{k,\max }},\forall n (10)
    \frac{1}{N}\sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {{p_{{\text{c}},k}}[n]} } \le {\bar P_{\text{c}}},\frac{1}{N}\sum\limits_{n = 1}^N {{p_k}[n]} \le {\bar P_k},\forall k (11)

    设加性高斯白噪声功率谱密度为{N_0}。在时隙n,无人机k回程链路可实现的通信速率(bit/(s·Hz))为

    {R_{k,{\text{c}}}}[n] = \frac{1}{{2K}}{\log _2}\left(1 + \frac{{{{\left| {{h_{k,{\text{c}}}}[n]} \right|}^2}{p_{{\text{c}},k}}[n]}}{{{B_{{\text{c}},k}}{N_0}}}\right) (12)

    为了减少不同用户之间的干扰,在每个时隙内,无人机与地面用户为1对1的关系[6],即

    \qquad 0 \le \sum\limits_{g = 1}^G {{a_{k,g}}[n]} \le 1,\forall n,k (13)
    \qquad 0 \le \sum\limits_{k = 1}^K {{a_{k,g}}[n]} \le 1,\forall n,g (14)
    \qquad {a_{k,g}}[n]({a_{k,g}}[n] - 1) = 0,\forall n,k,g (15)

    其中,{a_{k,g}}[n]表示无人机k在时隙n与用户g的关联变量。

    在不考虑回程链路的情况下,地面用户g在时隙n的通信速率(bit/(s·Hz))为

    \begin{split} {R_g}[n]& = \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]{{\log }_2}\left(1 + \frac{{{{\left| {{h_{k,g}}[n]} \right|}^2}{p_k}[n]}}{{{B_k}{N_0}}}\right)} ,\\ & \,\forall n,g\\[-1pt] \end{split} (16)

    在任意时隙内,无人机k与关联的地面用户的通信速率之和不大于无人机k回程链路通信速率,即

    {R_g} \le \sum\limits_{k = 1}^K {{a_{k,g}}[n]{R_{k,{\text{c}}}}[n]} ,\forall n,g (17)

    为了减少无人机的能耗,在每个时隙内,无人机k最多感知1个目标区域[17],即

    \qquad 0 \le \sum\limits_{r = 1}^R {{b_{k,r}}[n]} \le 1,\forall n,k (18)
    \qquad {b_{k,r}}[n]({b_{k,r}}[n] - 1) = 0,\forall n,k,r (19)

    其中,{b_{k,r}}[n]表示无人机k在时隙n与目标区域r的关联变量。

    为了提高感知信息的准确性,在整个任务周期内,目标区域至少需要被感知 {f_r} 次,即

    {f_r} \le \sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {{b_{k,r}}[n]} } ,\forall r (20)

    在时隙n,无人机k与目标区域r关联,则无人机k对目标区域r的有效感知功率

    \begin{split} {p_{k,r}}[n] = \,& \frac{{{\beta _0}{p_k}[n]}}{{d_{k,r}^2[n]}}\\ & \cdot\left({C_1} + \frac{{{C_2}}}{{1 + \exp ( - ({B_1} + {B_2}{v_{k,r}}[n]))}}\right),\\ \forall & n,k,r\\[-1pt] \end{split} (21)

    {\varGamma _{\min }}表示区域r的最小有效感知功率阈值。为了保证感知链路的建立同时减少其他非关联区域r'的回声信号的干扰,需要满足最小有效感知功率约束和感知水平距离约束[17],即

    \quad {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]{p_{k,r}}[n],\forall n,k,r (22)
    \quad {b_{k,r}}[n]\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{u}}_r}} \right\| \le {b_{k,r}}[n]{d_{{\text{s}},\min }},\forall n,k,r (23)

    定义优化变量{\boldsymbol{A}} \triangleq \{ {a_{k,g}}[n],\forall n,k,g\} , {\boldsymbol{B}} \triangleq \{ {b_{k,r}}[n],\forall n,k,r\} , {\boldsymbol{P}} \triangleq \{ {p_{{\text{c}},k}}[n],{p_k}[n],\forall n,k\} , {\boldsymbol{Q}} \triangleq \{ {q_{\text{c}}}[n], {q_k}[n],\forall n,k\} {\boldsymbol{H}} \triangleq \{ {h_k}[n],\forall n,k\} 。本文通过联合优化无人机集群对用户的通信关联A、对目标区域的感知关联B、无人车与无人机集群的发射功率P、无人车与无人机集群的水平轨迹Q以及无人机集群的垂直轨迹H,在用户通信、目标感知、回程链路、轨迹等约束下,最大化用户最小平均通信速率,保证通信用户的公平性。相应的问题建模为

    {\mathrm{P}}1: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{\boldsymbol{P}},{\boldsymbol{Q}},{\boldsymbol{H}},\eta } \eta (24a)
    {\mathrm{s.t.}} \;\eta \le \frac{1}{N}\sum\limits_n^N {{R_g}[n]} ,\forall g (24b)
    式(1)-式(7)、 式(10)-式(20)、 式(22)、 式(23) (24c)

    其中,\eta 表示用户最小平均通信速率。上述优化问题是一个包含高度耦合变量且非凸的问题,难以求解。为此,下节将利用块坐标下降法和连续凸优化法对其进行求解。

    为了方便求解,引入松弛变量 {\boldsymbol{S}} \triangleq \{ {s_{k,{\text{c}}}}[n],{s_{k,g}}[n], {s_{k,r}}[n],\forall n,k,g,r\} {{\boldsymbol{R}}_{{g}}} \triangleq \{ {R_g}[n],\forall n,g\} ,即

    {\mathrm{P}}2: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{\boldsymbol{P}},{\boldsymbol{Q}},{\boldsymbol{H}},{\boldsymbol{S}},{{\boldsymbol{R}}_{{g}}},\eta } \eta (25a)
    \begin{split} & {\mathrm{s.t}}.\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {a_{k,g}}[n]\\ & \qquad\qquad\quad \cdot{{\log }_2}\left(1 + \frac{{{{\left| {{h_{k,g}}[n]} \right|}^2}{p_k}[n]}}{{{B_k}{N_0}}}\right) ,\forall n,g \end{split} (25b)
    \left. \begin{aligned} & {s_{k,i}}[n] \le {B_1} + {B_2}{v_{k,i}}[n],\forall n,k,i \in {{I}}\\ & 式(1)-式(7)、 式(10)-式(15)、 式(17)-式(20)、\\ & 式(22)、 式(23)、式(24{\mathrm{b}}) \end{aligned}\right\} (25c)

    对于式(15)和式(19)约束,引入松弛变量{\bar a_{k,g}}[n]{\bar b_{k,r}}[n],等价转化为

    {a_{k,g}}[n](1 - {\bar a_{k,g}}[n]) = 0,{a_{k,g}}[n] = {\bar a_{k,g}}[n],\forall n,k,g (26)
    {b_{k,r}}[n](1 - {\bar b_{k,r}}[n]) = 0,{b_{k,r}}[n] = {\bar b_{k,r}}[n],\forall n,k,r (27)

    {{\bar {\boldsymbol{A}}}} \triangleq \{ {\bar a_{k,g}}[n],\forall n,k,g\} {{\bar {\boldsymbol{B}}}} \triangleq \{ {b_{k,r}}[n],\forall n,k,r\} ,在P, Q, HS给定的情况下,P2近似表示为

    {\mathrm{P}}3: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{{\boldsymbol{R}}_{{g}}},{{\bar {\boldsymbol{A}}}},{{\bar {\boldsymbol{B}}}},\eta } \eta - {\omega _\rho } (28a)
    \begin{split} {\mathrm{s.t.}}\;\;\rho = \,&\sum\limits_n^N \sum\limits_k^K \sum\limits_g^G ({{\left| {{a_{k,g}}[n](1 - {{\bar a}_{k,g}}[n])} \right|}^2}\\ & + {{\left| {{a_{k,g}}[n] - {{\bar a}_{k,g}}[n]} \right|}^2}) \\ & + \sum\limits_n^N \sum\limits_k^K \sum\limits_r^R ({{\left| {{b_{k,r}}[n](1 - {{\bar b}_{k,r}}[n])} \right|}^2} \\ &+ {{\left| {{b_{k,r}}[n] - {{\bar b}_{k,r}}[n]} \right|}^2}) \end{split} (28b)
    {\omega _\rho } = \frac{1}{{2\mu }}\rho (28c)
    \begin{split} & 式(13)、式(14)、式(17)、式(18)、式(20)、式(22)、\\ & 式(23)、式(24{\mathrm{b}})、式(25{\mathrm{b}}) \end{split} (28d)

    其中,\mu 表示惩罚项系数,\rho 表示关联变量惩罚项。当惩罚项\rho 趋近于0,式(15)和式(19)的约束满足[17]

    将P3分解成松弛变量{{\bar {\boldsymbol{A}}}}, {{\bar {\boldsymbol{B}}}}和关联变量{\boldsymbol{A}}, {\boldsymbol{B}}这两个优化子问题,并通过交替优化求解。在{\boldsymbol{A}}, {\boldsymbol{B}}, {{\boldsymbol{R}}_{{g}}}\eta 给定的情况下,令目标函数对{{\bar {\boldsymbol A}}}{{\bar {\boldsymbol B}}}的1阶偏导为0,得到最优的松弛变量形式[17]

    \bar a_{k,g}^{{\text{opt}}}[n] = \frac{{{a_{k,g}}[n] + a_{k,g}^2[n]}}{{1 + a_{k,g}^2[n]}},\forall n,k,g (29)
    \bar b_{k,r}^{{\text{opt}}}[n] = \frac{{{b_{k,r}}[n] + b_{k,r}^2[n]}}{{1 + b_{k,r}^2[n]}},\forall n,k,r (30)

    {{\bar {\boldsymbol A}}}{{\bar {\boldsymbol B}}}给定的情况下,P3可以简化为

    {\mathrm{P}}4: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{{\boldsymbol{R}}_{{g}}},\eta } \eta - {\omega _\rho }\ (31a)
    \begin{split} & {\mathrm{s.t}}. \;式(13)、式(14)、式(17)、式(18)、式(20)、\\ & \quad\;\; 式(22)、式(23)、式(24{\mathrm{b}})、式(26) \end{split} (31b)

    问题P4是一个标准的凸优化问题,可以用内点法[18]求解。

    A,B,Q,HS给定的情况下,P2可以简化为

    \qquad {\mathrm{P}}5: \mathop {\max }\limits_{{\boldsymbol{P}},{{\boldsymbol{R}}_{{g}}},\eta } \eta (32a)
    \begin{split} & {\mathrm{s.t}}. \;式(10)、式(11)、式(17)、式(22)、\\ & \quad\;\; 式(24{\mathrm{b}})、式(25{\mathrm{b}}) \end{split} (32b)

    显然,P5是一个标准的凸优化问题,可以借助凸优化工具箱求解。

    定理1 当2 \le \alpha \le 4, {C_1},{C_2},\gamma ,x,y \gt 0时,{\psi _1}(x,y) \triangleq \left({C_1} + \dfrac{{{C_2}}}{x}\right)\dfrac{\gamma }{{{y^{\alpha /2}}}}是关于xy的凸函数。

    证明 定义{\psi _1}^\prime (x,y) \triangleq \left({C_3} + \dfrac{{{C_4}}}{x}\right)\dfrac{1}{{{y^{\alpha /2}}}} , (2 \le \alpha \le 4) , {C_3} = {C_1}\gamma \ge 0,{C_4} = {C_2}\gamma \ge 0

    {\psi _1}^\prime (x,y)的海森矩阵为{\nabla ^2}{\psi _1}^\prime (x,y),当2 \le \alpha \le 4x,y \gt 0时,对于任意{\boldsymbol{t}} = {[{t_1},{t_2}]^{\text{T}}},有{{\boldsymbol{t}}^{\text{T}}}{\nabla ^2}{\psi _1}^\prime (x,y){\boldsymbol{t}} \ge 0,即{\psi _1}(x,y)是关于x,y \gt 0的凸函数。证毕

    为了方便处理1阶泰勒展开式,定义{X_{k,i}}[n] = 1 + {{\text{e}}^{ - {s_{k,i}}[n]}},\forall n,k,i \in {{I}}, {Y_{k,{\text{c}}}}[n] = {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{\text{c}}}[n]} \right\|^2} + {h_k}{[n]^2},\forall n,k , {Y_{k,i}}[n] = {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{u}}_i}} \right\|^2} + {h_k}{[n]^2}, \forall n, k, i \in \{ g,r\} , {\lambda _{k,{\text{c}}}}[n] = {\beta _0}{p_{{\text{c}},k}}[n]/({B_{{\text{c}},k}}{N_0}), {\lambda _{k,g}}[n] = {\beta _0}\cdot {p_k}[n]/({B_k}{N_0})。设X_{k,i}^l[n] Y_{k,i}^l[n] 分别为{X_{k,i}}[n] {Y_{k,i}}[n] l次迭代的值。由定理1可知,{p_{k,r}}[n]是关于{X_{k,i}}[n] {Y_{k,i}}[n] 的凸函数。将{p_{k,r}}[n]X_{k,i}^l[n] Y_{k,i}^l[n] 处1阶泰勒展开,得到{p_{k,r}}[n]的全局下界p_{k,r}^{{\text{lb}}}[n],即

    \begin{split} {p_{k,r}}[n] \ge\,& \frac{{{\beta _0}{p_k}[n]}}{{Y_{k,r}^l[n]}}({C_1} + \frac{{{C_2}}}{{X_{k,r}^l[n]}}) \\ & + \varphi _{k,r}^l[n]({X_{k,r}}[n] - X_{k,r}^l[n]) + \zeta _{k,r}^l[n]\\ & \cdot({Y_{k,r}}[n] - Y_{k,r}^l[n]) \end{split}\tag{33} (33)
    \left. \begin{aligned} & \varphi _{k,r}^l[n] = - \frac{{{C_1}{\beta _0}{p_k}[n]}}{{X_{k,r}^l{{[n]}^2}Y_{k,r}^l[n]}}\\ & \zeta _{k,r}^l[n] = - \frac{{{\beta _0}{p_k}[n]}}{{Y_{k,r}^l{{[n]}^2}}}\left({C_1} + \frac{{{C_2}}}{{X_{k,r}^l[n]}}\right) \end{aligned}\right\} (34)

    {R_{k,i}}[n]{X_{k,i}}[n] {Y_{k,i}}[n] 的凸函数[11],将{R_{k,i}}[n]X_{k,i}^l[n] Y_{k,i}^l[n] 处1阶泰勒展开,得到R_{k,i}^{{\text{lb}}}[n]

    \begin{split} {R_{k,i}}[n] \ge\,& \frac{1}{{2K}}({\log _2}(1 + \frac{{{\lambda _{k,i}}[n]}}{{Y_{k,i}^l[n]}}\left({C_1} + \frac{{{C_2}}}{{X_{k,i}^l[n]}}\right) \\ & + \xi _{k,i}^l[n]({X_{k,i}}[n] - X_{k,i}^l[n]) + t_{k,i}^l[n]\\ & \cdot({Y_{k,i}}[n] - Y_{k,i}^l[n]))\\[-1pt] \end{split} (35)
    \begin{split} & \xi _{k,i}^l[n] =\\ & - \frac{{({{\log }_2}{\text{e}}){C_2}{\lambda _{k,i}}[n]}}{{X_{k,i}^l[n](X_{k,i}^l[n]Y_{k,i}^l[n] + {\lambda _{k,i}}[n]({C_1}X_{k,i}^l[n] + {C_2}))}} \end{split} (36)
    \begin{split} & t_{k,i}^l[n] =\\ & - \frac{{({{\log }_2}{\text{e}})({C_1}X_{k,i}^l[n] + {C_2}){\lambda _{k,i}}[n]}}{{Y_{k,i}^l[n](X_{k,i}^l[n]Y_{k,i}^l[n] + {\lambda _{k,i}}[n]({C_1}X_{k,i}^l[n] + {C_2}))}} \end{split} (37)

    {v_{k,i}}[n] \triangleq {h_k}[n]/{({Y_{k,i}}[n])^{1/2}},\forall i \in {{I}}{v_{k,i}}[n]{Y_{k,i}}[n]的凸函数[11],将{v_{k,i}}[n] Y_{k,i}^l[n] 处展开,即

    {v_{k,i}}[n] \ge \frac{{{h_k}[n]}}{{{{(Y_{k,i}^l[n])}^{1/2}}}} - \frac{{{h_k}[n]}}{{2{{(Y_{k,i}^l[n])}^{3/2}}}}({Y_{k,i}}[n] - Y_{k,i}^l[n]) (38)

    将式(4)和式(7)分别在{\boldsymbol{q}}_{\mathrm{c}}^l[n]{\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n]处1阶泰勒展开,得

    \begin{split} {d_i} + {d_{{\text{c}},\min }} \le \,& - \left\| {{\boldsymbol{q}}_{\text{c}}^l[n] - {{\boldsymbol{u}}_i}} \right\| + 2{({\boldsymbol{q}}_{\text{c}}^l[n] - {{\boldsymbol{u}}_i})^{\mathrm{T}}}\\ & \cdot({{\boldsymbol{q}}_{\text{c}}}[n] - {{\boldsymbol{u}}_i}),\forall n,i \in \{ g,r,j\} \end{split} (39)
    \begin{split} d_{\min }^2 \le \,& {\left| {{h_k}[n] - {h_{k'}}[n]} \right|^2} - {\left\| {{\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n]} \right\|^2} \\ & + 2{({\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n])^{\mathrm{T}}}({{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]),\forall n,k \ne k' \end{split} (40)

    A, B, PH给定的情况下,P2可以近似表示为

    {\mathrm{P}}6: \mathop {\max }\limits_{{\boldsymbol{Q}},{\boldsymbol{S}},{{\boldsymbol{R}}_{{g}}},\eta } \eta (41a)
    {\mathrm{s.t.}} \;{R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]R_{k,{\text{c}}}^{{\text{lb}}}[n]} ,\forall n,g (41b)
    \quad\;\; {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]p_{k,r}^{{\text{lb}}}[n],\forall n,k,r (41c)
    \quad\;\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]} R_{k,g}^{{\text{lb}}}[n],\forall n,g (41d)
    \quad\;\; {s_{k,i}}[n] \le {B_1} + {B_2}v_{k,i}^{{\text{lb}}}[n],\forall n,k,i \in {{I}} (41e)
    式(1)、 式(2)、 式(23)、 式(24{\mathrm{b}})、 式(39)、 式(40) (41f)

    显然,P6是一个标准的凸优化问题,可以用内点法求解。

    式(7)中,在h_k^l[n] - h_{k'}^l[n]处1阶泰勒展开,得

    \begin{split} d_{\min }^2 &\le {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]} \right\|^2} - {\left| {h_k^l[n] - h_{k'}^l[n]} \right|^2} \\ & \quad + 2{(h_k^l[n] - h_{k'}^l[n])}({h_k}[n] - {h_{k'}}[n]),\\ & \,\forall n,k \ne k' \end{split} (42)

    对于式(17)、式(22)和式(26),与3.3节式(33)和式(34)同理,得到{p_{k,r}}[n]{R_{k,i}}[n]的全局下界\varGamma _{k,r}^{{\mathrm{lb}}}[n]R_{k,i}^{{\mathrm{lb}}}[n]。则在A,B,PQ给定的情况下,P10可以近似表示为

    {\mathrm{P}}7 \mathop {\max }\limits_{{\boldsymbol{H}},{\boldsymbol{S}},{\boldsymbol{R}}_g,\eta } \eta (43a)
    {\mathrm{s.t.}}\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]R_{k,{\text{c}}}^{{\text{lb}}}[n]} \forall n,g, (43b)
    \quad\;\; {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]p_{k,r}^{{\text{lb}}}[n],\forall n,k,r (43c)
    \quad\;\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]} R_{k,g}^{{\text{lb}}}[n],\forall n,g (43d)
    \begin{split} & \quad\;\;式(3)、式(5)、式(6)、式(17)、式(22)、\\ & \quad\;\;式(24{\mathrm{b}})、式(25{\mathrm{b}})、式(25{\mathrm{c}})、式(42) \end{split} (43e)

    其中,式(25c)不等号右边是关于H的凹函数[11],因此P7可以用内点法求解。

    通过交替优化迭代上面各个子问题直至收敛,完整的优化算法如算法1所示。

    表 1  双层迭代算法
     (1) 初始化迭代次数{l_1}=0和{l_2}=0,关联变量{{\boldsymbol{A}}^{{l_1},{l_2}}}{{\boldsymbol{B}}^{{l_1},{l_2}}},功率变量{{\boldsymbol{P}}^{{l_1}}},水平轨迹变量{{\boldsymbol{Q}}^{{l_1}}},垂直轨迹变量{{\boldsymbol{H}}^{{l_1}}},惩罚项系数
     {\mu ^{{l_1},{l_2}}},目标函数{\eta ^{{l_1}}},收敛阈值{\varepsilon _1}>0, {\varepsilon _2}>0,内层循环最大迭代次数{L_2}
     (2) repeat
     (3)   令内层迭代次数{l_2}=0,repeat
     (4)     给定{{{\boldsymbol{A}}^{{l_1},{l_2}}}, {{\boldsymbol{B}}^{{l_1},{l_2}}}, {{\boldsymbol{P}}^{{l_1}}}, {{\boldsymbol{Q}}^{{l_1}}}, {{\boldsymbol{H}}^{{l_1}}}},通过式(29)和式(30)计算{{{{\bar {\boldsymbol A}}}^{{l_1},{l_2} + 1}}, {{{\bar {\boldsymbol B}}}^{{l_1},{l_2} + 1}}}
     (5)     给定{{{{\bar {\boldsymbol A}}}^{{l_1},{l_2} + 1}}, {{{\bar {\boldsymbol B}}}^{{l_1},{l_2} + 1}}, {\mu ^{{l_1},{l_2}}}},通过求解P4得到{{{\boldsymbol{A}}^{{l_1},{l_2} + 1}}, {{\boldsymbol{B}}^{{l_1},{l_2} + 1}}, {\rho ^{{l_1},{l_2} + 1}}}
     (6)     更新惩罚项系数{\mu ^{{l_1},{l_2} + 1}}, {l_2} = {l_2} + 1
     (7)   until{\rho ^{{l_1},{l_2}}} \le {\varepsilon _2} or {l_2} \ge {L_2}
     (8)   更新{{\boldsymbol{A}}^{{l_1} + 1}} = {{\boldsymbol{A}}^{{l_1},{l_2}}}, {{\boldsymbol{B}}^{{l_1} + 1}} = {{\boldsymbol{B}}^{{l_1},{l_2}}},计算\eta _1^{{l_1} + 1}
     (9)   给定{{{\boldsymbol{A}}^{{l_1} + 1}}, {{\boldsymbol{B}}^{{l_1} + 1}}, {{\boldsymbol{Q}}^{{l_1}}}, {{\boldsymbol{H}}^{{l_1}}}},通过求解P5得到{{{\boldsymbol{P}}^{{l_1} + 1}}, \eta _2^{{l_1} + 1}}
     (10)   给定{{{\boldsymbol{A}}^{{l_1} + 1}}, {{\boldsymbol{B}}^{{l_1} + 1}}, {{\boldsymbol{P}}^{{l_1} + 1}}, {{\boldsymbol{H}}^{{l_1}}}},通过求解P6得到{{{\boldsymbol{Q}}^{{l_1} + 1}}, \eta _3^{{l_1} + 1,{\text{lb}}}}
     (11)   给定{{{\boldsymbol{A}}^{{l_1} + 1}}, {{\boldsymbol{B}}^{{l_1} + 1}}, {{\boldsymbol{P}}^{{l_1} + 1}}, {{\boldsymbol{Q}}^{{l_1} + 1}}},通过求解P7得到{{{\boldsymbol{H}}^{{l_1} + 1}}, \eta _4^{{l_1} + 1,{\text{lb}}} }
     (12)   更新{l_1} = {l_1} + 1, {{\boldsymbol{A}}^{{l_1},0}} = {{\boldsymbol{A}}^{{l_1} - 1}}, {{\boldsymbol{B}}^{{l_1},0}} = {{\boldsymbol{B}}^{{l_1} - 1}}, {\mu ^{{l_1},0}},计算{\eta ^{{l_1}}}
     (13) until \dfrac{{{\eta ^{{l_1}}} - {\eta ^{{l_1} - 1}}}}{{{\eta ^{{l_1} - 1}}}} \lt {\varepsilon _1}
    下载: 导出CSV 
    | 显示表格

    算法1的步骤(3)–步骤(12)可得, {\eta ^{{l_1}}}\mathop \le \limits^{\mathrm{a}} \eta _1^{{l_1} + 1}\mathop \le \limits^{\mathrm{b}} \eta _2^{{l_1} + 1}\mathop = \limits^{\mathrm{c}} \eta _2^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{d}} \eta _3^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{e}} \eta _4^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{f}} {\eta ^{{l_1} + 1}} 。其中不等号a表示在算法1的步骤(3)–步骤(7)中,惩罚项趋近于0时,目标值具有非减性;不等号b,d和e分别表示在步骤(9)–步骤(11)中,子问题P5, P6和P7的目标函数max(·)具有非减性。等号c表示在步骤(9)中,1阶泰勒展开式在给定局部点具有相同的值。不等号f表示在步骤(11)中1阶泰勒展开得到的 \eta _4^{{l_1} + 1,{\text{lb}}} {\eta ^{{l_1} + 1}} 的下界。因此算法1每次迭代的目标函数值是非减的,且存在上界,因此算法1是收敛的。假设求解器精度为\varepsilon >0[18]算法1的时间复杂度为O((N(1+G+K+KG+KR))log2(1/\varepsilon ))。

    本节给出仿真结果来验证本文提出方案联合优化算法的性能,并且与以下3种方案作对比:

    方案1 固定通信感知关联和功率方案,优化无人车和无人机集群的轨迹。将用户和目标区域分成K簇。无人车和无人机在纯通信时隙分配相等的发射功率,在感知时隙,无人机保持峰值发射功率。

    方案2 固定无人机集群高度方案,优化无人机集群的通信感知关联、发射功率和水平轨迹以及无人车的发射功率和行进轨迹,即无人机集群保持相同的高度,即{h_k}[n] = {h_{k,{\text{I}}}},\forall n

    方案3 固定无人车基站方案,优化无人机集群的通信感知关联、功率和3维轨迹以及无人车的发射功率。在这个方案中,无人车基站保持静止,即,{{\boldsymbol{q}}_{\text{c}}}[n] = {{\boldsymbol{q}}_{\text{I}}},\forall n

    对比方案1和方案2的优化算法复杂度均为O((N(1+G+K+KG+KR))log2(1/\varepsilon )),方案3优化算法复杂度为O((N(G+max(K+1,R)+KG+KR))log2(1/\varepsilon ))。在仿真中,工作区域的长宽均为1 250 m,无人车初始位置为(625,0,0) m,无人机数量K为3,用户数G为6,用户最大半径0.5 m,目标区域数R为4,目标区域最大半径为1 m,障碍物数J为5,障碍物最大半径为30 m。3架无人机的初始高度分别为80 m, 90 m, 100 m,无人车峰值发射功率0.15 W,平均发射功率0.015 W,无人机峰值发射功率0.12 W,平均发射功率0.024 W。无人车和无人机最大水平速度分别15 m/s和30 m/s。无人机最大垂直速度为20 m/s,最大最小飞行高度分别为300 m和50 m,无人机感知目标区域的最大水平距离为200 m。系统总带宽为1 MHz,任务总周期为160 s,时隙长度为0.5 s,高斯白噪声功率谱密度N0= –169 dBm/Hz,无人车防碰撞距离为20 m,无人机防碰撞距离为10 m,有效感知功率阈值为–95 dBm,任务周期内每个目标区域的感知频数为20次,参考距离1 m的信噪比为-60 dB,莱斯信道参数[11]B1=–4.3221, B2=6.0750, C1=0, C2=1。设算法1{\varepsilon _1}=1e–4, {\varepsilon _2}=1e–5, {L_2}=10。

    图2给出了算法1目标函数和惩罚项的迭代情况。在不同的{\varGamma _{\min }}{f_r}条件下,所提出算法迭代到30次左右,惩罚项趋近于0,且目标函数值收敛,说明在不同参数下,算法1可以达到良好的收敛效果。

    图 2  所提算法中目标函数和惩罚项与迭代次数的关系

    图3是在{\varGamma _{\min }}= –95 dBm和{f_r}=20 次时,算法1得到的无人机中继的通信感知关联情况。可以看出,感知任务较少的无人机会分配通信时隙给感知任务较多的无人机所关联的用户。

    图 3  无人机集群通信感知关联

    图4给出了当{\varGamma _{\min }}= –95 dBm和{f_r}=20 次时,算法1得到的无人车与无人机集群的水平轨迹和3维轨迹。在图4(a)中,无人车依次为无人机提供信道质量较好的回程链路,无人机飞往关联的目标区域执行感知任务,在感知完后,靠近关联的用户和无人车,获得较好的信道质量。从图4(b)中看出,无人车和无人机动态调整位置,改变回程链路、通信链路和感知链路的信道质量,协调通信感知性能之间的权衡。

    图 4  无人车和无人机集群的水平轨迹和3维轨迹

    图5给出了当{f_r}=20 次时几种算法用户最小平均通信速率和有效感知功率阈值的关系。随着有效感知功率阈值的减小,用户最小平均通信速率越来越大,但在–105 dBm以后受限于感知频率等因素,减小有效感知功率阈值,用户最小平均通信速率提升不大。所提优化算法的用户最小平均通信速率均比其他3个对比算法明显提高。因为所提优化算法方案拥有更多的优化自由度,实现通信感知性能之间更好的权衡。

    图 5  用户最小平均通信速率随有效感知功率阈值的变化

    图6给出了当{\varGamma _{\min }}=–95 dBm时几种算法的用户最小平均通信速率和目标区域感知次数的关系。所提优化算法的用户最小平均通信速率均比其他对比方案高。从图5图6可以看出,与其他3种优化方案相比,所提优化算法虽然增加了一定的复杂度(仍是可接受的多项式复杂度),但显著提高了用户最小平均通信速率,从而验证了所提优化算法的有效性和必要性。

    图 6  用户最小平均通信速率随感知频率的变化

    本文提出一种以空地协同的方式辅助通信感知一体化系统的方法,通过优化无人机中继集群对用户的通信关联和目标区域的感知关联、发射功率和飞行轨迹,以及无人车基站的发射功率和行进轨迹,最大化用户最小平均通信速率。基于块坐标下降和连续凸优化法,提出一种双层迭代的算法求解次优解。仿真结果表明,所提优化算法在不同参数下均有良好的收敛性。此外,相比于无人机集群高度固定、通信感知关联和发射功率固定以及回程基站静止这3种基准方案,所提算法可以实现通信感知一体化系统中通信感知任务关联的均衡,并且动态调整空地协同网络的位置和发射功率,使之与通信感知一体化系统的通信感知任务相适应,协调通信感知性能之间的权衡,使得在相同感知性能下,有效提高了用户最小平均通信速率。

  • 图  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 bit,并整理为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 bit 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 bit二进制数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 bit数值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×10390.6×103
    签名33454083107.6×10388.2×103
    验签7488902048.1×10339.9×103
    下载: 导出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]1)Zynq-70002170/8680/3472/0/086348187.4
    文献[9]2)Zynq-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
  • 期刊类型引用(2)

    1. 潘钰,胡航,金虎,雷迎科,冯辉,姜丽,张孟伯. 非授权频段下无人机辅助通信的轨迹与资源分配优化. 电子与信息学报. 2024(11): 4287-4294 . 本站查看
    2. 郭丹. 无线传感器网络簇间通信信息自适应节能优化方法. 长江信息通信. 2024(11): 104-106 . 百度学术

    其他类型引用(0)

  • 加载中
图(4) / 表(13)
计量
  • 文章访问数:  2053
  • HTML全文浏览量:  1077
  • PDF下载量:  149
  • 被引次数: 2
出版历程
  • 收稿日期:  2020-10-12
  • 修回日期:  2021-01-29
  • 网络出版日期:  2021-03-01
  • 刊出日期:  2021-07-10

目录

/

返回文章
返回