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

摘要

本发明公开了一种基于格的口令认证密钥交换方法及系统。本发明通过使用错误协调机制AKC，当两个参与方交换完信息seed,y

说明书

技术领域

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

背景技术

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

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

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

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

Con(σ₁，params)：输入σ₁和params，从中随机选取k₁，计算输出v。

Rec(σ₂,v,params)：输入σ₂和params，计算输出k₂。

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

发明内容

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

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

本发明的技术方案为：

一种基于格的口令认证密钥交换方法，其步骤包括：

1)客户端C随机选取种子seed并生成公共参数a，然后从环R_q上的中心二项分布中选取秘密s_C和错误e_C，计算y_C＝as_C+e_C，γ＝H₁(pw_C)，m＝y_C+γ，然后将<C_id,m,seed>发送给服务器S；其中pw_C为客户端C的口令；

2)服务器S接收到客户端C发送的消息<C_id,m,seed>后，首先检查m，如果不在环R_q上，则协议终止，否则根据种子seed生成公共参数a，并根据环R_q上的中心二项分布选取秘密s_S和错误e_S、e_σ；然后计算y_S＝as_S+e_S、y_C＝m+γ′、σ_S＝y_Cs_S+e_σ,并对σ_S进行协调，得到协调值k_σ和信号值v；然后计算验证值k＝H₂(C_id,S_id,m,y_S,k_σ,γ′)和验证值k″＝H₃(C_id,S_id,m,y_S,k_σ,γ′)，将<y_S,v,k>发送给客户端C；其中，环R_q为整系数多项式环，γ′为服务器S持有的客户端C的口令哈希值；对于l∈{2,3,4}，哈希函数H_l:{0,1}^*→{0,1}^λ，λ表示最终共享的会话密钥的比特长度，H₂和H₃用于验证，H₄用于密钥派生，C_id表示客户端标识；

3)客户端C接收到消息<y_S,v,k>后，首先检查y_S，如果不在环R_q上，则协议终止，否则计算σ_C＝y_Ss_C,调用协调函数Rec(σ_C,v)，得到协调值k′_σ＝「t(v/g-σ₂/q)modt」；然后计算γ′＝-γ，将H₂(C_id,S_id,m,y_S,k_σ,γ′)与k进行比较，若不相同则协议终止，否则计算k′＝H₃(C_id,S_id,m,y_S,k′_σ,γ′)，得到最终的会话密钥sk_C＝H₄(C_id,S_id,m,y_S,k′_σ,γ′)，并将k′发送给服务器S；其中，2≤t,g≤q和S_id为服务器S的标识，g、q、d、t为正整数；

4)服务器S验证k′是否等于k″，若相等，则计算得到最终的会话密钥sk_S＝H₄(C_id,S_id,m,y_S,k_σ,γ′)。

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

服务器S，用于接收到客户端C发送的消息<C_id,m,seed>并检查m，如果m不在环R_q上，则协议终止，否则根据种子seed生成公共参数a，并根据环R_q上的中心二项分布选取秘密s_S和错误e_S、e_σ；然后计算y_S＝as_S+e_S、y_C＝m+γ′、σ_S＝y_Cs_S+e_σ,并对σ_S进行协调，得到协调值k_σ和信号值v；然后然后计算验证值k＝H₂(C_id,S_id,m,y_S,k_σ,γ′)和验证值k″＝H₃(C_id,S_id,m,y_S,k_σ,γ′)，将<y_S,v,k>发送给客户端C；以及接收客户端发送的k′并验证k′是否等于k″，若相等，则计算得到最终的会话密钥sk_S＝H₄(C_id,S_id,m,y_S,k_σ,γ′)；

客户端C，用于随机选取种子seed并生成公共参数a，然后从环R_q上的中心二项分布中选取秘密s_C和错误e_C，计算y_C＝as_C+e_C，γ＝H₁(pw_C)，m＝y_C+γ，然后将<C_id,m,seed>发送给服务器S；以及接收到消息<y_S,v,k>后检查y_S是否在环R_q上，如果不在环R_q上，则协议终止，否则计算σ_C＝y_Ss_C,调用协调函数Rec(σ_C,v)，得到协调值然后计算γ′＝-γ，将H₂(C_id,S_id,m,y_S,k_σ,γ′)与k进行比较，若不相同则协议终止，否则计算k′＝H₃(C_id,S_id,m,y_S,k′_σ,γ′)，得到最终的会话密钥sk_C＝H₄(C_id,S_id,m,y_S,k′_σ,γ′)，并将k′发送给服务器S；

