基于陷门哈希函数的无证书签密方案

束 红

（1.铜陵学院 数学与计算机学院，安徽 铜陵 244061；2.网络与信息安全安徽省重点实验室，安徽 芜湖 241002）

数字签密技术通过逻辑单操作完成对消息的加密和数字签名，而其计算和通信成本比加密和签名的叠加成本更有效，同时提供机密性、完整性、认证性和不可否认性［1］，在网络安全传输和通信中起到重要的作用。

1 相关研究

1997 年，Zheng［2］（P17-21）首次提出了数字签密的概念，有效改善了传统的“先加密后签名”算法计算效率低的不足［3］。 文献［1］将数字签密分为基于PKI 的签密［2］（P17-21）、基于身份的签密［4］及无证书签密［3，5-8］三类。 其中，PKI 密码体制具有证书的分发、存储等管理问题， 基于身份的密码体制存在密钥托管的缺陷，因此，无证书密码体制因其既无证书管理问题又无密钥托管问题， 且计算效率高于传统的公钥密码体制， 引起了广大研究者的兴趣。2008 年，Barbosa 等人［9］(P369-372)首次提出无证书签密概念。 自此，学者们围绕无证书签密的研究逐渐深入，无证书签密体制成为当前密码研究领域的热点之一。无证书签密方案根据其计算基础的不同，可以分为基于双线性对的无证书签密方案［5，8］、基于指数运算的无证书签密方案［3，7］和基于椭圆曲线密码体制（ECC）的无证书签密方案［6］。 由于双线性对的运算时间大于乘法群上的指数的运算时间， 而指数的运算时间又大于ECC 群上的标量乘法运算时间［8］，因此，基于ECC 的签密方案具有较高的计算效率。 陷门哈希函数的概念最早由Krawczyk 和Rabin 提出，用于构造变色龙签名［10］(P143-154)。 很多数字签名方案都基于变色龙签名思想［11］(P355-367)［12，13］。Chandrasekhar 等［14］(P610-618)基于陷门哈希函数提出聚合签密方案，将多陷门哈希函数与可分解的乘法同态ElGamal 加密相结合，提出一种新的有效的聚合签密方案，可以生成常量级的聚合签密文本，从而为多对一的通信场景提供机密性和完整性及身份认证功能。本文基于ECC 及陷门哈希函数，提出一种无证书签密方案。

2 预备知识

2.1 椭圆曲线离散对数问题

定义1 椭圆曲线离散对数问题ECDLP［15］假设E（Fl）是有限域Fl上的椭圆曲线，已知P 是E（Fl）的一个q 阶生成元，当Q∈E(Fl)且Q=aP，求整数a（0≤a≤q-1）。

2.2 CDH 问题

定义2 CDH 问题［16］令q 是群G 的 阶，P 是G的生成元， 给定P，aP，bP∈G， 其中a，b∈Z*q且未知，计算abP∈G。

2.3 陷门哈希函数

陷 门哈希 函 数［10］（P143-154）拥有 哈 希/陷 门 密 钥（HK，TK），其中，哈希密钥HK 是公开的，陷门密钥TK 是私有的。 陷门哈希函数使用一些特殊信息产生固定的哈希值，其抗碰撞性取决于用户对陷门信息（TK）的了解状态［11］（P355-367）。也就是说，仅知道HK时， 很难在消息空间找到两个不同的消息s′和s，以及两个不同的辅助参数u′和u［12］，使得THHK（s，u）=THHK（s′，u′）。 但是，当TK 和HK 都已知时，根据s、s′和u， 很容易计算出u′， 满足THHK（s，u）=THHK（s′，u′）。陷门哈希函数的这一性质可用于构造各种数字签名方案［11］（P355-367）［12，13］。

定义3 陷门哈希函数由四个概率多项式时间(PPT)算法组成［13］：

ParGen: 输入安全参数k， 输出系统公共参数param；

KeyGen: 输入param， 输出陷门/哈希密钥对；

HashGen:输入param，HK，消息s 以及辅助参数u，输出哈希值THHK（s，u）；

TrapColGen:输入param，，s，u 以及新消 息s′≠(s)，输 出u′，使 得THHK（s，u）=THHK（s′，u′）。

3 基于陷门哈希函数的无证书签密方案

3.1 方案构造

3.1.1 初始化

密钥生成中心(KGC)选择两个大素数p 和q，设E(Fp)是有限域Fp上的椭圆曲线y2=x3+ax+b mod p，其中，a，b∈Fp且4a3+27b2≠0。 G 是E(Fp)的一个循环子群，P 是G 的一个q 阶生成元，W1：{0，1}*×G×G →，W2：{0，1}*×G →Z*q，W3：{0，1}*×G →，W4：{0，1}*×G→为安全无碰撞散列函数。

3.1.2 用户密钥生成

用户IDi随机选择秘密值yi， 计算公开参数Yi=yiP，并将秘密值-公开参数对（yi，Yi）通过安全通道发送给KGC。

