基于椭圆曲线的签密方案

崔文军 贾志娟 胡明生* 公 备 王利朋

1(郑州师范学院信息科学与技术学院 河南 郑州 450044)2(北京工业大学计算机学院 北京 100124)

0 引 言

随着计算机等网络通信设施的高速发展与应用，信息安全已然成为当今社会重要的研究热点之一，其中应用于数据传输、存储和身份认证的安全加解密算法，对构建安全平稳的网络环境有着至关重要的作用。

自公钥密码学出现以来，是否可以以安全和认证的方式传递任意长度的消息，且所耗代价低于传统的“先签名后加密”，这个疑问到20世纪90年代似乎从未得到过解决。幸运的是，Zheng[1]找到了一种名为“签密”的新加密方案，它既能够满足数字签名又可以公钥加密，且成本远低于“先签名后加密”。随后，大量科研工作人员对各类相关方案进行了学习和研究。文献[2]改进了Zheng的方案，使得接受者不再需要私钥进行签名验证，并且任何人仅仅使用发送者的公钥便可验证方案，也就是说方案具有了公开验证的性质，但其不具备前向安全性。文献[3]借助离散对数问题思考了一个具有前向安全性的签密方案，但不具备公开验证的性质。文献[4]借助双线性对给出了一个基于身份的签密方案，而后证明了该方案在BDH问题难以解决的前提下是安全的。文献[5]展现了一个既可以满足前向安全性又满足公开验证性的签密方案，并基于求解离散对数的困难性问题和CDH问题困难性证明了方案具备安全性。文献[6]基于求解离散对数问题的困难性和Hash函数的单向性提出了一个新的签密方案，通过将参数r隐藏在指数位置(即R=gr)，使得攻击者即便获取了发送者的私密钥也不可能获得此次以及之前的秘密信息，即证明了方案具有前向安全性。当发送方与接收方发生纠纷时，接受方便可交由第三方进行验证，仅需公开签名和明文消息的哈希函数，这样就保护了明文消息，达到了公开验证的目的。文献[7]对Zheng的方案进行了研究和改善，改进后的方案主要包括两次加解密运算和五次模指数运算，而后给出了一个基于ECC的签密方案。文献[8]详细分析了文献[7]的方案，指出其数字签密方案并没有前向安全性且提出的椭圆曲线数字签密方案复杂度过高，并针对这两个问题做出了改进，使得椭圆曲线数字签密方案摒弃模指数与模逆计算，依靠模乘运算，计算量有了较大幅度减少。基于DL和CDH问题的困难性，文献[9]利用双线性对设计了一个无证书的签密方案，并进行了有效性、不可伪造性和效率分析。由于签密长度较短，该方案能较好适应计算能力受限的环境。在BDH和CDH问题困难性的假设下，由于公钥签密不能处理任意长度的消息，文献[10]在随机预言模型下，设计了一个无证书混合签密方案，并证明了相关的安全性。文献[11]对最近提出的六个签密方案分别设计了密码学方面的改进，指出六个方案均不能满足方案的保密性，详细分析了文献[9]方案，对其保密性和不可伪造性给出了相关方面的攻击，并证明了改进的措施安全性。文献[12]提出了一种无双线性映射的高效无证书签密方案，基于CDH假设和DL困难性问题，验证了该方案具有不可伪造性、机密性、不可否认性和公开验证性等优良的安全性质。文献[13]结合了混合签密和环签密的优势，采取KEM-DEM机制生成了对称密钥，并基于离散对数问题和计算性DH问题，证明了方案具有不可伪造性和机密性。文献[14]给出了一个无Hash函数的签密方案，并证明了该方案具有抗伪造性、前向安全性和公开验证性等性质。文献[15]设计了一种基于椭圆曲线的前向安全的签名方案，该方案不仅可以抗随机数攻击，而且具有前向安全性。该方案比ECDSA方案少了1次倍点运算、2次模乘运算和2次模逆运算，运算量较小。文献[16]对一种基于椭圆曲线前向安全数字签名方案进行了分析，指出了其安全性漏洞并给出具体攻击方法。

