基于二叉树的非签名认证密钥协商协议

吴福生 张焕国

(武汉大学计算机学院 武汉 430072) (空天信息安全与可信计算教育部重点实验室(武汉大学) 武汉 430072)

基于二叉树的非签名认证密钥协商协议

吴福生 张焕国

(武汉大学计算机学院 武汉 430072) (空天信息安全与可信计算教育部重点实验室(武汉大学) 武汉 430072)

(liss@whu.edu.cn)

协议是网络通信的规范，密码协议是信息安全的关键技术之一，安全的密码协议常常依赖于签名或消息认证技术.签名或消息认证给密钥协商协议通信带来大量计算，不利于计算能力有限设备的网络通信.设计具有计算量小又实用的安全协议是信息安全研究目标之一.故以整数乘法同态映射和二叉树为基础，提出一种新的密钥协商协议，并在开源的OpenSSL环境下实现新协议模拟实验，给出二叉树叶子结点数变化对网络通信影响的模拟实验和实验结果分析.新协议在随机预言模型下可证明安全，即在公钥加密方案中新协议满足选择明文攻击不可区分性的(IND-CPA)安全.新协议与经典的密钥协商协议相比(例如MTI，MQV，HMQV)，计算量小、强安全假设少、无需额外的签名与消息认证，且可以在非安全通信信道上进行安全通信.

协议；密码学；同态；二叉树；可证明安全

密钥协商协议是网络空间信息安全研究的重点[1].已经在很多方面得到应用，特别是基于分布式安全多方计算的密钥协商协议的应用，引起学者们广泛的关注[2].Diffie和Hellman[3]在1976年提出著名的Diffie-Hellman密钥协商协议(简称Diffie-Hellman协议)，第1次在非安全的公共通信信道上实现密钥协商.此后，许多研究者以Diffie-Hellman协议为基础，提出改进的密钥协商协议，著名的有MTI系列[4-6]密钥协商协议、MQV[7]密钥协商协议和KEA密钥协商协议[8].MQV协议的改进协议[9]引起研究者极大的关注，已成为IEEE P1363-2000标准[10].目前，以MQV为基础的最新研究成果有：HMQV[11]，OAKE[12]，sHMQV[13]，YAK[14-15]等密钥协商协议.其中，最具代表性的是HMQV密钥协商协议.

这些协议在密钥协商方面已有很大的改进，但是仍存在一些不足：Diffie-Hellman协议无法抵抗中间人攻击；MTI系列容易受到未知密钥攻击、Lim-Lee攻击、身份假冒攻击；MQV容易受到密钥泄露伪装攻击； HMQV协议及以它为基础的改进协议无法在多种移动终端设备上实行(受计算能力有限或安全性不高等因素制约).上述密钥协商协议的安全性必须依赖于签名或消息认证，因此增加协议的时间开销.更详细的密钥交换协商协议参考文献[16].

本文以整数乘法同态映射*整数乘法同态映射：设α，β∈Z-{0}，f：Z-{0}→Z-{0}，满足f(α)*f(β)= f(α*β).和二叉树为基础，提出一种新的密钥协商协议，并且在OpenSSL的C语言环境下给出新协议叶子结点参数变化的网络通信模拟实验和实验结果分析.新协议无需依赖额外签名或消息认证，也能提供协议参与者之间隐式认证和抵抗中间人攻击.由于无须签名或认证，可减少通信时间开销，新协议应用于计算能力有限的设备或大数据、云计算网络环境下的通信时，在计算量的开销上有一定的优势.

1 基础知识

本文以整数环上的乘法同态映射为基础，根据群的同态概念给出基本定义与定理.

1.1 基本定义

定义1. 群同态[17].设G1，G2是2个群(半群、幺半群)，“*” 为二元乘法运算.f是G1到G2的映射，如果f满足：

∀x,y∈G1,f(x)∈G2,
f(x)*f(y)=f(x*y)，