输入用户标识IDi和公开参数Yi，KGC 随机选择秘密值si， 计算Vi=siP 和βi=si+αW1（IDi，Yi，Vi），并将Vi和βi通过安全通道发送给用户IDi。其中，βi为用户IDi的部分私钥。 用户IDi通过验证βp=Vi+KpW1（IDi，Yi，Vi）等式是否成立，验证部分私钥βi的正确性。

用户IDi的公钥和私钥分 别 为：PKi=（Yi，Vi），SKi=（yi，βi）。

3.1.3 陷门哈希生成

这一部分由用户IDi生成各自的陷门哈希值。输入系统参数param， 用户标识IDi和其哈希密钥（公开密钥）Yi，随机选择辅助参数r∈Z*q，计算陷门哈希值Ti=THYi（IDi，r）=W2（IDi，Yi）Yi-rP，将陷门哈希值Ti公开。

3.1.4 签密

假设消息m 由发送者A 传递给接收者B，则签密过程操作如下：

根据陷门碰撞（即THYA（IDA，r）=THR（C，r′）），计算新辅助参数r′=uW2（C，R）-yAW2（IDA，YA），令H=W4（IDA，TA，r′），计算K=u-（yA+βA）H mod q，则A签密密文为σ=（R，K，C），将（σ，r′）发送给接收者B。

3.1.5 解签密

接收者B 收到发送者A 传递的签密文σ=（R，K，C），进行如下解签密操作:

签名验证:计算hA=W1（IDA，YA，VA），H=W4（IDA，TA，r′））。 如果等式KP+（YA+VA+KphA）H=R 成立，则接受该签名并输出1，否则拒绝该签名并输出0。

解密密文:计算Q′=（yB+βB）R，解密明文m=C⊕W3（IDB，Q′）。

3.2 正确性

上文所提的签密方案的正确性证明过程如下：

3.2.1 陷门哈希碰撞正确性

3.2.2 部分私钥验证正确性

3.2.3 签名验证正确性

3.2.4 密文加解密正确性

4 安全性分析

4.1 机密性

定理1 在随机预言机模型中， 本文方案在适应性选择消息攻击下具有机密性。

证明: 假设算法Z 是CDH 困难问题的解决方案，给定实例(P，aP，bP)，求解目标为abP。建立敌手C 和挑战者Z 之间的游戏，令KP=aP，运行初始化算法，敌手C 进行如下询问:

W1询 问：当C 以（IDi，Yi，Vi）询 问 时，若 存 在（IDi，Yi，Vi，w1）∈Lw1，则Z 返回w1给C；否则，Z 选择w1∈，且（*，*，*，w1）未出现在Lw1中，将（IDi，Yi，Vi，w1）保存在中Lw1， 并返回w1给C。

W2询问：当C 以（IDi，Yi）询问时，若存在（IDi，Yi，w2）∈Lw2，则Z 返回w2给C；否则，Z 选择w2∈，且（*，*，w2）未出现在Lw2中，将（IDi，Yi，w2）保存在Lw2中， 并返回w2给C。

W3询问：当C 以（IDi，Q）询问时，若存在（IDi，Q，w3）∈Lw3， 则Z 返回w3给C； 否则，Z 选择w3∈，且（*，*，w3）未出现在Lw3中，将（IDi，Q，w3）保存在中Lw3， 并返回w3给C。

W4询问：当C 以（IDi，Ti）询问时，若存在（IDi，Ti，w4）∈Lw4， 则Z 返回w4给C； 否则，Z 选择w4∈，且（*，*，w4）未出现在Lw4中，将（IDi，Ti，w4）保存在中Lw4， 并返回w4给C。

公钥生成询问:当Z 接收到C 关于IDi的公钥生成询问时，执行如下操作:若（IDi，Yi，Vi，di）∈LPK，则返回（Yi，Vi）给C。 否则，Z 选取随机数di∈{0,1}，若di=0，则随机选取yi，βi，w1∈Z*q，计算Yi=yiP，Vi=βiP-KPw1，且 满 足（*，Yi，Vi，*）∈/ LPK，将（IDi，Yi，Vi，di）保存到LPK，并返回给C，同时将（IDi，yi，βi）保存到LSK。 若di=1，令Yi=y*P，Vi=v*P，且y*,v*∈，（*，Yi，Vi，*）∈/ LPK， 将（IDi，Yi，Vi，di）保存到LPK，并返回给C。

私钥生成询问: 当Z 接收到C 关于IDi的私钥生成询问时，执行如下操作：若（IDi，yi，βi）∈LSK，则返回（yi，βi）给C。 否则，Z 在LPK中查询相应的（IDi，Yi，Vi，di），若di=0，公钥生成询问中已将（IDi，yi，βi）保存到了LSK， 因此，Z 可直接将LSK中相应的元组（yi，βi）传给C。 若di=1， Z 终止模拟。

公钥替换询问:C选择一个新的公钥（IDi，，，di）替换原始公钥（IDi，Yi，Vi，di）。

陷门哈希生成询问:当C 以（IDi，Yi）询问时，若存在（IDi，Yi，ti）∈LT，则Z 返回ti给C;否则，Z 选择r∈，计 算ti=W2（IDi，Yi）Yi-rP，将（IDi，Yi，ti）保 存在LT中， 并返回ti给C。