其中，pw_C为客户端C的口令，环R_q为整系数多项式环，γ′为服务器S持有的客户端C的口令哈希值；对于l∈{2,3,4}，哈希函数H_l:{0,1}^*→{0,1}^λ，λ表示最终共享的会话密钥的比特长度，H₂和H₃用于验证，H₄用于密钥派生；2≤t,g≤q和C_id表示客户端标识，g、q、d、t为正整数。

进一步的，服务器S从中随机选取k_σ，计算得到协调值k_σ和信号值v。

进一步的，|σ_C-σ_S|_q＝|e_Ss_C-e_Cs_S-e_σ|_q≤d，(2d+1)t<q(1-t/g)。

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

进一步的，通过计算得到中心二项分布；其中x_i和x_i′是均匀独立的比特。

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

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

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

附图说明

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

具体实施方式

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

Gen是伪随机生成器，将小种子扩展为环R_q上的元素，H₁～H₄表示四个不同的哈希函数，H₁:{0,1}^*→R_q，对于l∈{2,3,4}，H_l:{0,1}^*→{0,1}^λ，λ表示最终共享的会话密钥的比特长度，H₂和H₃用于验证，H₄用于密钥派生。在具体实现时，可以使用XOF函数，如SHAKE-128来实例化H₁，使用SHA3-256等哈希函数来来分别对H_l进行实例化，例如H_l(x)＝SHA3-256(x,l)，l∈{2,3,4}。ψ_b表示环R_q上的中心二项分布，其标准差为客户端C持有口令pw_C，在得到服务器标识S_id后，随机选取种子seed，使用伪随机生成器Gen生成公共参数a，从环R_q上的中心二项分布中选取秘密s_C和错误e_C，计算y_C＝as_C+e_C，γ＝H₁(pw_C)，m＝y_C+γ，将<C_id,m,seed>发送给服务器S，其中C_id表示客户端标识。本发明的方法流程如图1所示，其步骤包括：

1)服务器S持有客户端口令的哈希值γ′＝-H₁(pw_C)，在接收到客户端C发送的消息<C_id,m,seed>后，首先检查m，如果不在环R_q上，则协议终止，否则使用伪随机生成器Gen和种子seed生成公共参数a，根据环R_q上的中心二项分布选取秘密s_S和错误e_S,e_σ，计算y_S＝as_S+e_S，y_C＝m+γ′,σ_S＝y_Cs_S+e_σ,通过函数Con对σ_S进行协调，即从(即小于t的非负整数)中随机选取n个值，分别作为多项式k_σ的n个系数，即并针对每一个系数，计算最终得到协调值k_σ和信号值v＝(v¹,...,vⁿ)，分别计算验证值k＝H₂(C_id,S_id,m,y_S,k_σ,γ′)和验证值k″＝H₃(C_id,S_id,m,y_S,k_σ,γ′)，将<y_S,v,k>发送给客户端C。

2)客户端接收到消息<y_S,v,k>后，首先检查y_S，如果不在环R_q上，则协议终止，否则计算σ_C＝y_Ss_C,调用协调函数Rec(σ_C,v)，得到协调值计算γ′＝-γ，将H₂(C_id,S_id,m,y_S,k_σ,γ′)与k进行比较，若不相同则协议终止，否则计算k′＝H₃(C_id,S_id,m,y_S,k′_σ,γ′)，最终的会话密钥sk_C＝H₄(C_id,S_id,m,y_S,k′_σ,γ′)，将k′发送给服务器S。

3)服务器验证k′是否等于k″，若不等于，则协议终止，否则计算最终的会话密钥sk_S＝H₄(C_id,S_id,m,y_S,k_σ,γ′)。

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

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

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

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

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