基于椭圆曲线加密技术实现双向认证的数字签名方案

邓婕 卓碧华

中图分类号：TN918.1 文献标识码：A

摘要：提出一种基于椭圆曲线离散对数问题的数字签名方案。避免将明文信息嵌入到橢圆曲线EP（a，b） 上的实际困难，从而提高了加密的效率；同时将DES、ECC和Hash三种算法有机结合达到数字签名双向认证的效果。

关键词：数字签名；椭圆曲线加密；单向Hash加密

1.引言

RSA公钥密码的安全性基于大整数因子分解这一数学难题，已经在信息安全领域得到广泛的应用。

椭圆曲线公钥密码（Elliptic Curve Cryptography ，ECC）是在20世纪80年代由Miller[1]和Koblitz[2]分别独立提出的，是继RSA之后其安全性得到密码界公认的又一公钥密码。ECC的安全性基于计算椭圆曲线的离散对数这一数学难题。ECC使用较短的密钥可以达到RSA使用较长密码时同样的安全性，因此椭圆曲线公钥密码在运算速度和传输带宽上都有优势，尤其在诸如IC卡、单片机和移动通信等低端环境中，存储资源和计算速度都有很大的限制，椭圆曲线就显得更为合适。

ECC的安全性依赖于给定G和kG的条件下计算出k的困难程度，这被称为椭圆曲线对数问题。取椭圆曲线对数的最快的技术是称为Pollard rho的方法。表一比较了ECC 和RSA的工作效率。我们可以看到，和RSA比较ECC可以用小得多的密钥大小。另外，在密钥大小相等时，ECC 和RSA 所要求的计算工作量差不多。因而，在安全性差不多的情况下，使用较短密钥的ECC比使用RSA具有计算上的优势。

2.数字签名

数字签名由公钥密码发展而来，是实现电子交易安全的核心技术之一，它在身份认证、数据完整性、不可否认性以及匿名性等方面有着重要的应用。

在数字签名协议中，数字签名必须能保证：接收者能够核实发送者对报文的签名；发送者事后不能抵赖对报文的签名；接收者不能伪造对报文的签名。

数字签名的基本原理是：发送者A用自己的私钥d对报文m进行解密（指一个运算动作），将结果D（m）传送给接收者B。B用已知的A的公钥e对密文加密得出E（D（m））=m。因为除A外没有人能具有A的私钥，所以除A外没人能产生密文D（m）。这样，实现了A对报文m的签名。

3.基于椭圆曲线的数字签名

本方案为实现数字签名的目的，它的基本原理是：数据通信之前，进行Hash运算得到信息摘要（因为对整个报文实施加密通常是不切实际的，且对于大的数据分组的使用，像ECC这样的函数可能也太昂贵了。在这种情况下可以采用Hash函数，因为Hash函数具有两个重要特性：①它的输出一般相对较短，通常为128位；②也是更重要的一点，Hash函数具有抗碰撞性，就是说能保证不会有两个不同的数据产生相同的Hash值，即当x≠y是f（x）≠f（y）。因此，攻击者不能根据截获到的真正的散列值，构造出欺骗明文并通过鉴别），然后使用ECC对信息摘要进行数字签名，然后产生一个DES密钥对信息明文和摘要进行加密，同时通过ECC对DES密钥进行加密和实现数字签名。

3.1椭圆曲线的定义

ECC是在1985年由V.Miller[1]和 N.Koblitz[2]分别独立提出的。对于ECC来说我们最关心的是一种受限形式的椭圆曲线，这种椭圆曲线定义在一个有限域（Fp）上 。密码编码学特别感兴趣的是被称为模p椭圆群的对象，其中p（p≥3）是一个素数。这个群的定义如下。选择两个满足下列条件的小于p的非负整数a和b：

4a3+27b2（modp）≠0

那么EP（a，b）表示满足下列条件的模p椭圆群：这个群中的元素（x，y）是满足如下方程的小于p的非负整数另外加上无穷点0：

y2≡x3+ax+b（modp）（1）

我们在这个有限域椭圆曲线E上定义“+”运算，P+Q=R，R是过P，Q 的直线上与曲线的另一个交点关于x的对称点；当P=Q 时，R 是P 点的切向量与曲线的另一个交点关于x 轴的对称点。这样，（E，+）构成可交换群（Abel群），O是加法单位元（零元）。椭圆曲线上的所有点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式mP=P+P+···+P=Q中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题就被称为椭圆曲线上的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来[5，6]。