(1)

则称f是群(半群、幺半群)G1到群(半群、幺半群)G2的一个同态映射，简称同态.

定义2. 映射.由于f是半群或幺半群+上的一个映射，“*”为二元乘法运算，f满足：

f(x)×f(y)=f(x×y)x,y∈+.

(2)

根据定义1，称f是半群或幺半群+到自身的一个整数乘法同态映射，x,y∈+称之为整数同态点，而对应的点f(x*y)∈+称为整数同态值.

1.2 基本定理

定理1. 如果在整数环上的半群或幺半群+上存在一个整数乘法同态映射f，从半群或幺半群+任意取n个数ai∈+,i=1,2,…,n，则一定存在一个整数乘法同态值f(a1*a2*…*an)与之对应.

证明: 任取n个整数，∀a1,a2,…ai,…,an∈+，计算f(a1)*f(a2)*…*f(an)，令其值为v：

f(a1)*f(a2)*,…,*f(an)=v.

(3)

根据乘法的结合律两两结合，式(3)可变为

(4)

1) 当n为偶数时，刚好两两匹配，适合乘法结合律，即式(4)不变.

2) 当n为奇数时，增加一项f(1)=1，不影响式(4)积值.

由1)和2)可知，总是存在式(4)的表示法.由定义2，式(4)可变为

f(a1*a2)*…*f(an-1*an)=v.

(5)

根据乘法结合律两两结合，以此类推，最后等式成立：

f(a1*a2*…*an-1*an)=v.

(6)

由此可得，式(3)与式(6)相等:

f(a1)*f(a2)*…*f(an)=
f(a1*a2*…*an)=v.

(7)

证毕.

2 整数乘法同态二叉树的构造与分析

二叉树在计算机科学中是一种常用的数据结构.它既可用抽象的代数理论表示，也可用程序语言伪代码表示，介于理论与程序代码之间.因此，二叉树结构非常容易转化为实际执行的计算机程序代码.

2.1 整数乘法同态二叉树的构造

2) 根据定义2，计算f(xi)*f(xj)=vi,j，f(xi*xj)=f(vi,j)=vi,j.

3) 由定理1，等式f(xi)*f(xj)=f(xi*xj)=vi,j成立.

4) 以f(xi)=vi为左子树、f(xj)=vj为右子树、f(xi*xj)=vi,j为根结点，构造1棵二叉树.下面给出任意2个结点的构造二叉树，如图1所示:

Fig. 1 The binary tree structure of any two nodes图1 任意2结点的构造二叉树

5) 随机选取xi+1,xj+1∈+，执行过程1)～4)构造第2棵二叉树，得到以f(vi+1*vj+1)=vi,j,i+1,j+1为根结点的二叉树，如图2所示:

Fig. 2 The binary tree structure of any two nodes图2 任意2结点的构造二叉树

6) 由定理1可知:

f(xi*xj)*f(xi+1*xj+1)=
f(xi*xj*xi+1*xj+1)

成立，则以f(xi*xj)=vi,j为根结点为左子树、以f(xi+1*xj+1)=vi+1,j+1为根结点的右子树、以f(vi+1*vj+1)=vi,j,i+1,j+1为根结点，构造1棵二叉树，如图3所示：

Fig. 3 A binary tree图3 二叉树

7) 以此类推，当n个随机数两两匹配结束，则构造成1棵叶子结点数为n的二叉树T，称之为整数乘法同态二叉树，如图4所示：

The binary tree with n leaf nodes图4 n个叶子结点的构造二叉树

2.2 整数乘法同态二叉树的基本遍历与性质

整数乘法同态二叉树没有空树，即不会有空操作.整数乘法同态二叉树的基本遍历与性质类似于数据结构[18]中的二叉树的基本遍历与性质.整数乘法同态二叉树的基本遍历和性质如下：

2.2.1 整数乘法同态二叉树的先序遍历

