(19)中华人民共和国国家知识产权局

(12)发明专利申请

(10)【申请公布号】CN110519219A
(43)【申请公布日】20191129

(21)【申请号】201910610724.0
(22)【申请日】20190708
(71)【申请人】 中国科学院信息工程研究所 ; 【地址】 100093 北京市海淀区闵庄路甲89号 ;
(72)【发明人】 杨颖珊 ; 顾小卓 ; 王斌 ;
(74)【专利代理机构】北京君尚知识产权代理有限公司 11200【代理人】司立彬 ;
(51)【Int.CI.】 H04L 29/06 (2006.01) ; H04L 9/32 (2006.01) ; H04L 9/08 (2006.01) ;

(54)【发明名称】一种基于格的口令认证密钥交换方法及系统
(57)【摘要】本发明公开了一种基于格的口令认证密钥交换方法及系统。本发明通过使用错误协调机制AKC,当两个参与方交换完信息seed,yC和yS,并根据这些信息分别计算出两个近似的值σC和σS时,可以从中协调出相同的协调值,用于后续的验证和会话密钥的派生。AKC生成的信号值独立于协调值,且协调值均匀分布,即使敌手获取到信号值,也无法从中推断出协调值的信息,保证了方案的安全性。本发明大大提高了服务器的响应效率,使方案能更适用于大量客户端同时连接服务器的高并发情况。

【权利要求书】


1.一种基于格的口令认证密钥交换方法,其步骤包括:

1)客户端C随机选取种子seed并生成公共参数a,然后从环Rq上的中心二项分布中选取秘密sC和错误eC,计算yC=asC+eC,γ=H1(pwC),m=yC+γ,然后将<Cid,m,seed>发送给服务器S;其中pwC为客户端C的口令;

2)服务器S接收到客户端C发送的消息<Cid,m,seed>后,首先检查m,如果不在环Rq上,则协议终止,否则根据种子seed生成公共参数a,并根据环Rq上的中心二项分布选取秘密sS和错误eS、eσ;然后计算yS=asS+eS、yC=m+γ′、σS=yCsS+eσ,并对σS进行协调,得到协调值kσ和信号值v;然后计算验证值k=H2(Cid,Sid,m,yS,kσ,γ′)和验证值k″=H3(Cid,Sid,m,yS,kσ,γ′),将<yS,v,k>发送给客户端C;其中,环Rq为整系数多项式环,γ′为服务器S持有的客户端C的口令哈希值;对于l∈{2,3,4},哈希函数Hl:{0,1}*→{0,1}λ,λ表示最终共享的会话密钥的比特长度,H2和H3用于验证,H4用于密钥派生,Cid表示客户端标识;

3)客户端C接收到消息<yS,v,k>后,首先检查yS,如果不在环Rq上,则协议终止,否则计算σC=ySsC,调用协调函数Rec(σC,v),得到协调值然后计算γ′=-γ,将H2(Cid,Sid,m,yS,kσ,γ′)与k进行比较,若不相同则协议终止,否则计算k′=H3(Cid,Sid,m,yS,k′σ,γ′),得到最终的会话密钥skC=H4(Cid,Sid,m,yS,k′σ,γ′),并将k′发送给服务器S;其中,2≤t,g≤q和Sid为服务器S的标识,g、q、d、t为正整数;

4)服务器S验证k′是否等于k″,若相等,则计算得到最终的会话密钥skS=H4(Cid,Sid,m,yS,kσ,γ′)。

2.如权利要求1所述的方法,其特征在于,步骤1)中,对σS进行协调的方法为:从中随机选取kσ,计算得到协调值kσ和信号值v。

3.如权利要求1所述的方法,其特征在于,|σC-σS|q=|eSsC-eCsS-eσ|q≤d,(2d+1)t<q(1-t/g)。

4.如权利要求1所述的方法,其特征在于,步骤1)中,使用伪随机生成器Gen和种子seed生成公共参数a;如果Gen的输出值a大于或等于5q,则重新生成a,否则将当前生成的a循环减去q,直到更新后的a值小于或等于q,将最终得到的结果作为公共参数a。

