基于GF(2n)椭圆曲线点积改进算法的PKI数据传输模型研究 椭圆曲线算法

摘 要 描述了PKI(公钥基础设施)数据传输模型,对其关键技术与运作模式进行了研究与改进。讨论了数据在传输过程中的安全性问题,分析了椭圆曲线加密算法的核心问题即点积算法,并在此基础上提出了改进。比较了新旧算法的执行效率,得出了新算法执行效率更高的结论,从而实现了数据在网络中的更加安全有效的传输。

关键词 椭圆曲线;点积算法;公钥基础设施

1 引言

在信息安全技术领域里,公开密钥加密技术发展迅速,在此基础上形成发展起来的公开密钥基础设施PKI(Public Key Infrastructure)很好的为互联网以及其相关方面提供了全面的安全服务,PKI技术是目前能够有效全面解决安全问题的可行方案。

传统的文件传输方案中,椭圆曲线ECC加密由于其安全性能高,存储空间小,计算量小,处理速度快而受到大家的推崇,发展前景十分广阔。

提出了一种基于三重比较的改进的PKI传输模型,以及在此基础上对椭圆曲线加密效率进行了研究,有效的增强了数据在网络传输过程中的安全与可信度,进一步提高了数据在加解密过程中的效率。

本文所用到的函数与算法:采用相对安全的哈希函数SHA_1对数据进行散列运算;用对称加密算法3重DES对数据进行加解密;而用于文件传输与验证的非对称加密算法采用日渐流行的椭圆曲线加密算法ECC。

2 PKI简介及模型的设计

2.1 PKI简介

PKI(Public Key Infrastructure)即公开密钥基础设施[1],是通过使用公开密钥技术和数字证书来确保系统信息安全并负责验证数字证书持有者身份的一种体系。它主要通过身份认证、操作的不可否认性、信息传输、存储的完整性和机密性来实现。PKI的核心的是CA,通常也称为PKI/CA。

作为一个安全的数据传输系统,PKI应具有以下功能:

a. 身份认证:即收发双方能够确定相互的身份。

b. 操作的不可否认性:即收发双方对自己的行为具有不可抵赖性。

c. 信息传输、存储的完整性和机密性。即能够确保文件在传输过程中没被篡改,确保文件的安全。

2.2 用户之间数据通信原理

1)用户A 随机选取一个整数 nA,作为自己的私钥,计算 (点积运算), GA 作为自己的公钥。同样,用户B随机选取一个整数nB作为自己的私钥,计算 作为自己的公钥。

2)用户A、B分别用自己的公开密钥 GA 和GB 向认证中心CA申请证书,CA再分别对 GA 和 GB 生成数字签名,记为D(GA ),D( GB ) ,再产生证书 CA= { GA , D(GA ) } 返回给用户A,产生证书 CB= {GB , D( GB) } 返回给用户B。持有证书的用户A,B就可以进行安全的数据通信了。

2.3 数据的编码、加密与解密过程

(1) 编码

用户首先对信息M进行分组,使其成为有限域上的明文信息块 m。

然后将 m经编码嵌入到椭圆曲线上的点 Pm。这种编码不同于加密,任何一个合法用户都可以解码恢复明文。记分组数为 num,约定 0≤num<[p/256]一1,要找到这样的x,使之满足256m< x <256(m+1),且 为 GF(p)上的平方剩余。若找到这样的x,就完成了明文信息的编码阶段。

(2) 发送密文

用户A对经过分组与编码的信息进行加密计算,并发送如下点对给用户B:

=

(3)接受密文并解密

用户B接受到密文,可使用KB 作如下解密运算,恢复出Pm.x。由点积运算的性质,可得:

(4) 解码

得到P 后,去掉点P 的z坐标的最低一个字节,即将Pm.x除以256后取整 ,即可得到明文分组m, 也即: 。

2.4 基于以上理论,设计了一个安全的PKI数据传输模型如图所示[2]:

发送方示意图

用户A向用户B发送数据过程:

1) 用户A随机产生对称加密算法密钥,通过对称加密函数对明文进行加密生成密文(a);其密钥通过非对称加密函数进行加密而生成加密的对称加密密钥(b)。

2) 用户A随机选取散列算法生成散列函数,通过散列函数对明文散列生成数据摘要(c)。

3) 用户A通过证书库得到自己的私钥和用户B的公钥。

4) 用用户B的公钥结合非对称加密函数对用户A的对称加密密钥进行加密(d,e);对用户A的数据摘要进行加密(g)。

5) 用用户A的私钥结合非对称加密函数对数据摘要进行数字签名(f)。

6) 通过对密文、加密的对称加密密钥、加密的数据摘要和数字签名进行打包发送给用户B。

接收方示意图

用户B接收处理数据过程:

1) 用户B接收到从用户A传来的数据包并打开它。

2) 用户B通过证书库得到自己的私钥(a),并通过非对称解密函数对已加密的对称加密密钥进行解密,还原对称解密密钥(b)。

3) 通过对称解密密钥对密文进行解密生成明文( c )。