为了清楚整数乘法同态二叉树的先序遍历，给出先序遍历步骤：

1) 访问根结点；

2) 先序遍历左子树；

3) 先序遍历右子树.

① 虽然通信双方A与B注册有相同的点，但其认证结构不同于以往的Diffie-Hellman扩展协商协议，即使敌手E能得到A或B的所有注册点，也无法获得A与B的共享密钥.详细分析见4.3节.

2.2.2 整数乘法同态二叉树的基本性质

性质1. 整数乘法同态二叉树的第i层上至多有2i-1个结点(i≥1).

性质2. 整数乘法同态二叉树的深度为k时，二叉树至多有2k-1个结点(k≥1).

3 整数乘法同态二叉树的密钥协商协议

通信双方A和B在可信第三方TA中一次性注册一些相同的可信同态点①(素数，且A端的同态点集合中不会有相同点，同理B端的同态点集合中不会有相同点).这些点数量满足2h,h∈n，即叶子结点是以2h配对增加，(如h=1时叶子结点为2，h=2时叶子结点为4，h=3时叶子结点数为8，即叶子结点是以2h配对增加).当协议运行时，分别在A和B端构造1棵整数乘法同态二叉树(其叶子结点为素数).通过整数乘法同态二叉树的先序遍历，找到认证点(即同态值)，取同态值的左、右子树根结点作为参数，然后基于Diffie-Hellman协议进行密钥协商，得到共享会话密钥kAB，即完成通信双方的隐式认证.该共享会话密钥kAB可应用于认证、加密、签名等.当协议结束时，通信双方释放构造的整数乘法同态二叉树.

3.1 构造1棵叶结点为素数的整数乘法同态二叉树

根据2.1节的整数乘法同态二叉树构造方法，构造1棵叶子结点为素数的整数乘法同态二叉树.构造方法如下：

设Z1⊂+和Z2⊂+是2个整数环上的半群或幺半群，Z1，Z2是+上的一个划分，且Z1={pi|p∈primes∧i∈n}.f是+到自身的一个整数乘法同态映射，pi,pj∈Z1，i,j∈n,i≠j不同的素数.随机选取pi,pj，构造1棵叶子结点为素数的同态二叉树，其步骤为：

1) 随机选取不同的素数pi，pj，计算f(pi)=pi，f(pj)=pj，f(pi*pj)=vi,j.

2) 以f(pi)=pi为左子树、f(pj)=pj为右子树、f(pi*pj)=vi,j为根结点，构造1棵叶子结点为素数的同态二叉树.

3) 随机选取pi+1，pj+1，计算f(pi+1)=pi+1，f(pj+1)=pj+1，f(pi+1*pj+1)=vi+1，j+1，以f(pi+1)=pi+1为左子树，f(pj+1)=pj+1为右子树，f(pi+1*pj+1)=vi+1，j+1为根结点，构造1棵叶子结点为素数的同态二叉树.

4) 分别以步骤2)的根结点f(pi*pj)=vi,j为左子树根结点、步骤3)的根结点f(pi+1*pj+1)=ni+1，j+1为右子树根结点，构造1棵叶子结点为素数的同态二叉树.

5) 重复步骤1)～4)，n个素数叶子结点两两配对完成后，构造出1棵叶子结点为素数的同态二叉树，称之为Ti，j，如图5所示:

Fig. 5 The homomorphic binary tree with n leaf nodes of the primenumbers图5 叶子结点为n个素数的同态二叉树

3.2 整数乘法同态二叉树密钥协商协议具体步骤

Ti，j是已经构造好的叶子结点为素数的同态二叉树.为证明方便，用一个集合{Ti，j}表示构造好的同态二叉树，分别存储于通信双方(A和B).pi,pj∈Z1,i,j∈n,i≠j是叶子结点(即为素数).G是一个素数阶为N的循环群，g∈G是群G的生成元.

f为+到自身的一个同态映射：f(x)=x，x∈+.