1 预备知识

1.1 有限域上的椭圆曲线[17-18]

一般来说，称形如E：y2+a1xy+a3y=x3+a2x2+a4x+a6的方程为椭圆曲线的曲线方程，其中a1，a2，a3，a4，a6∈域K。其中，基于有限域Zp上的椭圆曲线方程为：

y2=x3+ax+b

(1)

基于有限域GF(2m)的椭圆曲线方程为：

y2+xy=x3+ax+b

(2)

ECC的域参数为(q,a,b,G,n,h)。其中q为素数p或q=2m。常用的椭圆曲线是非奇异的，即4a3+27b2≠0。G是椭圆曲线上的基点，n是点G的大素数阶，即n是满足nG=0的最小正整数。h是一个有椭圆曲线的阶除以n产生的余因子，且h≤4。

1.2 椭圆曲线离散对数问题

1.3 汉明距离[19]

用d(x,y)代表汉明距离，它表示相同长度的字符串x和y对应位置上不同字符的个数。

1.4 Hash(哈希)函数[17, 20]

Hash函数可以说是一种压缩映射。不论消息串的长度大小，均可被映射成较短定长的消息串。具体性质如下：

(1) 正向计算简单性：对于Hash函数h和消息x，计算h(x)是极为简单的；

(2) 逆向计算困难性(也称单向性)：对给定的任意值y，求解h(x)=y中的x是困难的。

2 文献[6]方案

2.1 初始化

2.2 签 密

加密：

c=EK(m)r=h(h(m),yb,gkmodp)R=grmodps=k(r+xa)-1modq

A将消息m签名为(c,R,s)，并将其发送给B。

2.3 解 密

B收到A的签名后，进行如下解密计算：

K=h((yaR)sxbmodp)

解密：

m=DK(c)

签名验证：

R=gh(h(m),yb,(yaR)smod p)modp

若签名验证通过证明签名有效，则B接受明文消息和来自A的签名。

2.4 方案分析

文献[6]方案主要依赖于求解离散对数问题的困难性和Hash函数的单向性。通过将参数r隐藏在指数位置(即R=gr)，使得攻击者即便获取了发送者的私密钥也不可能获得此次以及之前的秘密信息，即证明了方案具有前向安全性。当发送者与接收者发生纠纷时，接受者便可交由第三方进行验证，仅需公开签名和h(m)，这样就保护了明文消息，达到了公开验证的目的。或者在签解密的过程及公开验证阶段，用密文c代替h(m)，避免一次哈希运算，提高计算效率和速度。在方案设计过程中，用到了大量模指数运算，和一次模逆运算，导致运算代价高昂，费时费力。如果能在摒弃模指数和模逆这样高代价运算的前提下实现方案的可公开验证性和前向安全性，这样的方案更值得推广和应用。

3 文献[8]方案

3.1 初始化

3.2 签 密

R=rG=(r1,r2)

KAB=ryB=(k,l)

加密：

c=Ek(m)

Hash函数值e=h(m,r1)，汉明重w=ham(e)。