4) 用散列算法对明文进行散列生成数据摘要1 ( d )

5) 用用户B自己的私钥通过非对称解密密钥对加密数据摘要进行解密,生成数据摘要2 (e )。

6) 用用户B自己的私钥通过非对称解密密钥对数字签名进行解密,生成数据摘要3 (f)。

7) 比较数据摘要1、2、3是否一致,一致则数据完整,否则数据已被篡改。

3 基于PKI模型的ECC加密算法

如上文所述,PKI系统确保通信安全所依赖的是加密算法,其中最要的是非对称加密算法,因此,这个模型的核心就是ECC。ECC的关键问题是如何高效快速的实现ECC算法。提高ECC的效率一直是椭圆曲线密码研究中的一个重要内容。本文在这方面进行了一些探索和尝试。

3.1 椭圆的选取

椭圆曲线指的是由Weierstrass方程[3]:所确定的曲线,在密码学中,人们关心的是一种受限形式的椭圆曲线,本文讨论的椭圆曲线的点积算法就是基于有限域 的。

设K为有限域 ,取K上的椭圆曲线为E: ,其中x,y,a,b∈K,b≠0,则E上的加法运算定义如下:

设P,Q∈E。P,Q≠O(O为无穷远点), ; ,则P的逆元 ,且 。

若Q≠ ,Q≠P,则 ,其中

; ;

若 , P≠q, 则 其中

; ;

特别的,对任意P∈E,P+Q=P,对实数0,0P=O, 则nP=P+P+P…..+P 。

也就是椭圆点P自身加n次。[4]

3.2 椭圆曲线的算法与效率分析

第一种解法:

参考文献[4]给出了计算 P的最基本算法:“加-减”(addition-subtraction)算法J,它是“加-与-倍加”(add-and-double)算法的改进,无需预处理。在仿射坐标模式下,对给定的整数,设P为椭圆曲线 E上的一个随机点,B(n )为给定的任意大正整数的二进制序列,显然n和B(n )可分别表示成如下形式[5]:

(1)

其中, ai∈{0,1},i=0,1,…t-1 于是根据点积定义,nP可写成

(2)

INPUT:大正整数n和椭圆点P

OUTPUT:Q=nP

③for i form k-2 downto 0 do

Else

效率分析:该算法要进行8/31og2n次乘法和4/31og2n次求逆运算,在射影坐标模式下要8/31og2n次乘法。

第二种解法:

对NAF做了改进[6],使得B(n)序列中任3个(或以上)的连续元素中至少有一个为0,再通过对 做预计算来提高运算效率。

① (预先做倍点运算)

②set Q=0,i=0;

③for i from k-1 to 0

④return Q

效率分析:该算法至多做2(k-1)/3次点加法运算,而每次点加法运算仅需要域 上元素的3次乘法,9次加法和一次求逆。比之算法一有了较大的提高。

3.3 改进的算法与效率分析

算法3:

在算法1和算法2的基础上,通过设置合适的窗口长度来减少点加运算次数。以达到提高运算效率的目的[7]。

INPUT: 大正整数n的 表示和椭圆点P

OUTPUT:Q=nP

⑶ while i>=3 do

① 从i 位开始向右搜索连续的0串:

,即

② if i>=3 then

then

⑷ 计算//序列最右边不满4位时直接计算

⑸ return Q

3.4 数据分析

取Koblitz方程 , n=233,窗口长度w=4。分别对算法1,算法2,算法3进行运算比较得如下表:

点积运算nP的效率比较

随机数1 随机数2 随机数3

算法1 0.238 0.489 0.587

算法2 0.234 0.440 0.525

算法3 0.230 0.430 0.510

通过上表可以看出,算法3的确比算法1和算法2在效率上有了较大的提高。

4 总结

文中改进了PKI模型,并对其非对称加密算法ECC的效率进行了比较研究,介绍了它的改进的高效算法,实现了收发双方能够确定相互的身份,收发双方对自己的行为具有不可抵赖性,即能够确保文件在传输过程中没被篡改,确保文件的安全,经验证,此方法是切实可行的。

参考文献

[1]. Carlisle Adams,Lloyd Steve.公开密钥基础设施----概念,标准和实施[M].北京:人民邮电出版社,2001.

[2]. 韦昌法.基于PKI的安全文件传输系统的设计与实现.计算机工程与设计,2006年1月,第27卷第1期,114---116

[3]. Darrel Hankerson、张焕国等译.<<椭圆曲线密码学导论>>[M]p71---p146

[4]. IEEE P1363, Editorial Contribution to Standard for Public KeyCryptography 1998[S].

[5].Montgomery P.Speeding the Pollard and elliptic curve menthods of factiorization[J]. Mathematics of Compututation,1985,48:209-224.

[6].郝林.一种改进的冗余序列算法在椭圆曲线密码体制中的实现.数值计算与计算机应用,2005年3月,74--77.

[7]. 符茂胜. 域上椭圆曲线点积算法的一种改进。

[8]. 李湛.一种改进的椭圆曲线密码实现算法[J]电子科技2004(7):31—33