参数设置：{Ti，j}，ri,rj∈{Ti，j},i,j∈n,i≠j保密；结点ri,j∈{Ti，j}，G，g公开.协议执行步骤：一轮A与B密钥协商，如图6所示，“‖”表示连接.

Fig. 6 One round A and B key exchange protocols图6 一轮A与B密钥交换协议

1)A在整数乘法同态二叉树中，如图5所示，随机选取2个兄弟结点数ri,rj，且计算：f(ri)=ri，f(rj)=rj，f(ri)*f(rj)=f(ri*rj)=ri，j，X=grimodN，把(X‖ri，j)发送给B.

2)B收到(X‖ri,j)，根据2.2.1节整数同态二叉树的先序遍历，查找ri,j.如果查找成功，取ri,j的左子树根结点ri，计算Y′=grimodN，然后验证等式X=Y′，相等则B相信(X‖ri,j)是由A发送.否则，终止协议执行.

所以A与B生成共享密钥kAB，即完成通信双方的密钥协商.

4 协议安全分析

新协议可以抵抗中间人攻击.当只有2个大素数叶子结点时，新协议的安全性等价于大整数因式分解的困难.新协议满足CDH与DDH安全性假设及GDH[19]假设.给出新协议结构的安全证明.

4.1 一般安全性分析

1) 建立敌手模型.设E是攻击者，E具有Dolev-Yao[20]模型的能力：①完全控制网络信息交换，即敌手可以获得网络上的任何信息；②主动攻击与被动攻击(冒充、截取、注入、重放等能力)；③询问随机预言模型；④离线计算能力.

2) 假设在通信双方A和B端当且仅当取2个大素数叶子结点pi,pj时，即为pi*pj=ni,j，其安全性等同于RSA算法.

3) 新协议以Diffie-Hellman为基础，满足CDH与DDH假设.

① 满足CDH假设：存在一个PPT算法C，在树{Ti，j}随机选取ri,rj，存在:

Pr[Cg,gri,grj=gri]≤ε(n)，

(8)

其中,ε(n)为概率可忽略不计函数.即协议满足CDH假设安全.

② 满足DDH假设：存在一个PPT算法C，在树{Ti，j}随机选取ni,nj，存在:

Pr[Cg,gri,grj,grirj=1]-
Pr[Cg,gri,grj,gc=1]≤ε(n)，

(9)

其中,ε(n)为概率可忽略不计函数.即协议满足DDH假设安全.

4) 新协议没有使用签名与消息认证，但可以抵抗中间人攻击和具有隐式认证功能.

Ⅰ必须解决离散对数难解问题，即求解截获X的指数ri；

Ⅱ整数因式分解问题，即分解截获的大整数ri,j的因子ri.故协议可以抵抗中间人攻击.

5) 会话密钥kAB的前向安全.由同态二叉树可知，ri,j是随机选择，具备新鲜度,所以每次得到的会话密钥kAB都不一样，且每次都是独立.故前后生成的kAB不会相互泄密信息，保证新协议的前向安全成立.

4.2 基于随机预言模型(random oracle model)的可证明安全分析

设DDH(·)为预言机，D为一个求解GDH问题的算法.

定义求解的优势概率为

Pr[D(g,gri,grj,gri)=1]-
Pr[D(g,gri,grj,gc)=1].

(10)

如果其优势概率满足：

Pr[D(g,gri,grj,gri)=1]-
Pr[D(g,gri,grj,gc)=1]≤ε(n)，

(11)

ri,rj∈+,g∈G，ε(n)可忽略不计的.则称协议满足GDH假设.

(12)

当n→∞时，优势概率可忽略不计，协议在RO模型下是可证明安全的，即满足IND-CPA安全.

证毕.

4.3 新协议结构的安全分析

由新协议构造可知，假设敌手E在2种情况下成立，则E可以攻破协议.

1)E可获取A或B端的注册点，即同态点.

