1、信息安全研究第10 卷第1期2 0 2 4年1月Journalot information Security ResearchVol.10No.1Jan.2024DOl:10.12379/j.issn.2096-1057.2024.01.03基于NTRU密钥协商协议设计郑鉴学张道法徐松艳宋苏鸣(北京遥测技术研究所北京10 0 0 9 4)()The Design of a Key Agreement Protocol Based on NTRUZheng Jianxue,Zhang Daofa,Xu Songyan,and Song Suming(Beijing Research Instit
2、ute of Telemetry,Beijing 100094)Abstract NTRU is the earliest public-key cryptosystem that reduces the difficulty of thecryptosystem to the lattice-hard problem.The features of NTRU are simple,and the storage spacerequired is small.Therefore,NTRU is more simple and efficient algorithm for establishi
3、ng acryptosystem based on lattice-hard problems.However,there are few relevant references to designNTRU-based key agreement protocols.The existing NTRU-based key agreement protocols do notprotect the keys sufficiently,which is easy to leave convenience for adversary attacks.The proof isnot sufficien
4、t and incomplete.In order to solve this problem,this paper proposes two keyagreement protocols based on NTRU lattice,adding temporary secret information,so that thescheme has strong forward security,and proposes a detailed security proof.The proof is based onthe unforgeability of the session key und
5、er the SVP assumption on the lattice.The security proof isbased on the eCK model.Compared with traditional key agreement schemes such as DH andECDH,this NTRU scheme is based on polynomial rings,and has higher computational efficiency.Its security can be reduced to solving difficult problems on latti
6、ces,and it can resist quantumattacks.Key words lattice;NTRU;key agreement protocol;provable security;eCK model摘要NTRU是最早将密码系统困难性规约到格上困难问题的公钥密码体制.NTRU的特征简洁,密钥生成不复杂,运算速度快并且需要的存储空间小,所以目前基于格上困难问题建立密码体制的算法中,NTRU更加简便高效.然而基于NTRU的密钥协商协议相关研究较少,现存的基于NTRU的密钥协商协议消息传递过程中密钥的保护不充分,易为敌手攻击留下后门,且协议的安全性论证不充分不完备.鉴于此,提出了
7、2 个基于NTRU格上的密钥协商协议,增加临时秘密信息,使方案具有强前向安全性,并且提出了详细的安全证明,在不泄露响应方密钥和要伪造的会话密钥的情况下,该证明是基于格上最短向量计算困难性SVP假设下会话密钥的不可伪造性.该安全证明在收稿日期:2 0 2 3-0 4-2 5引用格式:郑鉴学,张道法,徐松艳,等。基于NTRU密钥协商协议设计J.信息安全研究,2 0 2 4,10(1):12-1912学术论文.ResearchPaperseCK模型下可证明安全的.相较于DH,ECDH等传统的密钥协商方案,NTRU方案是基于多项式环上的,运算效率更高,其安全性可以归约到求解格上的困难问题,可以抵御量子
8、攻击。关键词格;NTRU;密钥协商协议;可证明安全;eCK模型中图法分类号TP309.2如今,网络通信已经成为人们生活中交流通信的重要渠道.然而,在开放的网络通信环境下信息很容易遭到攻击者的攻击.相较于对称密码,公钥密码可以在不安全的信道上传输加密的信息.然而公钥密码的加解密计算复杂,速度比对称密码加解密慢得多,所以加密大量的数据还需使用对称密码.因此公钥密码用于解决在开放网络通信环境中建立双方通信会话密钥的安全性问题.密钥协商(key agreement,K A)就是在不安全的信道下让2 个或多个用户计算共同的会话密钥进行安全通信。1998年,Hoffstein等人提出了NTRU格的概念,设
9、计了一个基于多项式环上的公钥密码体制,通常被称为NTRU加密体制.随后几年,这种签名、加密方案不断出现,但一直没有提出可证明安全的方案,直到2 0 0 8 年,Lyubashevsky等人2 、Gentry等人3先后提出了2 个可证明安全性的格基数字签名方案.因此,基于格基上的公钥加密和数字签名技术取得了巨大的进步4,然而基于格的KA(lattice-based KA,LBK A)协议目前仍然没有很好的发展.由于KA协议在不安全的网络环境中运行,因此,设计出能够抵御各种攻击的认证KA协商协议就显得尤为重要.目前,BR,m BR,C K,e C K,seCK5-81都是密钥协商协议常用的安全模型
10、,基于安全模型的密钥协商方案也在不断地发展9-10。在文献11中,将dA=(f A 十prACB),d B=(f B十prBCA)作为协商双方交互的信息,其中fA,fB分别为Alice和Bob的私钥,属于固定数据.该方案并没有对用户的私钥进行伪随机性保护,这给敌手攻击预留了方便.受此启发,本文对文献11进行改进,提出了2 个基于NTRU格上的密钥协商协议.方案1中,本文在双方协商交互的过程中增加了2 个随机化因子(r1A,r 2 A)和(r1B,r 2 B),使得参与密钥协商过程的发起方和响应方每次生成的会话密钥和协商的信息都不相同,保证了在密钥协商中会话密钥与随机序列的不可区分性.方案2中,
11、本文利用NTRU加密方法,把双方随机选取的多项式(r1A,r 2 A)和(r1B,r 2 B)进行加密,得到dA=(r2A十pr1ACB)和dB=(r 2 B十priBCA)发送给对方,双方收到dA和dB后再对消息用自已的私钥进行解密.该方案密钥协商的过程中双方交互的消息都不包含各自的秘密信息(私钥),安全性完全依赖于NTRU加密方案的安全性,如果NTRU加密方案是安全的,那么该密钥协商方案在基于格上最短向量计算困难性SVP假设下会话密钥也同样具有不可区分性和不可伪造性.1相关知识描述本节将介绍后续需要用到的关于格和NTRU格的一些基本知识,包括格的基本的定义、NTRU密码体制的基本思想及其困
12、难性.1.1NTRU算法描述NTRU加密系统取决于3个整数参数(N,p,q)和4个阶为N-1的系数是整数的多项式集合Cf,Lg,L,Cm.注意p和q不需要是素数,但是本文假设gcd(p,q=1),并且设qp.本文的运算在多项式环R=ZJ/(XN一1)上进行.1个元素fER可以写成多项式或者向量:N-1f=Zfiai=fo,fi,fn-i,i-0取2 个元素f,g ER,将符号定义为环R上的加法运算符号,加法运算定义为fOg=h,hk=fk十gk,其中hER,hk为多项式h的k阶系数.将符号?定义为环R上的乘法运算符号.乘法运算定义为f?g=h,N-1hk-2figk-i+2figN+-=i0其
13、中hk为多项式h的k阶系数.容易验证R在以网址http:/ 1 13i=k+1i+j=k(mod N)Zfigi.信息安全研究第10 卷第1期2 0 2 4年1月Journalotinformatien Security ResearchVol.10No.1Jan.2024上定义的加法运算和乘法运算下构成1个环.进行1次模的乘法运算,这意味着将多项式中的系数约简在模q下。1.2格定义1.NTRU格.令q为大于5的素数,n为2的幂次,多项式f,gER(且f模q是可逆的).令h=g/f(m o d g),则由多项式h和q确定的NTRU格定义为Ah.=(u,)ER u+Xh=0(mod q).由定义
14、1可知NTRU格L,可以通过下面的2NX2N阶矩阵生成:10010 0Lh=0000LO0由生成矩阵可知,NTRU格为满秩格,NTRU格的行列式由素数q和2 N维数唯一确定,即det(L,)=qN,Ah.是Z2N上的一个满秩格,n中的元素通过(,r)Lh的行向量生成,其中rER.25方案设计和安全性分析结合文献12,本文对文献11的工作进行修改,提出2 个密钥协商方案.2.1方案1描述2.1.1大方案的参数选取公开参数(N,p,q),其中选取N=251,=3,q一般为2 的幂次,可以取q=128或者q=256;多项式Q/(N-1)和Z/(N1),其中:Q和Z分别代表有理数环和整数环;商环Z,J
15、/(XN-1)和Z,J(XN-1),其中模q运算的结果在一q/2,q/2 内,而模p运算的结果在 一1,0,1)中.L(a,b)代表多项式环Z/(XN一1)中的特定多项式的全体,这些特定的多项式有a个系数为1,6 个系数为一1,其他系数为0.2.1.2密钥生成阶段Alice分别随机选取fAEL(df,df-1)和gAEL(dg,d g-1),并将fA和gA作为自己的私钥,其141公钥为CA=fgAmodq.Bob分别随机选取fBEL(df,df-1)和gBEL(dg,d g-i),并将fB和gB作为自己的私钥,其公钥为 cB=fzgBmodq.不妨取dj=dg=d,=36,p=3.2.1.3密
16、钥协商阶段1)Bo b 随机选择2 个多项式r1B,r 2 BEL(d r,dr-1),计算dB=fBr2B十pr1BCA,并把dB发给Alice.2)A l i c e 随机选择2 个多项式r1A,r 2 A EL(d,dr-1),计算dA=fAr2A+priACB,并把dA0ho0-hN-1hohN-2:1一h1一h2000000hihN-1ho000发给Bob.同时计算mA=r2AfAdg(mod q)(mod p),SK=H(Key,dA,dB,IDA,IDB),其中Key=r2Ar2BfAdB(modq).3)Bo b 收到dA后,计算mB=r2BfBdA(modq)(modp),S
17、K=H(Key,dA,dB,IDA,IDB),SK作为Alice和Bob的协商密钥.2.1.4密钥协商的正确性q取值为2 56 时,p=3,而d,和dg皆为36,故q2pXmax(drdg).mA=r2AfAdg(modq)(mod p)=r2AfA(fBr2B+priBCA)(mod q)(mod p)=(r2AfAfer2B+pr2Ari1BgA)(modq)(mod p)=(r2AfAfer2B+pr2ArIBgA)(mod p)=fAfBr2Ar2B,同理mB=fAfBr2Ar2B,mA=mB=Key.值得注意的是,由于r2A和r2B分别由用户随机选择,在线路上不传输,故第三方无法获取
18、r2A和r2B,进而第三方也就无法得到mA和mB以及Key,进而提升了密钥协商数据的安全性。2.1.5对文献11的分析文献11提出的NTRU-AKA协议中以下2点值得注意:1)文献11的密钥协商过程中:dA=(fA+prACB),dg=(fB+prBCA),Key=mA=fAd(modq)(mod p)=fBdA(modq)(mod p)=mB=Key.而fA,f B分别为Alice和Bob的私钥,属于固定数据.在双方交互的过程中,Alice和Bob分别发送了dA和dB,而dA和dB这2 个消息中,文献11并没有对用户的私钥进行伪随机性保护,学术论文.ResearchPapers这给敌手攻击预
19、留了方便,因此文献11 只具有弱前向安全性,不能达到完美的前向安全性.本文提出的方案1在密钥协商过程对发送的消息进行改进:dA=(fAr2A+r1AC),dB=(fBr2B+pr1BCA),其中(r1A,r2A),(r1B,r2B)EL(d,dr-1)是 Alice和Bob分别选择的随机多项式.因此在每次的密钥协商中dA和dB中都没有直接使用Alice和Bob的私钥固定值.即使双方的长期私钥泄露也不能破解会话密钥.2)在文献11中并没有对其设计的NTRU密钥协商方案进行详细的安全证明.在2.2 节中本文给出了在eCK模型下的安全方案及安全性证明.2.2方案1的安全性证明2.2.1eCK模型协议
20、参与者:定义协议参与用户为i,定义其身份为IDi其私钥为(fi,g;),公钥为hi.参与者i可以与其他多个用户同时进行密钥协商协议.令II;表示参与者i(发起方)与参与者i(响应方)之间的第次会话.如果会话I,协商了会话密钥SK,那么该会话可以被接受.tran,表示在会话I;中发起方i和响应方j之间传递的信息集,每个成功协商的会话I,都含有会话标识sid.sid定义为此会话中协商双方的身份和消息的串联标识,即sid;=(ID;,IDj,X,X,),其中X;是II,发出的消息,X,是II,收到的消息.敌手模型:A是拥有概率多项式计算能力的预言机,它能够全面监控网络,并且能够实现窃听、延迟、重放和
21、篡改信息,同时还能够执行多项式数量界的询问.包括:EphemeralKeyReveal(I,).A获取II,的临时私钥。SessionKeyReveal(II,).如果II,没有被接受,返回工.否则,输出I ,的会话密钥.StaticKeyReveal(I D,).敌手获取身份为ID;的参与方i的私钥(fi,g;).EstablishParty(I D,).敌手能模拟参与者i注册1个合法用户的身份ID;,并且可以获取其长期私钥.Send(IIj,M).可以通过身份为ID;发送消息M参与会话II j,并且按照协议相关操作返回身份为ID;的参与者所做的响应给敌手A.如果II,收到的第1个信息是入,
22、那么i是发起者;否则i是响应者.在进行安全实验中,必须保证ii.匹配会话:如果会话II ,和II ,拥有相同的会话标识,则称这2 个会话为匹配会话。新鲜会话:身份分别为ID,和ID,的参与者接受会话II;,定义I 为II,的匹配会话.下列条件都不满足,那么I,是新鲜的:如果A查询了II,或II(存在匹配会话)的会话密钥.匹配会话I,存在时,敌手同时询问了StaticKeyReveal(ID,),EphemeralKeyReveal(II,),或者同时询问了EphemeralKeyReveal(Ij),StaticKeyReveal(ID,);匹配会话II 不存在时,敌手同时询问了StaticK
23、eyReveal(ID,),EphemeralKeyReveal(II,),或者询问了 StaticKeyReveal(ID,).Test(II,):该询问测试了敌手是否有能力判断会话密钥和相同长度的随机比特串的不可区分性.某一时刻,A选择1个新鲜会话II,进行唯一的Test查询.挑战者抛1枚公平硬币b=(0,1),如果6=0,返回,真实的会话密钥;如果b=1,返回随机比特串。在敌手完成Test询问之后,敌手还可以反复进行敌手模型中所有的查询.游戏结束时,A对6的猜测值为6 .当I ,是新鲜的并且6=b,则A赢得游戏.A获胜的优势被定义为AduAKE(A)=2PrA 成功11.eCK安全性:1
24、个2 方认证密钥交换协议是安全的,如果它满足如下条件:在按照协议执行的诚实敌手面前,会话I;和I.总是协商相同的会话密钥.对任何概率多项式敌手,AduAKE(A)可忽略不计.2.2.25安全性证明令k表示安全参数,A定义为1个关于k的poly(k)敌手.假设游戏中,A最多能够让n。(N)个不同的诚实参与方进行安全实验(敌手A可进行np(N)次StaticKeyReveal询问),每个参与方最多能参与n(N)个会话(敌手A可进行np(N)次EphemeralKeyReveal 和SessionKeyReveal 询问),A至多进行n次H询问.如果A能够以网址http:/1 15信息安全研究第10
25、 卷第1期2 0 2 4年1月Journalotinformatien Security ResearchVol.10No.1Jan.20241/2十f(k)的概率优势获得安全实验游戏的胜利,其中f(k)是不可忽略的,则A就有不可忽略的概率获得成功.H询问都被看作随机预言机,执行Test查询(成功概率为1/2).在测试会话II.6没有匹配会话时.敌手A输人(Key,da,d b,I D a,I D,)的H询问,其中与测试会话相关的值为(da,d b,I D a,I D,).在此情况下,A自己计算Key.挑战者将利用赢得伪造攻击的敌手A构造求解器CH,以不可忽略的概率成功求解SVP问题.事件1.
26、测试会话II ,没有匹配会话Ib,a,以及A没有执行EphemeralKeyReveal(II,b)查询和StaticKeyReveal(ID,)查询.Setup:CH 按照以下步骤建立系统公钥和用户长期私钥.CH随机选择fELr(df,d,-1)和g;ELg(df,df一1),设置(fi,g;)为第i个剩余参与方i的私钥i十b.Queries:A模拟poly(k)次的除Test查询外的其他询问,并将所有哈希函数看作随机预言机。A 只询问 1 次 Test 查询.对于 A进行的询问,CH对每个询问都有初始空列表,需要进行维护。EstablishParty(ID,):CH 维护形如(ID;,fi
27、,g,c,)的用户列表Ausers,如果ID,不在Ausers列表中,CH为敌手A注册1个参与方i.CH随机选择fiEL(df,df-1)和g;EL(dr,df-1),计算c;=f7g;modq,返回(figi.c;)给敌手A.并更新列表Ausers:StaticKeyReveal(ID,):如果ID,=IDa,C H中止.否则,CH查询Ausers返回(f;,g)给A.EphemeralKeyReveal(I I ,:如果II,=I.b,CH 中止.否则,CH返回存储的临时私钥rj给敌手A.Send(II,M):CH维护元组(IIj,t r a n j,r,)的列表Asend,其中tran;
28、是安全实验I,记录的参与双方交互信息的协议副本,r,是临时私钥.CH执行如下操作:如果M是副本中的第2 个消息,简单接受此会话.否则,考虑以下情形:当I=I,设置r,=上,返回U=fau2a十pulaC6给A,并更新Asend中所在元组.当I,=I.,则随机选择r=(r,r),161dm返回给A,计算foro=de;一pric;并更新Asend中II,所在元组.当I,I6,I I 时,随机选择r;=(rs,rrt),计算d,=f,rr+prric,返回给A,并更新send中I,所在元组.SessionKeyReveal(I I ,):CH 维护元组形如(I,IDini,IDresp,dmi,d
29、resp,SK)的列表AReveal,其中IDini和IDresp分别是会话I,发起者的身份标识和响应者的身份标识.CH执行如下操作:若I,已被接受,返回工;当I;=I.6,中止.当II,II.6,考虑以下几种情形:ID;=I D,时,获取fj,从Asend中获取相对应的(dw.j,dy).计算Key=firfadr,和Key=(dn.j-prr.ic,)dy.如果Key=Key则Key=Key=Key,并且查找AH中是否有形如(IIj,ID,ID;,d j,d y.b,K e y ,)的元组,如果有则返回SK=h 给敌手A,更新ARevel中I,所在的元组;否则(如果没有对应的元组存在,或者
30、KeyKey)随机选取SK.当IDIDi,获取(djdy)和fi,计算Key=Key=firyid.执行1次H查询,获取SK=h.将(Ij,ID i mi,ID r e s p,d m,d r e s p,SK )添加至AReveal并返回SK.H(I;,ID;,ID,d,d,Key)询问:CH维护元组形如(ID;,ID,,d j,d i,K e y ,h )的列表AH.CH执行如下操作:如果(IDi,IDjd,dyi,Key,h)在AH表中则返回h给敌手A;否则考虑AReveal中存在形如(*,ID;,ID j,d,d ,)的元组时,执行如下操作:当ID,=ID,,计算Key=fjrrodr
31、,和Key=(dm,-pr.jcj)dy.b.验证Key=Key是否成立来验证Key是否正确生成.如果成立,从AReveal中获取相应的SK并设置h=SK否则,随机选取h。当ID,ID,计算Key=firy.ads和Key=firridy.验证Key=Key是否成立来验证Key是否正确生成.如果成立,从AReveal中获取相应的SK并设置h=SK;否则,随机选取h。学术论文ResearchPapers将元组(ID;,ID,,d j,d y,K e y ,h )添加至H中,并返回h.Test(II,):如果II;II.6,CH 中止.否则,CH随机选取E(O,1),并返回给A.如果A选择I ,6
32、 为测试会话,以及事件发生并且 CH在游戏中没有退出.如果 A赢得游戏,它肯定已经询问了输人为(Key,U,d b,I D a,I D,)或(Key,db,U,IDb,IDa)的H 询问,其中U是CH输出的消息,d,是敌手选择的消息.因此,为了解决SVP问题,CH从AH中找到相应的项,然后输出 SVP(db,U)=Key.CH解决 SVP问题的优势为 PrCH 成功pi(k)/non,(N)n(N),其中pi(k)为事件1发生并且敌手A成功伪造会话密钥的概率,即敌手A的优势.1/no为n。次H询问发生碰撞的概率,1/ng(N)np(N)是在询问ng(N)np(N)次SessionKeyReve
33、al询问后成功伪造会话密钥概率,1/n,(N)为n。(N)次StaticKeyReveal询问后成功伪造ID,的长期私钥的概率.因此如果敌手的优势pi(k)是不可忽略的,则 CH解决 SVP问题的优势也是不可忽略的.这与SVP假设矛盾.事件2.测试会话II,拥有匹配会话II b.a,即II,和IIb。的临时私钥是由挑战者产生的.Setup:与事件1的询问类似.Queries:C H 参照事件1的实验回答除SessionKeyReveal以外的查询.关于SessionKeyReveal查询,CH回答如下:SessionKeyReveal(II,).CH 执行如下操作:如果,已被接受,返回工;否则
34、,当 I ,=I ,或者I ,=I b,a,中止.当I,Ia.6,I ;I b,a,参照事件1的实验回答剩余情形.分析:敌手A选择I ,作为测试会话,并且IIb.a为I,的匹配会话,以及事件发生并且CH在回答敌手的询问中没有退出.如果A能赢得游戏,那么它一定执行了输人为(Key,U,db,IDa,ID,)或(Key,db,U,IDb,IDa)的H查询,其中U和ds=for2十pruca(f 未知)是CH输出的消息.因此,为了解决SVP问题,CH从AH中找到相应的项,然后输出 SVP(db,U)=Key.CH解决SVP问题的优势为PrCH成功p2(k)/non(N)np(N),其中p2(k)是事
35、件2 发生并且敌手A成功伪造会话密钥的概率即为敌手A成功的优势.1/no为n。次H询问发生碰撞的概率,1/n。(N)n p(N)为在询问n。(N)n p(N)次SessionKeyReveal询问后成功伪造会话密钥概率,1/ng(N)为在n。(N)次StaticKeyReveal询问后成功伪造ID,的长期私钥的概率,1/np(N))为在针对IDa的SessionKeyReveal 询问中,成功伪造出匹配会话的密钥.因此如果p2(k)是不可忽略的,则CH的优势也是不可忽略的.这与 SVP假设矛盾.2.2.3安全性分析已知密钥安全:如果之前会话密钥泄露被敌手获取,他利用之前的会话密钥仍然不能解密本
36、次会话密钥的任何信息.安全性实验中通过EphemeralKeyReveal查询,模仿敌手的已知密钥攻击.抗基本的假冒攻击:如果敌手没有任何关于用户A的长期密钥的信息,敌手将无法冒充A与其他参与者进行通信.用户A公钥cA=fgAmodq,与其长期私钥fa和gA息息相关,如果敌手没有用户A的长期私钥就无法正确计算密钥协商值.抗密钥泄露模仿攻击:如果敌手获取了用户A的长期私钥,敌手不能冒充A以外的用户与其他参与方进行通信.用户的公钥与其长期私钥息息相关,使得公钥和私钥一一对应,不能冒充。前向安全性:1个或多个参与方长期私钥的泄露不影响之前建立的会话密钥的安全性.协商的会话密钥由双方的长期私钥和每次会
37、话的临时密钥共同生成,即使双方长期私钥泄露也不能破解会话密钥,因此方案有完美前向安全性.抗临时秘密密钥泄露:参与方临时私钥泄露并不影响利用此临时私钥进行会话的会话密钥的安全性.在安全证明实验中,利用EphemeralKeyReveal查询,模拟敌手获取参与方临时私钥的能力.抗临时中间结果泄露:临时中间结果(即临时共享秘密值)的泄露不会影响该会话密钥的安全性(在不知道任何参与方长期私钥的情况下).在安全证明实验中,Send查询模拟了敌手可以截获密钥协商双方交互的信息。2.3方案2 描述方案2 的密钥系统建立和密钥生成与本文的方案1类似.网址 http:/1 17信息安全研究第10 卷第1期2 0
38、 2 4年1月Journalotinformatien Security ResearchVol.10No.1Jan.20242.3.1密钥协商阶段1)Bob随机选择2 个多项式r1B,r 2 BEL(d r,d,一1),计算dB=(r 2 B十pr1BCA),并把d发给Alice.2)A l i c e 随机选择2 个多项式r1A,r 2 A EL(d,d,一1),计算dA=(r2A+priACB),并把dA发给Bob.同时计算m1A=fAdB(m o d q)(mod p),m2A=fpAmiA(mod q)(mod p),SK=H(r2A,r2B,IDA,IDB).3)Bob收到dA后,
39、计算m1B=fBdA(mod q)(mod p),m2B=fBm1(mod q)(mod p),同时,计算 SK=H(r2A,r2B,IDA,IDB).SK作为Alice和Bob的协商密钥.2.3.2宅密钥协商的正确性q取值为2 56 时,p=3,而d,和dg皆为36,故q2pmax(df,dg).miA=fAdb(mod q)(mod p)=fA(r2B+pr1BCA)(mod q)(mod p)=(fAr2B+pr1BgA)(mod q)(mod p)=(fAr2B+pr1BgA)(mod p).故有m2A=fAm1A(modp)=r2B.同理,m2B=fBm1B(modp)=r2A.进而
40、密钥协商数据SK可以在Alice和Bob之间保持一致.分析:方案2 的安全性证明和分析与方案1类似.由于r2A和r2B分别由用户随机选择,在线路上不传输,故第三方无法获取r2A和r2B,进而第三方也就无法得到mA和mB以及Key,进而提升了密钥协商数据的安全性。方案2 密钥协商的过程中双方交互的消息都性能文献12 困难问题假设CDH计算代价5TE安全模型eCKPFS是基于NTRU密码学的方案1和方案2 与文献12 相比计算耗时少、效率高.文献13是基于BR安全模型设计的,没有分析临时私钥泄露后对方案的安全影响.文献11只能满足弱完美的前向181不包含各自的秘密信息(私钥),安全性完全依赖于NT
41、RU加密方案的安全性,如果NTRU加密方案是安全的,那么该密钥协商方案也是基于格上最短向量计算困难性假设(SVP)下会话密钥也同样具有不可区分性和不可伪造性.与文献11相比,减少了长期私钥泄露的风险,提高了安全性。SK也可按如下方式计算:SK=H(r2A+r2B,IDA+IDB),这样可以让Alice和Bob处于平等地位.3与其他方案的对比分析本文的2 个方案是基于NTRU密码学构建的,相较于DH,ECD H 等传统的密钥协商方案,NTRU方案基于多项式环上的运算效率更高,其安全性可以归约到求解格上的困难问题,可以抵御量子攻击。将本文方案与其他方案进行比较.首先比较方案的计算代价,其中Te表示
42、椭圆曲线密码学加解密的计算耗时,TNE,T ND,T NM 分别表示NTRU密码学加密、解密和多项式模运算的计算耗时.因为在NTRU加解密算法中多项式系数仅为(一1,0,1,分析文献13-14得到的NTRU加解密运算时间与分析文献12 得到椭圆曲线加解密运算时间相比较,TET NE,T ND,T NM.NT RU 密码运算效率和计算耗时远远优于椭圆曲线密码运算.其次,本文还分析方案是否具有完美的前向安全性(perfect forward security,PFS)和方案使用的安全模型,比较了各方案的安全性.比较的结果如表1所示:表1方案比较文献11文献13SVPSVPTNE+TND+TNMTN
43、E+TND+TNMeCK(安全证明不详细)BR不是是安全性,如果临时私钥泄露还会降低用户长期密钥的安全性.本文基于更强安全性的eCK模型对文献11进行改进,本文方案1在信息交互中,对用户的私钥进行伪随机性保护,使得方案具有完方案1(本文)SVPTNE+TND+2TNMeCK是方案2(本文)SVPTNE+TND+TNMeCK是学术论文ResearchPapers美的前向安全性,虽然计算耗时增加,但是安全性更强;本文方案2 对方案1进行了改进,提高了计算效率,计算耗时与文献11相当.4 结语本文对文献11的认证密钥协商协议方案进行了改进,提出了一种基于NTRU格的密钥协商协议.在随机预言机模型下给
44、出了详细的游戏模型,并证明了该方案在eCK模型中是可证明安全的.而现阶段,基于LWE和RLWE的加密方案15得到飞速发展,如何在安全目标不变的情况下找到计算量更小的LWE和RLWE的密钥协商协议是本文下一步的重点研究方向.参考文献1 Hoffstein J,Pipher J,Silverman J H.NTRU:A ring-basedpublic key cryptosystem G/LNCS 1423:AlgorithmicNumber Theory.Berlin:Springer,1998:206-2882 Lyubashevsky V,Micciancio D.Asymptotical
45、ly efficientlattice-based digital signatures C/Proc of TCC 2008.Berlin:Springer,2008:37-543 Gentry C,Peikert C,Vaikuntanathan V.Trapdoors forhard lattices and new cryptographic constructions C/Proc of the fortieth Annual ACM Symp on Theory ofComputing.NewYork:ACM,2008:197-2064胡予濮。一个新型的NTRU类数字签名方案JJ.
46、计算机学报,2 0 0 8,30(9):16 6 1-16 6 651Bellare M,Rogaway P.Entity authentication and keydistribution C/Proc of the 13th Annual Int CryptologyConf.Berlin:Springer,1993:232-2496 Canetti R,Krawczyk H.Analysis of key-exchangeprotocols and their use for building secure channels C IlProc of EUROCRYPT 2001.Ber
47、lin:Springer,2001:453-4747 LaMacchia B,Lauter K,Mityagin A.Stronger security ofauthenticated key exchange CJ/Proc of the lst Int Confon Provable Security.Berlin:Springer,2007:1-168 Sarr A,Elbaz-Vincent P,Bajard J.A new security modelfor authenticated key agreement C/Proc of Int Conf onSecurity and C
48、ryptography for Networks.Berlin:Springer,2010:219-2349 Liu Xiangyu,Liu Shengli,Gu Dawu.Two-pass authen-ticated key exchange with explicit authentication and tightsecurity CJ/Proc of ASIACRYPT 2020.Berlin:Springer,2020:785-8141oXiao Yuting,Zhang Rui,Ma Hui.Tightly secure two-passauthenticated key exc
49、hange protocol in the CK model Cl/Proc of the Cryptographers Track at the RSA Conf2020.Berlin:Springer,2020:171-19811李子臣,张亚泽,张峰娟.基于NTRU新型认证密钥协商协议的设计.计算机应用研究,2 0 18,35(2):532-535,54112孙海燕。认证密钥协商协议及其应用D.北京:北京邮电大学,2 0 1413王龙安.基于格的匿名认证和密钥协商方案研究D.重庆:重庆邮电大学,2 0 2 014倪亮,王念平,谷威力,等基于格的抗量子认证密钥协商协议研究综述J.计算机科学,2 0 2 0,47(9):2 9 9-30 915韩新光.基于LWE问题认证密钥协商协议的研究与设计D.西安:西安电子科技大学,2 0 2 0郑鉴学硕士研究生.主要研究方向为密码学、信息安全,张道法硕士,研究员.主要研究方向为密码学、信息安全徐松艳硕士,研究员.主要研究方向为安全体系设计宋苏鸣硕士,工程师.主要研究方向为密码产品设计.S网址http:/119