(2) 随机取整数α,β(0<α,β

u=(r-αr1-βm)modn

s=(w+αr1+xA)modn

签密为(c,R,s,β,u)，将签名发送给B。

3.3 解 密

收到A的签名后，B进行如下解密计算：

KAB=xBR=(k,l)

解密：

m=Dk(c)

Hash函数值e=h(m,r1)，汉明重w=ham(e)。

接着再计算：

γ=(s-w+βm+u)modn

验证等式：

γG-yA=R

若正确，则接受签密。

3.4 方案分析

由于椭圆曲线的签解密算法具有密钥长度和签名长度短的优势，使得椭圆曲线有着较广的应用。相较于文献[6]方案，文献[8]方案是基于求解椭圆曲线离散对数问题的困难性进行签解密设计的。其在满足公开验证性和前向安全性的基础上，模指数与模逆运算0次，且主要用到了模乘运算。方案计算速度和效率有了大范围提高，计算量达到了较小范围。若对该方案进行改进，降低模乘运算的次数是主要的研究方向之一。

4 方案设计

文献[6]方案在签解密过程中用到了模指数和模逆运算，导致运算成本高、复杂度大、代价高昂。文献[8]方案模指数与模逆运算0次，主要用到了模乘运算。本文在文献[8]方案的基础上进行改进，降低模乘运算的次数是主要的研究方向。本方案借助于求解椭圆曲线离散对数问题的困难性、Hash函数单向性和汉明距离等密码学知识进行签密，待收到签名后进行解密，并验证等式βG-wA=R的成立性。整个方案保证了正确性和安全性，同时具备一些优良性质。签解密过程中主要用到了模乘运算，通过效率分析可知，本文方案在签密过程中比文献[8]方案少了一次模乘运算，签密长度少|n|。故本文方案在理论上达到了复杂度最小化。

4.1 初始化

4.2 签 密

R=rG

K=rwB=(k1,k2)

加密：

c=Ek1(m)

Hash函数值e1=h(c,k2)。

此时任选与e1等长的e2，计算：

d=d(e1,e2)

(2) 随机取正整数t(t

α=r+d+xA-tcmodn

签密为(c,R,e2,t,α)，并将其发送给B。

4.3 解 密

(1) 接受者B收到(c,R,e2,t,α)后，计算：

K=xBR=(k1,k2)

解密：

m=Dk1(c)

Hash函数值e1=h(c,k2)，汉明距离d=d(e1,e2)。

(3) 计算：

β=(α-d+tc)modn

验证等式：

βG-wA=R

若验证等式正确说明签名有效，则B接受明文消息和来自A的签名。

5 方案分析

5.1 正确性证明

βG-wA=(α-d+tc)G-xAG=

(r+d+xA-tc-d+tc-xA)G=

rG=R

上述说明此方案的验证过程正确。

5.2 安全性分析

5.2.1抗私密钥攻击

攻击者获取签名(c,R,e2,t,α)后，想要恢复明文消息m首先需获知k1(由于m=Dk1(c))。而获取k1的途径有两种。第一种途径是获知接受者B的私密钥xB，通过K=xBR=(k1,k2)得知。但由wB=xBG求解私密钥xB等同于求解椭圆曲线离散对数问题，显然这是不现实的。这样便可实现抗私密钥攻击。第二种途径可详看前向安全性的证明。

5.2.2不可伪造性

若对签名进行伪造，主要有两类人，一是除B之外的攻击者，二是B本人。

(2) 由解密过程可知，接受者B伪造签名，此时接受者B知道的信息有m、c、R、d、t、α。对于签密方程α=r+d+xA-tc，若通过R=rG解出r等同于求解椭圆曲线离散对数问题，显然是不可能的。一个方程含有两个未知量r和xA(A的私密钥)，故无法求解签密方程。

综上，任何攻击者均无法对签名进行伪造。

5.2.3前向安全性

若发送者A的私密钥xA被攻击者获取，本方案保证了除接受者B可以得知消息明文m外，其余攻击者均无法恢复m。这主要体现在获取解密密钥k1上(由于m=Dk1(c))。而获取k1的途径有两种：

(1) 由K=rwB=(k1,k2)可知需要知道r(wB是接受者B的公开钥)。而R=rG，想要解出r等同于求解椭圆曲线离散对数问题。

(2) 由K=xBR=(k1,k2)可知需要知道接受者B的私密钥xB。

综上，不论是获得r还是xB，对于攻击者来说都是不可能的。

故本方案具有前向安全性。

5.2.4不可否认性

即本方案满足公开验证性。当矛盾出现时，即发送者A否认签密，接受者B可将签名(c,R,e2,t,α)提供给第三方可信中心进行解签密证实。第三方在安全可信的基础上证实A确定发送过该消息，这样便达到了不可否认的目的。验证过程中只是对密文c进行公开验证，保护了明文消息m。因此，本文方案具有一定的保密性。

5.3 效率分析

最新能够同时保持前向安全性和可公开验证性两种性质的签密方案即为文献[6]和文献[8]方案。由表1可知，文献[6]方案是基于求解Zp上离散对数问题的困难性进行设计的，虽保障了安全性，但在签密的过程中主要依靠模指数和模逆运算，导致方案运算成本大，不太适用于广泛应用。本文方案与文献[8]方案是基于求解椭圆曲线离散对数问题的困难性进行签密的，主要用到了模乘运算。但本文方案在签密过程中比文献[8]方案少了一次模乘运算，签密长度少了|n|。因而，本文方案运算量有了大幅度减少，加快了计算效率和速度，在理论上达到了复杂度的最小值。

表1 三种方案效率比较

6 结 语

本文借助于求解椭圆曲线离散对数问题的困难性设计了一个签密方案。已有的多数方案不能同时提供前向安全性和可公开验证性两种性质。文献[6]方案和文献[8]方案具备了这两种性质。本文先对文献[6]方案进行分析，发现文献[6]方案中用到了模指数和模逆运算，这样导致计算成本高、复杂度大、代价高昂，故而进行广泛推广不太适用。由于椭圆曲线的签解密算法具有密钥长度和签名长度短的优势，使得椭圆曲线有着广泛应用。文献[6]方案是基于求解椭圆曲线离散对数问题的难度而设计的。该方案运用模乘运算进行方案的设计，使得方案具备了公开验证性和前向安全性，且模指数与模逆运算0次。对该方案进行改进，降低模乘运算次数是主要的研究方向之一。针对此问题，设计了本文方案。本文方案将签密过程与求解椭圆曲线离散对数的困难性和哈希函数的单向性相结合，能够同时满足前向安全性和可公开验证性，安全性高，且签密过程中仅用到了模乘运算，运算速度快。正确性证明部分说明了本方案的验证过程是正确的。通过验证等式βG-wA=R的正确性，说明接受者收到了来自发送者的签名。针对方案的不可伪造性，本文主要分两部分进行分析，一是除接受者之外的攻击者进行伪造签名，二是接受者伪造签名。通过分析得知任何攻击者(包括B)均不能对签密进行伪造。对于前向安全性，本文假设了发送者的私密钥被攻击者获取，但最终除接受者外其他任何人都得不到消息明文。这主要体现在获取解密密钥k1上，本文进行了两种情况的分析，分别是签密和解密阶段对于解密密钥的获取。由于方案的验证过程需要的是密文消息，这样就可以保证了明文消息的机密性，进而体现出方案可公开验证性的性质。最后，本文方案进行了效率分析。分析表明，本文方案模指数与模逆运算0次，在签密过程中比文献[8]方案少一次模乘，且签密长度少了|n|。因而，本文方案运算量有了大幅度减少，加快了计算效率和速度，在理论上达到了复杂度的最小值，有着较广的应用性，为签密技术在网络通信等安全领域提供了一定的理论基础。

同时，签密技术在各个领域已经得到了广泛的应用，如防火墙[21]和电子现金支付[22]等。安全的签密技术可以实现信息的保密传输和生成签名的身份认证，保障交易过程安全进行。在物联网、云计算等相关领域，如在无线传感器网络中，利用签密技术进行密钥分发和节点的可信认证，具有广泛的应用前景。随着计算机技术的发展，利用求解椭圆曲线离散对数的困难性，设计更加优化安全的算法，减少密钥长度，仍有很多的工作要做。