5.如权利要求1所述的方法,其特征在于,通过计算得到中心二项分布;其中xi和xi′是均匀独立的比特。

6.一种基于格的口令认证密钥交换系统,其特征在于,包括服务器和若干客户端;其中,

服务器S,用于接收到客户端C发送的消息<Cid,m,seed>并检查m,如果m不在环Rq上,则协议终止,否则根据种子seed生成公共参数a,并根据环Rq上的中心二项分布选取秘密sS和错误eS、eσ;然后计算yS=asS+eS、yC=m+γ′、σS=yCsS+eσ,并对σS进行协调,得到协调值kσ和信号值v;然后然后计算验证值k=H2(Cid,Sid,m,yS,kσ,γ′)和验证值k″=H3(Cid,Sid,m,yS,kσ,γ′),将<yS,v,k>发送给客户端C;以及接收客户端发送的k′并验证k′是否等于k″,若相等,则计算得到最终的会话密钥skS=H4(Cid,Sid,m,yS,kσ,γ′);

客户端C,用于随机选取种子seed并生成公共参数a,然后从环Rq上的中心二项分布中选取秘密sC和错误eC,计算yC=asC+eC,γ=H1(pwC),m=yC+γ,然后将<Cid,m,seed>发送给服务器S;以及接收到消息<yS,v,k>后检查yS是否在环Rq上,如果不在环Rq上,则协议终止,否则计算σC=ySsC,调用协调函数Rec(σC,v),得到协调值然后计算γ′=-γ,将H2(Cid,Sid,m,yS,kσ,γ′)与k进行比较,若不相同则协议终止,否则计算k′=H3(Cid,Sid,m,yS,k′σ,γ′),得到最终的会话密钥skC=H4(Cid,Sid,m,yS,k′σ,γ′),并将k′发送给服务器S;

其中,pwC为客户端C的口令,环Rq为整系数多项式环,γ′为服务器S持有的客户端C的口令哈希值;对于l∈{2,3,4},哈希函数Hl:{0,1}*→{0,1}λ,λ表示最终共享的会话密钥的比特长度,H2和H3用于验证,H4用于密钥派生;2≤t,g≤q和Cid表示客户端标识,g、q、d、t为正整数。

7.如权利要求6所述的系统,其特征在于,服务器S从中随机选取kσ,计算得到协调值kσ和信号值v。

8.如权利要求6所述的系统,其特征在于,|σC-σS|q=|eSsC-eCsS-eσ|q≤d,(2d+1)t<q(1-t/g)。

9.如权利要求6所述的系统,其特征在于,服务器S使用伪随机生成器Gen和种子seed生成公共参数a;如果Gen的输出值a大于或等于5q,则重新生成a,否则将当前生成的a循环减去q,直到更新后的a值小于或等于q,将最终得到的结果作为公共参数a。

10.如权利要求6所述的系统,其特征在于,通过计算得到中心二项分布;其中xi和xi′是均匀独立的比特。

【说明书】


一种基于格的口令认证密钥交换方法及系统

【0001】技术领域

【0002】本发明属于密码技术领域,涉及一种基于格的口令认证密钥交换方法及系统。

【0003】背景技术

【0004】由于大部分公钥密码算法都比对称密码算法速度慢,因此密钥交换仍然是保密通信过程中的重要问题。同时,在通信过程中需要使用认证来防止假冒、篡改、否认等攻击。将认证与密钥交换结合在一起,就产生了认证密钥交换协议,先对通信方的身份进行认证,在成功认证的基础上,为下一步的安全通信生成所使用的会话密钥。

【0005】口令认证密钥交换是指协议的参与方通过共享一个低熵、易于记忆的口令,来建立一个共同的会话密钥,以实现在不安全的信道上进行安全保密通信。口令作为协议参与方的长期密钥,在没有泄露或被窃取的情况下,用于双方的相互认证,以及会话密钥的建立。由于在身份验证过程中使用低熵口令,口令认证密钥交换避免了使用额外的设备和公钥基础设施,不需要与受信任的第三方通信,而是基于服务器和客户端之间的直接信任,认证过程更加灵活简单。这是一类非常实用的密钥交换协议,有着广阔的应用前景。