2) 二叉树的结点不唯一(例如存在：当ri≠rj≠rk≠rm,i,j,k,m∈n，有rirj=rkrm).

证明.

1) 假设E获取了A或B端的注册点，设为{p1,p2,…,p2n}.由3.1节可知，在构造二叉树时，叶子结点是配对组成由数学的排列组合可知h∈n.

(13)

证毕.

5 新协议性能比较与分析

本文分别从3个方面分析新协议的性能.

5.1 新协议的二叉树存储与遍历

二叉树是计算机科学中常用的一种数据结构，其常用存储方式有2种：1)顺序存储;2)链式存储.不管是哪一种存储，在它最坏情况下空间复杂度为O(n)，遍历的时间复杂度为O(n).

设新协议的二叉树叶子结点为n，分析新协议最坏情况的存储.根据性质1(见2.2.2节)得到新协议的二叉树深度为i=lbn+1.根据性质2(见2.2.2节)得到新协议总结点数为：2lb n+1-1=2n-1.由此可知，新协议存储空间为线性O(n).根据其存储方式可知其遍历复杂度为线性O(n)，故新协议可实现.

5.2 计算量比较

选取4种以Diffie-Hellman协议为基础的相似协议和同类横向2种身份识别协议，比较它们在最坏情况下计算量大小和在协议中会用的安全假设个数，结果如表1所示，其中的Texp表示1次指数运算的时间.

Table 1 Compared Performance of the Protocols表1 协议的性能比较

表1中协议使用的签名或消息认证为

从表1可以看出，提出的新协议在计算量的开销方面具有明显优势，原因是新协议不需要加入签名和消息认证.同时协议只使用1个强安全假设GDH，与使用2个强安全假设(GDH，KEA[21]假设)的密钥协商协议(HMQV，OAKE)相比，新协议在实际应用中安全性更高.

5.3 参数n对网络通信的影响

参数n对新协议在网络通信中的影响主要表现为：1)结点的查找；2)通信时间开销.

(14)

当n→∞时，平均查找长度为：lbn.故新协议查找长度为对数可以实现.

2) 新协议基于OpenSSL下的C语言代码模拟实验，分析参数n变化对新协议在网络通信中所用时间的影响.

本文给出n的2种变化形式对新协议在网络通信中的影响：①二叉树素数叶子结点个数(numbers of nodes,N)；②叶子结点的位数(node bits,bits).

实验环境：Intel®CPU G3240，内存4 GB；Win7，Visual studio 2010，openSSL-1.0.1 s.使用OpenSSL函数库的大数运算，其中包括大数模指数运算函数、大素数生成函数等使用.参与者之间的通信经过Socket API的TCP连接.

采用服务器与客户端模式进行模拟实验，分别得出叶子结点个数与结点位数变化在网络通信中的时间开销，如表2所示(行表示叶子结点的位数，列表示叶子结点的个数N，行列交点表示网络传输花费的时间).

Table 2 The Effect of the Network Communication Based on Binary Tree Nodes表2 二叉树结点的网络通信影响 s

对表2的数据分别以行、列及网络通信时间(s)作为坐标进行分析.实验数据分析结果：图7表示叶子结点个数变化对网络通信时间的影响；图8表示叶子结点位数变化对网络通信时间的影响.

Fig. 7 The effect of the number of leaf nodes on communication time in network图7 叶子结点个数变化对网络通信时间的影响

Fig. 8 The effect of the bit of leaf nodes on communication time in network图8 叶子结点位数变化对网络通信时间的影响

3) 结果分析：