3.2椭圆曲线加密方案

设E为有限域Fp（p≥3为素数）上的椭圆曲线，选择一个素数p≈2180和方程（1）的椭圆曲线参数a和b，这就定义了点组成的椭圆群EP（a，b）。又设G为EP（a，b）上选定的一个点（称为基点），选择G的重要准则是满足nG=0的最小n值是一个非常大的素数，我们称n为G的阶，且选择的n为一个不等于p的大素数。以eA（1

椭圆曲线加密：

该方案要同时具有认证功能，则它需要利用一个信息认证码HMAC=（T，V）和2个hash函数H1和H2。这里T=T（k，x）是信息认证码的生成算法，它根据输入的密钥k和信息x，输出标签T。V=V（k，x，T）∈{0，1}是信息认证码的验证算法，这里k为密钥，x为信息，T为待验证的标签。当信息可以接受时，V 的输出为1；当信息不能接受时，V 的输出的0。

设用户A欲将明文m加密后发送给B。Hash函数H1和H2的输出为192比特，明文和密钥也都取为192比特。

用户A的加密算法：

①A随机选取整数r∈[1，n-1]，计算R=rG；

②计算D=rPB=（Dx，Dy）；

③将有限域元素Dx作为输入字节串Z，计算K1=H1（Z），K2=H2（Z）；

④计算c=m⊕K1，T=T（K2，c）；

⑤发送（c，R，T）给B。

用户B的解密运算：

①计算D=eBR=（Dx，Dy）；检查D≠0，如果D=0，则输出“无效”且结束。

②将有限域元素Dx作为输入字节串Z，计算K1=H1（Z），K2=H2（Z）

③计算V（K2，c，T），若V=0，则拒绝接受该信息；若V=1，则进行下一步。

④4）计算m=K1⊕c，输出明文m.

在上述算法中，将Z的Hash值K1与明文m进行c=m⊕K1运算，有利于隐蔽Z的特性。而采用信息认证码，一方面得到认证的功能，另一个方面防止了攻击方对密文的篡改，从而攻击者不能利用选择密文攻击法进行攻击。

3.3椭圆曲线的数字签名过程

（1）发送方A准备好要传送的明文信息。

（2）发送方A对信息进行Hash运算，得到一个信息摘要。

（3）发送方A用自己的椭圆曲线加密算法的私钥（SK）对信息摘要进行加密，得到发送方A的数字签名，并将其附在明文信息m之后。

（4）发送方A随机产生一个加密密钥（DES密钥），并用此密钥对要发送的信息（此时要发送的信息中包含明文和发送方的数字签名）进行加密，形成密文。

（5）发送方A用接受方B的公钥（PK）对刚才随机产生的加密密钥（DES密钥）进行加密，将加密后的DES密钥连同密文一起传送给接受方B。

（6）接受方B收到发送方A传过来的密文和加过密的DES密钥，先用自己的私钥（SK）对加密的DES密钥进行解密，得到DES密钥。

（7）然后接受方B用DES密钥对收到的密文进行解密，得到明文信息和数字签名，再将DES密钥抛弃（即DES密钥作废）。

（8）接受方B用发送方A的公钥（PK）對发送方A的数字签名进行解密，得到信息摘要，同时实现了双向认证的效果。

（9）接受方B用相同的Hash算法对收到的明文再进行一次Hash运算，得到一个新的信息摘要。

（10）接受方将收到的信息摘要和新产生的信息摘要进行比较。由于单向Hash函数具有良好的抗碰撞性，所以如果两份信息摘要内容一致，则可以说明收到的信息没有被修改过。

4.结束语

本方案加密和签名过程中，并没有将明文m嵌入到椭圆曲线上的形成可逆的Pm点域，同时也避开椭圆曲线加密的求逆的运算，从而降低了椭圆曲线加密运算的难度；而且对比较庞大的明文信息进行Hash运算，也对庞大的明文信息和签名信息使用速度最快的DES进行加密，且对需要保密的DES密钥和信息摘要则采用强度较高的ECC进行加密，这样可以充分发挥Hash、DES和ECC各自的长处，在不降低安全性的情况下，大大节省了加密的时间和加密的效率，并达到相互认证的效果。