【0006】随着量子计算机的发展,许多密码原语可能受到量子敌手的威胁。这使得能够抵抗量子计算机攻击的密码协议成为研究热点,称为后量子密码。格是构建后量子密码系统的最常用数学技巧之一。相较于其他的困难性假设,理想格上的Ring-LWE问题更加通用和高效。定义整系数多项式环其中n表示多项式的维度,取值为2的幂,q为正整数,令χ为Rq上的分布,从Rq中随机选取a,根据分布χ选取秘密s和错误e,Ring-LWE问题的一个实例为(a,b=as+e)∈Rq×Rq。

【0007】Ring-LWE问题引入了错误项,通信双方只能计算得到近似相等的值,因此对错误的处理成为基于格的密码方案需要解决的重要问题。其中一种方式就是使用错误协调机制,思想类似于模糊提取器,能够从近似相等的值中提取出相同的协调值。而非对称密钥共识AKC就是一种错误协调机制,其包含两个函数(k1,v)←Con(σ1,params)和k2←Rec(σ2,v,params),其中params=(q,t,g,d,aux)表示相关参数,(q,t,g,d)都是正整数且满足2≤t,g≤q和aux是由(q,t,g,d)确定的辅助参数,可以置为空,是辅助协调的信号值,是协调值,当|σ1-σ2|q≤d时,k1=k2。如果AKC的参数满足(2d+1)t<q(1-t/g),则AKC是正确且安全的,并且v独立于k1。其具体过程如下,通过将Con和Rec函数分别应用于多项式的每个系数,可以将它们扩展到多项式上:

【0008】Con(σ1,params):输入σ1和params,从中随机选取k1,计算输出v。

【0009】Rec(σ2,v,params):输入σ2和params,计算输出k2。

【0010】目前基于格的口令认证密钥交换协议相对较少,且大多是基于CRS,为了达到在标准模型下的安全性,往往需要复杂的密码组件,效率不高。而基于ROM的方法,会使协议设计更加简单高效,但已有的构造由于对错误协调机制的分析不够紧致,造成了性能和安全性的损失。另外,当大量客户端同时连接服务器,存在高并发时,服务器的负载较大,现有的后量子口令认证密钥交换不够高效,不足以应用到这种场景。

【0011】发明内容

【0012】针对现有技术中存在的技术问题,本发明的目的在于提供一种基于格的口令认证密钥交换方法及系统,以使得通信参与方能够在不安全的信道上协商出共同的会话密钥,并通过低熵的口令进行相互认证;该密钥将在之后的对称密码中使用,从而建立安全的通信信道。

【0013】首先,为了在客户端-服务器场景中提高口令认证密钥交换的效率和实用性,本发明提出了一种高效的口令认证密钥交换方法,并对安全性和性能进行综合考虑,给出了具体的参数选择,进一步提高了协议的安全强度,同时减少了传输的消息大小。该方法没有使用CRS进行构造,规避了CRS构造中由于使用复杂的密码组件所带来的低效,方法更加简单和高效。在认证过程中,客户端和服务端分别持有低熵口令和口令的哈希值,当二者匹配时,可以计算出相同的验证值,双方将认证成功,并能得到一致的会话密钥,进行后续保密通信。

【0014】本发明的技术方案为:

【0015】一种基于格的口令认证密钥交换方法,其步骤包括:

【0016】1)客户端C随机选取种子seed并生成公共参数a,然后从环Rq上的中心二项分布中选取秘密sC和错误eC,计算yC=asC+eC,γ=H1(pwC),m=yC+γ,然后将<Cid,m,seed>发送给服务器S;其中pwC为客户端C的口令;