① 从图7与图8可知，结点个数N和结点位数bits，在比较小的情况下，对网络通信并没有太大的影响.但随着它们变大，网络通信时间开销随之增长.②结点位数带来的网络时间开销增长比结点的个数带来的时间开销增长快.③不防设结点个数与位数的比值为：δ=N/b.当δ越小，则叶子结点位数越大，需要的叶子结点个数越少.这不仅保证了新协议的安全，而且消耗的资源更少(如叶子结点的个数、二叉树结点寻找时间等).例如，如果叶子结点是1 024 b二进制素数，新协议只需要2个大素数叶子结点，就能生成1个2 048 b二进制整数根结点.这时新协议的安全等价于1个2 048 b二进制大整数因式分解的困难.故新协议的安全完全等价于RSA的安全[23].

6 结束语

本文对已有密钥协商协议进行了研究，提出一种计算量小、无需签名和消息认证等额外时间开销的密钥协商协议.提出的新协议方案具有计算量小、强安全假设少、占用资源少等优点，具有一定的创新性与适用性.其安全性依赖离散对数与大整数因式分解困难问题.新协议引入二叉树及其性质和特点，使得协议更容易转化为实际的程序语言代码，适用于云计算、 物联网、 社交网络和大数据等新兴网络通信服务.协议并发通信的安全与认证将作为未来的研究方向.

[1]Zhang Huanguo, Han Wenbao, Lai Xuejia, et al. Survey on cyberspace security[J]. Scientia Scinica: Informations, 2116, 46(2): 125-164 (in Chinese)(张焕国, 韩文报, 来学嘉, 等. 网络空间安全综述[J]. 中国科学: 信息科学, 2016, 46(2): 125-164)

[2] Jian Han, Xu Qiuliang. Advances in key techniques of practical secure multi-party computation[J]. Journal of Computer Research and Development, 2015, 52(10): 2247-2257 (in Chinese)(蒋瀚, 徐秋亮. 实用安全多方计算协议关键技术研究进展[J]. 计算机研究与发展, 2015, 52(10): 2247-2257)

[3] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans on Information Theory, 1976, 22(6): 644-654

[4] Lim C H, Lee P J. A key recovery attack on discrete long-based schemes using a prime order subgroup[G] //LNCS 1294: Advances in Cryptology 1997. Berlin: Springer, 1997: 249-263

[5] Just M, Vaudenay S. Authenticated multi-party key agreement[G] //LNCS 1163: Advances in Cryptology 1996. Berlin: Springer, 1996: 36-49

[6] Goss K C. Cryptographic method and apparatus for public key exchange with authentication: USA, US4956863[P]. 1990-09-11

[7] Menezes A, Qu M, Vanstone S. Some new key agreement protocols providing implicit authentication[C] //Proc of the 2nd Workshop Selected Areas in Cryptography. Berlin: Springer, 1995: 89-98

[8] Schneier B. Skipjack and kea algorithm specification version 2.0[R/OL]. Washington: National Security Agency, 1998 [2016-10-30]. http://ece.gmu.edu/coursewebpages/ECE/ECE646/F09/project/reports_1999/carlton_report.pdf

[9] Law L, Menezes A, Qu M, et al. An efficient protocol for authenticated key agreement[J]. Designs, Codes and Cryptography, 2003, 28(2): 119-134

[10] IEEE. Standard specifications for public-key cryptography[S]. New York: Institute of Electrical Electronics Engineers, 2000: 1-228

[11] Krawczyk H. Hmqv: A high-performance secure Diffie-Hellman protocol[G] //LNCS 3621: Advances in Cryptology 2005. Berlin: Springer, 2005: 546-566