签密询问: 当Z 接收到C 关于 （IDI，IDJ，m）的签密询问时，则Z 在LPK中查询IDJ相应的（IDI，YJ，VJ，dJ）执行如下操作：若dJ=1，则Z 终止模拟。 否则，Z 分别对IDI，IDJ进行公、私钥生成询问，获得相 应元组（IDI，yI，βI）和（IDJ，YJ，VJ），生 成 密 文σ=（R，K，C）并返回给C。

解签密询问: 当Z 接收到C 关于（IDI，IDJ，R，K，C）的解签密询问时， 若LPK中存在元组（IDJ，YJ，VJ，dJ），且dJ=0，则Z 分别对IDI，IDJ进行公、私钥生成询问，获得相应元组（IDJ，yJ，βJ）和（IDI，YI，VI），运行解签密算法得到m 返回给C。 若LPK中存在元组（IDJ，YJ，VJ，dJ），且dJ=1，则Z 终止模拟。 若LPK中不存在元组（IDI，YI，VI），则Z 查询（IDI，，，）∈Lw1， （IDI，，）∈Lw2， （IDI，QI，w3） ∈Lw3，（IDI，TI，w4）∈Lw4，计算m=C⊕w3，若等式KP+成立，则返回m 给C。 否则，输出。

挑战:C 输出IDI和IDJ以及两个等长消息m0，m1， Z 查询LPK获得（IDJ，YJ，VJ，dJ），若dJ=0，则终止模拟。否则，令R=bP，随机选择Q∈G，计算C=ms⊕W3（IDB，Q），s∈{0,1}， 随机选择K∈使之满足KP+（YI+VI+KPhI）H=R， 将挑战密文σ=（R，K，C）返回给C。

C 经过询问，输出s′作为s 的猜测，当s′=s 时，Z 输出作为CDH 困难问题的解。

综上， 该方案在自适应消息攻击下具有机密性。

证毕。

4.2 消息验证性

由于在假设CDH 问题是困难的情况下， 没有多项式对手能够伪造有效的消息。 因此，接收者B想要检测消息（IDi，m，Yi，Vi）的有效性和完整性，可以通过检测等式KP+（Yi+Vi+KPhB）H=R 是否成立来判断。 其中，hB=W1（IDB，YB，VB），H=W4（IDA，TA）。故本方案提供身份验证功能。

4.3 密钥托管

本方案的部分私钥βi和部分公钥Vi是由KGC 根据用户标识IDi和公开参数Yi生成的，由于Yi= yiP，KGC 若想从已知的公开参数Yi计算出秘密值yi，需破解ECDLP 问题，故本方案可以有效避免密钥托管问题。

4.4 前/后向安全性

在本方案中，公开参数、部分公钥及加密参数的产生来源于随机产生的参数，即使敌手获得了密文传输过程中的相关参数，但由于随机数具有一定的时间效力，敌手无法根据此次获得的参数分析出以前的密文和相关参数，也无法分析出未来的密文和相关参数，因此，该方案具有前/后向安全性。

4.5 不可否认性

若消息发送者A 对自己签密的消息试图抵赖时，需要公开验证其身份。 由于等式KP+（YA+VA+KPhA）H=R 中包含发送者A 的公钥，消息发送者的身份可以通过任何第三方机构验证，因此，当消息发送者确实签密了某消息，其行为不可否认。

5 性能分析

性能分析分别从通信和计算代价两方面考虑，其中通信效率以密文长度来衡量，计算效率以签名阶段和解签密阶段验证算法的计算量来衡量。 令TSM为椭圆曲线中的标量乘法的时间开销，TE为群上的指数运算的时间开销，TBP为双线性映射运算的时间开销， 其中，1 次乘法群上的指数运算的时间TE大约相当于10 次椭圆曲线点乘运算TSM，1 次512 位的双线性对运算的时间大约相当于10 倍的1 024 位指数运算［8］。 由于群上的加法运算和哈希运算的时间远小于上述运算，所以不考虑这些运算的操作时间。 定义Lm为消息长度，LG为群G 中元素的长度，Lq为中元素的长度。

如表1 所示， 由于双线性映射的时间开销远大于标量乘法和指数运算， 故采用双线性映射的算法［5，8］计算开销较大，计算效率较低。 本文所提出的方案在签密阶段和解签密阶段分别只使用了3次和4 次椭圆曲线上的标量乘法，故具有较高的计算效率。 在通信效率方面，本文所提出的方案基本接近文献［3］但高于其他算法［5-8］，适用于网络带宽资源有限的网络环境。

表1 相关方案性能比较

6 总结

本文利用ECC 和陷门哈希函数构造了一种新的无双线性对的无证书签密方案。该方案提供具有无需密钥托管、可认证性、前/后向安全、不可否认性等安全特性，相较于同类型无证书签密方案，本方案具有较高的计算效率和存储效率， 适合网络通信环境中计算速度、 存储容量及带宽受限的安全应用。