【0017】2)服务器S接收到客户端C发送的消息<Cid,m,seed>后,首先检查m,如果不在环Rq上,则协议终止,否则根据种子seed生成公共参数a,并根据环Rq上的中心二项分布选取秘密sS和错误eS、eσ;然后计算yS=asS+eS、yC=m+γ′、σS=yCsS+eσ,并对σS进行协调,得到协调值kσ和信号值v;然后计算验证值k=H2(Cid,Sid,m,yS,kσ,γ′)和验证值k″=H3(Cid,Sid,m,yS,kσ,γ′),将<yS,v,k>发送给客户端C;其中,环Rq为整系数多项式环,γ′为服务器S持有的客户端C的口令哈希值;对于l∈{2,3,4},哈希函数Hl:{0,1}*→{0,1}λ,λ表示最终共享的会话密钥的比特长度,H2和H3用于验证,H4用于密钥派生,Cid表示客户端标识;

【0018】3)客户端C接收到消息<yS,v,k>后,首先检查yS,如果不在环Rq上,则协议终止,否则计算σC=ySsC,调用协调函数Rec(σC,v),得到协调值k′σ=「t(v/g-σ2/q)modt」;然后计算γ′=-γ,将H2(Cid,Sid,m,yS,kσ,γ′)与k进行比较,若不相同则协议终止,否则计算k′=H3(Cid,Sid,m,yS,k′σ,γ′),得到最终的会话密钥skC=H4(Cid,Sid,m,yS,k′σ,γ′),并将k′发送给服务器S;其中,2≤t,g≤q和Sid为服务器S的标识,g、q、d、t为正整数;

【0019】4)服务器S验证k′是否等于k″,若相等,则计算得到最终的会话密钥skS=H4(Cid,Sid,m,yS,kσ,γ′)。

【0020】一种基于格的口令认证密钥交换系统,其特征在于,包括服务器和若干客户端;其中,

【0021】服务器S,用于接收到客户端C发送的消息<Cid,m,seed>并检查m,如果m不在环Rq上,则协议终止,否则根据种子seed生成公共参数a,并根据环Rq上的中心二项分布选取秘密sS和错误eS、eσ;然后计算yS=asS+eS、yC=m+γ′、σS=yCsS+eσ,并对σS进行协调,得到协调值kσ和信号值v;然后然后计算验证值k=H2(Cid,Sid,m,yS,kσ,γ′)和验证值k″=H3(Cid,Sid,m,yS,kσ,γ′),将<yS,v,k>发送给客户端C;以及接收客户端发送的k′并验证k′是否等于k″,若相等,则计算得到最终的会话密钥skS=H4(Cid,Sid,m,yS,kσ,γ′);

【0022】客户端C,用于随机选取种子seed并生成公共参数a,然后从环Rq上的中心二项分布中选取秘密sC和错误eC,计算yC=asC+eC,γ=H1(pwC),m=yC+γ,然后将<Cid,m,seed>发送给服务器S;以及接收到消息<yS,v,k>后检查yS是否在环Rq上,如果不在环Rq上,则协议终止,否则计算σC=ySsC,调用协调函数Rec(σC,v),得到协调值然后计算γ′=-γ,将H2(Cid,Sid,m,yS,kσ,γ′)与k进行比较,若不相同则协议终止,否则计算k′=H3(Cid,Sid,m,yS,k′σ,γ′),得到最终的会话密钥skC=H4(Cid,Sid,m,yS,k′σ,γ′),并将k′发送给服务器S;

【0023】其中,pwC为客户端C的口令,环Rq为整系数多项式环,γ′为服务器S持有的客户端C的口令哈希值;对于l∈{2,3,4},哈希函数Hl:{0,1}*→{0,1}λ,λ表示最终共享的会话密钥的比特长度,H2和H3用于验证,H4用于密钥派生;2≤t,g≤q和Cid表示客户端标识,g、q、d、t为正整数。

【0024】进一步的,服务器S从中随机选取kσ,计算得到协调值kσ和信号值v。

【0025】进一步的,|σC-σS|q=|eSsC-eCsS-eσ|q≤d,(2d+1)t<q(1-t/g)。