[12] Yao Qizhi. Zhao Yunlei. Oake: A new family of implicitly authenticated Diffie-Hellman protocols[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 1113-1128

[13] Zhao Shijun, Zhang Qianying. Shmqv: An efficient key exchange protocol for power-limited devices[G] //LNCS 9065: Information Security Practice and Experience ISPEC 2015. Berlin: Springer, 2015: 154-167

[14] Feng Hao. On robust key agreement based on public key authentication[J]. Security and Communication Networks, 2014, 7(1): 77-87

[15] Toorani M. Cryptanalysis of a robust key agreement based on public key authentication[J]. Security and Communi-cation Networks, 2016, 9(1): 19-26

[16] Feng Dengguo. Security Protocol—Theory and Practice[M]. Beijing: Tsinghua University Press, 2011: 273-316 (in Chinese)(冯登国. 安全协议——理论与实践[M]. 北京: 清华大学出版社, 2011: 273-316)

[17] Xu Shurun, Meng Daoji, Xiao Yongzhen, et al. Concise Mathematics Dictionary[M]. Beijing: Science Press, 2002: 45-88 (in Chinese)(徐书润, 孟道骥, 萧永震, 等. 简明数学词典[M]. 北京: 科学出版社, 2002: 45-88)

[18] Clifford A. Data Structures, Algorithm Analysis in C++[M]. 3rd ed. New York: Dover Publications, 2011: 155-160

[19] Okamoto T, Pointcheval D. The gap-problems: A new class of problems for the security of cryptographic schemes[C] //Proc of Int Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography 2001. Berlin: Springer, 2001: 104-118

[20] Dolev D, Yao Qizhi. On the security of public key protocols[J]. IEEE Trans on Information Theory, 1983, 29(2): 198-208

[21] Bellare M, Palacio A. The knowledge-of-exponent assum-ptions and 3-round zero-knowledge protocols[G] //LNCS 3152: Advances in Cryptology 2004. Berlin, Springer: 2004: 273-289

[22] Yan Weimin, Wu Weimin. Data Structure (C Language Version)[M]. Beijing: Tsinghua University Press, 2008: 118-152 (in Chinese)(严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社, 2008: 118-152)

[23] Beniwal S, Yadav E, Savita. An effective efficiency analysis of random key cryptography over Rsa[C] //Proc of the 2nd Int Conf on Computing for Sustainable Global Development. Piscataway, NJ: IEEE, 2015: 267-271

KeyAgreementProtocolsofNon-SignatureAuthenticationBasedonBinaryTree

Wu Fusheng and Zhang Huanguo

(SchoolofComputerScience,WuhanUniversity,Wuhan430072) (KeyLaboratoryofAerospaceInformationSecurityandTrustedComputing(WuhanUniversity),MinistryofEducation,Wuhan430072)

Protocol is the specification of the network communication. Then cryptographic protocol, whose safety is based on signature or authentication technology, is one of the key techniques of information security. The technique of signature or authentication needs huge computation during communicating, which brings barriers for many communication devices because of their limited computing power. Therefore, it is an aim of studying information security to design a secure cryptographic protocol, which is practical but doesn’t need huge computation. In this paper, a novel key agreement protocol is proposed, which is based on the binary tree and the homomorphic mapping of integer multiplication. Meanwhile, an experiment is carried out in an open source (OpenSSL) systems to test how nodes of leaf binary trees affect network communication and the result of the experiment is analyzed. Our scheme is successful because our key agreement protocol is proved to be safe in the random oracle model. That is to say, in the PKI system, our key agreement protocol meets the requirement of the indistinguishable chosen plaintext attack (IND-CPA ) security. Compared with previous protocols (like MTI, MQV, HMQV), our key agreement protocol has many advantages: the computation is small; only one strong security assumption is needed; it dispenses with extra authentication of MAC and digital signature; and communicating parties can authenticate implicitly through unsafe channels.

protocols; cryptography; homomorphism; binary tree; provably secure

2016-11-01；

2017-02-06

国家自然科学基金重点项目(61332019)；国家“九七三”重点基础研究发展计划基金项目(2014CB340601)

This work was supported by the Key Program of the National Natural Science Foundation of China (61332019) and the National Basic Research Program of China (973 Program) (2014CB340601).

TP309

WuFusheng, born in 1974. PhD. His main research interests include design of cryptographic protocols and security analysis of cryptographic protocols.

ZhangHuanguo, born in 1945. Professor and PhD supervisor in Wuhan University. His main research interests include cryptography and trusted computing, and cryptographic protocols.