【0026】进一步的,服务器S使用伪随机生成器Gen和种子seed生成公共参数a;如果Gen的输出值a大于或等于5q,则重新生成a,否则将当前生成的a循环减去q,直到更新后的a值小于或等于q,将最终得到的结果作为公共参数a。

【0027】进一步的,通过计算得到中心二项分布;其中xi和xi′是均匀独立的比特。

【0028】该方法是基于理想格上的Ring-LWE困难问题进行构建的,因此能够抵抗量子敌手,在量子环境中是安全的。方案在BPR模型下证明是安全的,它可以抵抗字典攻击、会话密钥缺失等安全威胁,并且具备前向保密性。

【0029】通过使用错误协调机制AKC,当两个参与方交换完信息seed,yC和yS,并根据这些信息分别计算出两个近似的值σC和σS时,可以从中协调出相同的协调值,用于后续的验证和会话密钥的派生。AKC生成的信号值独立于协调值,且协调值均匀分布,即使敌手获取到信号值,也无法从中推断出协调值的信息,保证了方案的安全性。通过增大参数m,可以增加单次协调出的比特长度,而不会显著降低性能。AKC自身的特性允许服务器可以在空闲时间预先计算一部分中间结果,并进行存储,在与客户端交互时可以直接使用,以减少服务器上的负载,从而提高服务器的响应效率,使方案能更适用于大量客户端同时连接服务器的高并发情况。

【0030】通过每次都重新生成公共参数,避免公共参数中被植入陷门,以及避免当方案安全性仅依赖于一个实例时敌手发动all-for-the-price-of-one攻击,找到一个足够好的格基,破解通信过程。在每次连接时,都重新随机选取一个小种子,将其通过伪随机生成器扩展为所需的公共参数。选择从中心二项分布中进行噪声采样,该分布的采样器可以在软件和硬件上高效实现,这种方式不会显著影响方案的安全性,又避免了从高斯分布进行高精度采样的低效,同时能够防止计时攻击。

【0031】附图说明

【0032】图1为本发明基于格的口令认证密钥交换方法示意图。

【0033】具体实施方式

【0034】为了使本发明的目的、技术方案及优点更加清楚明白,以下参照附图,对本发明作进一步详细说明。

【0035】Gen是伪随机生成器,将小种子扩展为环Rq上的元素,H1~H4表示四个不同的哈希函数,H1:{0,1}*→Rq,对于l∈{2,3,4},Hl:{0,1}*→{0,1}λ,λ表示最终共享的会话密钥的比特长度,H2和H3用于验证,H4用于密钥派生。在具体实现时,可以使用XOF函数,如SHAKE-128来实例化H1,使用SHA3-256等哈希函数来来分别对Hl进行实例化,例如Hl(x)=SHA3-256(x,l),l∈{2,3,4}。ψb表示环Rq上的中心二项分布,其标准差为客户端C持有口令pwC,在得到服务器标识Sid后,随机选取种子seed,使用伪随机生成器Gen生成公共参数a,从环Rq上的中心二项分布中选取秘密sC和错误eC,计算yC=asC+eC,γ=H1(pwC),m=yC+γ,将<Cid,m,seed>发送给服务器S,其中Cid表示客户端标识。本发明的方法流程如图1所示,其步骤包括:

【0036】1)服务器S持有客户端口令的哈希值γ′=-H1(pwC),在接收到客户端C发送的消息<Cid,m,seed>后,首先检查m,如果不在环Rq上,则协议终止,否则使用伪随机生成器Gen和种子seed生成公共参数a,根据环Rq上的中心二项分布选取秘密sS和错误eS,eσ,计算yS=asS+eS,yC=m+γ′,σS=yCsS+eσ,通过函数Con对σS进行协调,即从(即小于t的非负整数)中随机选取n个值,分别作为多项式kσ的n个系数,即并针对每一个系数,计算最终得到协调值kσ和信号值v=(v1,...,vn),分别计算验证值k=H2(Cid,Sid,m,yS,kσ,γ′)和验证值k″=H3(Cid,Sid,m,yS,kσ,γ′),将<yS,v,k>发送给客户端C。

【0037】2)客户端接收到消息<yS,v,k>后,首先检查yS,如果不在环Rq上,则协议终止,否则计算σC=ySsC,调用协调函数Rec(σC,v),得到协调值计算γ′=-γ,将H2(Cid,Sid,m,yS,kσ,γ′)与k进行比较,若不相同则协议终止,否则计算k′=H3(Cid,Sid,m,yS,k′σ,γ′),最终的会话密钥skC=H4(Cid,Sid,m,yS,k′σ,γ′),将k′发送给服务器S。

【0038】3)服务器验证k′是否等于k″,若不等于,则协议终止,否则计算最终的会话密钥skS=H4(Cid,Sid,m,yS,kσ,γ′)。

【0039】客户端C持有口令pwC,服务端持有口令的哈希值。1)对服务器的认证:发送消息时,客户端将口令的哈希值添加到原始消息中,只有当服务器保存有对应的哈希值时,才能获取正确的原始消息。一旦服务器没有口令的哈希值,就无法计算正确计算原始消息,后续验证值k将与客户端计算的H2(Cid,Sid,m,yS,kσ,γ′)不一致,对服务器的认证失败,协议将终止。2)对客户端的认证:当客户端持有的口令与服务器存储的哈希值不对应时,计算出的k′将与服务器计算的k″不一致,对客户端的认证失败,协议终止。

【0040】当|σC-σS|q=|eSsC-eCsS-eσ|q≤d时,客户端和服务器可以获得相同的协调值kσ,并且协议能够按流程正确执行,若双方的口令和口令哈希值匹配,成功完成认证,则通信双方持有的(Cid,Sid,m,yS,kσ,γ′)完全一致,得到的会话密钥skC=skS,密钥交换成功,双方即可利用得到的会话密钥进行后续的通信。错误率与选取的参数相关,一方面参数需要满足2≤t,g≤q,(2d+1)t<q(1-t/g)时,确保AKC的正确性和安全性,另一方面,要选取尽量大的d,使整个方案的错误率尽可能地低。当选择的标准差为维度n=1024,模数q=12289,AKC相关参数t=2,g=64时,计算出满足条件的最大的d为2975,根据|eSsC-eCsS-eσ|q的分布,可以得到方案的错误率为2-41,对于大部分密钥交换的场景是足够的。

【0041】每次会话都重新生成公共参数会对性能产生轻微影响。为了最小化性能损失,本发明不需要传输公共参数a,而仅传输用于生成a的种子并假设生成的a直接在NTT域中以减少使用NTT的次数。同时,本发明采取下述措施降低a的采样拒绝率来加速生成:在从小种子扩展生成公共参数a时,如果Gen的输出值大于或等于5q,则拒绝这个值,重新生成,否则将这个值循环减去q,直到值在q以内,将结果作为公共参数的系数。中心二项分布ψk可以通过计算得到,其中xi和xi′是均匀独立的比特。

【0042】在基于Ring-LWE问题的方案中,多项式计算是最耗时的操作。本发明选择了维度n=1024,这是对于长期安全性和性能的一个合适的选择。模数q=12289是满足q≡1mod2n的最小素数,因此可以使用NTT对多项式乘法进行加速,这可以极大的提高计算速度。同时,比较小的模数可以使多项式更小,能减少协议的通信开销。由于安全级别随噪声-模数比增长,因此选择小的模数可以提高紧凑性和效率的同时提高安全强度。

【0043】尽管为说明目的公开了本发明的具体内容、实施算法以及附图,其目的在于帮助理解本发明的内容并据以实施,但是本领域的技术人员可以理解:在不脱离本发明及所附的权利要求的精神和范围内,各种替换、变化和修改都是可能的。本发明不应局限于本说明书最佳实施例和附图所公开的内容,本发明要求保护的范围以权利要求书界定的范围为准。

【说明书附图】


【0001】


图1