圆锥曲线密码体制（通用7篇）
圆锥曲线密码体制 篇1
引言
互联网的普及,使得网上电子数据交换大量增加。与此同时,信息的安全问题也显得至关重要。目前各方通常综合采用加密等技术作为确保网络安全的手段,根据密钥类型的不同,现代密码技术分为两类:对称加密系统和非对称加密(公开密钥加密)系统。当前安全有效的公钥密码体制主要有RSA体制,ElGamal体制和椭圆曲线加密体制(ECC体制)。1985年,由Neal Koblitz和Victor Miller提出的椭圆曲线密码体系,其安全性建立在椭圆曲线离散对数的难解性的基础上,在同等密钥长度的条件下其安全远高于RSA算法和其它算法,在网络安全领域有着广阔的应用前景。
一、椭圆曲线基本描述
1.1 椭圆曲线的定义
椭圆曲线的定义,最常用的是Weierstrass方程:
一条椭圆曲线是在射影平面上满足方程上所有点的集合,且曲线上的每个点都是非奇异(或光滑)的。
椭圆曲线在射影平面上有一Z=0的点(0,1,0),我们称其为无穷远点,记为O。令x=X/Z,y=Y/Z,则(1)式为:
椭圆曲线(2)可以限制为如下形式:
,为定义在有限域FP(P为大素数)上的椭圆曲线。
1.2 椭圆曲线的运算规则
椭圆曲线加法的运算规则是:一条直线与椭圆曲线相交,所有交点的和为O。在特定的加法运算下,椭圆曲线上的点集构成一个Abel群。定义如下加法运算:设P,Q,R∈E。
(1)O+P=P,且P+O=P;
(2)-O=O;
(3)如果P(x1,y1)≠O,则-P=(x1,-y1);
(4)如果Q=-P,则P+Q=O;
(5)如果P≠Q,Q≠O,Q≠-P,令R表示直线PQ(若P≠Q)或E在P点的切线(若P=Q)与椭圆曲线E的另一个交点,则P+Q=-R。
当P=Q时,P+Q=P+P=2P,此时称为倍点运算,倍点运算是点加运算的特例。给定一个整数k和椭圆曲线的点P,将P加到自身k次,记为kP,称为椭圆曲线上的点的数乘运算。
椭圆曲线可以用参数集T={p,a,b,G,n}来表示,其中p,a,b含义如上描述,G是在椭圆曲线中所挑选的基点,n是G的阶,其值是一个非常大的数,是满足nG=O成立的最小正整数。
1.2 椭圆曲线离散对数问题
根据椭圆曲线的数乘的定义,可以找到一个点P∈E(Ep),满足k∈Fp,kP=P+…+P(共有k个P)。若存在椭圆曲线上的另一点Q≠P,满足方程k P=Q。椭圆曲线离散对数(ECDLP)问题就是在已知P,Q的情况下求k的过程,即k=logpQ[1]。
已知k和P计算Q比较容易,而由Q和P计算k则比较困难,至今没有有效的方法来解决这个问题,这就是椭圆曲线加密原理所在。椭圆曲线离散对数问题是比整数因子分解问题难得多的数学难题,从这种意义上看,椭圆曲线密码系统是目前安全性较高的公钥密码系统。
二、椭圆密码体制的应用
椭圆曲线密码体制的应用主要有加密/解密、数字签名等领域。
2.1 加密/解密
为方便于椭圆曲线密码体制的计算,需要把明文嵌入作为曲线E中上的一个点,也就是对明文信息的编码。如果明文较长,可分段处理[2]。现在我们描述一个利用椭圆曲线进行加密通信的过程:
假设A向B进行加密传输,首先把发送的报文m编码成椭圆曲线上的一个点Pm椭圆曲线参数为T={p,a,b,G,n}。
(1)选取椭圆曲线Ep(a,b)和基点G。A在区间[1,n-1]中随机选取一个整数nA作为私钥保存,B随机选取一个整数nB作为私钥保存,并分别产生自己的公钥PA=nA×G,PB=nB×G。
(2)A随机选取一个正整数k,并产生密文Cm={k G,Pm+kPB},在这里,A使用了B的公钥。
(3)B接到密文{kG,Pm+kPB}要解密,需做以下运算:Pm+k PB-nB(k G)=Pm+k(nBG)-nB(kG)=Pm+k(nBG)-k(nBG)=Pm。
2.2 基于椭圆曲线数字签名
定义椭圆曲线Ep(a,b)和基点G,n是G的阶。建立密钥对(d,Q),其中d为私钥,Q=dG,Q是公钥予以公开。
A向B发送签名信息M时,签名过程如下:
(1)将消息M代入Hash函数,如MD5或SHA-1,计算消息M的摘要e=H(M)。
(2)在区间[1,n-1]中随机选取一个整数k。
(3)计算R=kG。
(4)计算r=Rx mod n(Rx是R的横坐标),若r=0,则返回(2)。
(5)计算s=k-1(e+rd)mod n,d为A的私钥,若s=0,则返回(2)。
(6)A把消息签名(r,s)传送给B。
B收到签名(r,s)后,对签名进行验证:
(1)验证r和s,是不是在[l,n-1]内的正整数,如果不是,则(r,s)不是有效的签名。
(2)获得A的签名公钥Q,利用A和B相同的Hash函数,计算消息M的摘要,e=H(M)。
(3)计算w=s-1 mod n。
(4)计算u=ew mod n。
(5)计算v=rw mod n。
(6)计算T=uG+vQ。
(7)如果T=O,则拒绝签名;否则计算v=Tx mod n(Tx是T的横坐标)。
(8)如果v=r,则A对消息M的签名被验证通过,否则拒绝此签。
该签名方案在抗攻击性安全强度、处理速度、密钥尺寸、计算开销与带宽需求等方面中具有一定的应用优势。
三、椭圆曲线安全性分析
安全性是所有密码体制的核心问题,ECC是建立在求椭圆曲线离散对数困难基础之上的,它的安全性依赖于椭圆曲线离散对数问题(EDLP)的安全性,椭圆曲线是目前最流行的公钥体制之一,所以对它的攻击也成了当前密码学研究中的一个热点。
3.1 特殊曲线攻击
1. MOV攻击
1991年Menezes,Okamoto和Vanstonel[3]给出了一种将ECDLP归约为有限域上离散对数问题,这种方法可以采用指数计算法,但它只适用于超奇异椭圆曲线,对不是超奇异椭圆曲线的曲线则无能为力。
2. Smart方法
q是素数,对定义在Fq上且E(Fq)=q的椭圆曲线E被称为“畸形”(Anomalous)曲线。Smart在1988年提出了一种能够在O(lnq)时间内求解这类曲线的方法[4]。Smart方法就是构造了E(Fp)到Fp的加法群的一个同构映射,使在多项式时间内可求解这类ECDLP。
3.2 一般曲线攻击
1. 大步小步法
1978年以前求解ECDLP最好算法是Shanks的大步小步(Baby step Giant step)算法[5]。设阶为n,这一算法的时间复杂度为,空间复杂度也为。该算法是对“穷搜索”法在时间和空间上的折衷。
2. Pohlig一Hellman算法
这个算法是由Pohlig和Hellmna提出的[6],实质上是一种演化算法。它的最大功能是能够将阶为n的有限群上的离散对数问题演化为阶为n的一个素因子的循环群上的离散对数问题。设阶为n,Q=mP,并设n的标准素因子分解式是,然后对每一个求出m mod,最后由中国剩余定理可求出m。因此为了抗击这种攻击,阶n必须包含大的素因子,而最理想的情况是n本身就是一个素数。
3. Pollard
方法
1978年Pollard提出了一种概率求解的方法[7],其时间复杂度大约是,与Shanks的大步小步法相当,但空间复杂度仅为O(l)。后来又提出如何将Pollard算法分为r个进程并行处理,则时间复杂约为。目前分布式Pollard算法是已知的对一般椭圆曲线离散对数最好的攻击方法。攻击者利用Pollard算法攻击的途径有硬件攻击(Hardware Attacks)和软件攻击(Software Attacks)。
3.3 椭圆曲线与其它加密体制的安全性比较
当前安全有效的公钥密码体制主要有RSA体制和ECC(椭圆曲线密码)体制等。RSA是目前使用最广泛的公钥加密算法,其安全性建立在大整数素因子分解困难的基础之上。但是随着大整数分解和计算机并行处理技术的发展,当前采用的公钥体制必须进一步增长密钥才能实现相对的安全性。而这样将使其更加复杂、速度更慢。
椭圆曲线引入到密码学体系以来,逐步成为一个流行的公钥密码体制,这种密码体制的引人之处在于安全性较好的前提下,可以使用较短的密钥。椭圆曲线资源丰富,同一个有限域上存在着大量不同的椭圆曲线,这为安全性增加了额外的保证,也为软硬件实现带来了方便[7]。
下表列出了RSA和ECC在安全强度相同情况下的密钥长度对比。
相对于RSA等其它公钥加密系统,椭圆曲线的离散对数计算更为困难。并且,与其他公钥密码系统相比,椭圆曲线密码(ECC)系统具有安全性高、计算负载小、密码尺寸短、速度快、占用带宽少等优点。其将逐步取代RSA密码系统,成为公钥密码系统的主体已经成为趋势。
四、结束语
椭圆曲线密码系统是建立在椭圆曲线理论基础上的公钥密码系统,该系统的安全性已经被公认。在理论的突破和技术的更新下,相信椭圆曲线密码体制的实现会加快,也更适合当今电子商务、电子政务和智能卡等需要安全和快速反应的发展潮流,其应用前景也更加广泛。
参考文献
[1]庞闻.ECC算法在数字签名中的应用[J].渭南师范学院学报,2006,2,41-43.
[2]户占良,张建林.椭圆曲线密码体制的应用和研究现状[J].乐山师范学院学报.2006,12,99-101.
[3]A.Menezes,T.Okamoto,S.Vanstone.Reducing elliptic curve logarithms to logarithms in a fi nite fi eld.IEEE Transactions on Information Theory,1993,volume39,Pages1639-1646.
[4]N.Smart.Announcement of an attack on the ECDLP for anomalous elliptic curves,1997.
[5]Shanks.D.Five number theoretical algorithms.Proc,2nd Manitoba Conference on Numerical Math,(Cong resses Nu merantiu m V II,Un iv.Man itoba Winnipeg),1972:353-356.
[6]白永志.基于椭圆曲线密码系统的数字签名研究与应用[D].2005,19.
[7]陈恭良.信息安全数学基础.清华大学出版社[M],2004:133-205.
圆锥曲线密码体制 篇2
一、椭圆曲线密码体制
椭圆曲线加密法ECC(Elliptic Curve Cryptography)是一种公钥加密技术,以椭圆曲线理论为基础,利用有限域上椭圆曲线的点构成的Abel群离散对数难解性,实现加密、解密和数字签名,将椭圆曲线中的加法运算与离散对数中的模乘运算相对应,就可以建立基于椭圆曲线的对应密码体制。椭圆曲线是由下列韦尔斯特拉斯Weierstrass方程所确定的平面曲线:
椭圆曲线加密算法以其密钥长度小、安全性能高、整个数字签名耗时小,使其在智能终端应用中有很大的发展潜力,比如掌上电脑、移动手机等都能有更好的表现。而在网络中,ECC算法也保证了其协同工作的实时性,使用ECC算法加密敏感性级别较高的数据(如密钥),速度上能够满足大数据量要求,而且安全性高,能很好地保障系统的安全。
由于椭圆曲线密码体制的安全性只与椭圆曲线的安全性有关,而椭圆曲线安全性是由ECDLP求解的困难性决定的,因此,为了保证ECDLP是难解的,在选取椭圆曲线的时候除了选择合适的参数(a,b),使得相应的Weierstrass方程满足非超奇异椭圆曲线的要求外,还要选取合适的有限域GF(q),使得q满足#E能被一大素数(≥30位的整数)整除,或q本身就是一个大素数。安全的椭圆曲线也就是能抵抗各种已有攻击算法攻击的椭圆曲线。
1. 选取安全椭圆曲线时应该遵循的一些原则
(1)E选用非超奇异椭圆曲线,而不选取奇异椭圆曲线、超椭圆曲线以及反常椭圆曲线;
(2)#E不能整除qk-1,1≤k≤20;
(3)当q=P为素数时,#E应为素数,随机选取椭圆曲线上的一点作为基点;当q=2m时,#E应包含大的素因子,如#E=2n,4n,其中的n是大素数,且m不取合数。随机选取E上一阶为n的点作为基点;
(4)选择以基点生成循环子域H∈GF(q)上实现ECC,|H|是#E的最大素因子。
2. 描述一个利用椭圆曲线进行加密通信的过程
(1)用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点作为基点G,选择一个私有密钥k,并生成公开密钥K=k G;
(2)用户A将Ep(a,b)和点K,G传给用户B;
(3)用户B接到信息后,将待传输的明文编码到Ep(a,b)上一点M,并产生一个随机整数r(r
(4)用户B将C1、C2传给用户A;
(5)用户A接到信息后,计算C1-k C2,结果就是点M。
因为C1-k C2=M+r K-k(r G)=M+r K-r(k G)=M,再对点M进行解码就可以得到明文。
在这个加密通信中,如果有一个入侵H,他只能看到Ep(a,b)、K、G、C1、C2而通过K、G求k或通过C1、C2求r都是相对困难的。因此H无法得到A、B间传送的明文信息。基于椭圆曲线的密码体制如图1所示。
二、基于椭圆曲线密码体制的网络身份认证系统
由于网络具有信息量大的特点,其主要威胁来自于非授权用户的非法访问,因此它对数据完整性的要求很高,需要最快的速度提供最高的安全性,保证信息的机密性、完整性和有效性。网络身份认证是依靠用户账号、口令或者生物特征等信息来实现的,这些认证方法在某种程度上存在着安全隐患,如账号、口令或指纹特征信息在存储、传输过程中可能被截取、被篡改等。在身份认证系统中,起关键作用的是其中的加密体系。本文设计的身份认证系统中,用户首先要通过认证模块进行注册,注册成功后,获得经过系统认证中心C A签名的公钥和私钥。用户公钥和CA的公钥都是公开信息,用户的私钥只有用户本人知道,由用户自己保存。
1. 系统的总体结构
假设通信的是A与B双方,A与B处在同一个网络中,文本加解密采用对称算法AES,而密钥的传输与签名验签都采用非对称算法ECC。系统由服务器和客户端两部分组成,如图2所示,服务器端包括代理服务器、认证服务器、应用服务器;客户端包括代理客户端、认证客户端。代理客户端和代理服务器共同完成代理功能,认证客户端和认证服务器共同完成身份认证功能。
系统模型主要工作流程如下:
(1)将用户信息存放在系统数据库中;
(2)客户端应用程序通过客户端代理向认证模块请求申请登录认证;
(3)认证模块检查用户身份并完成认证过程,向客户端发放应用服务器的Ticket;
(4)客户端向安全代理服务器请求获取访问策略数据;
(5)安全代理服务器读取访问控制表中对应的策略控制记录,确定用户是否有权限访问相应的应用服务器资源;
(6)确定用户有权访问后,连接到相应的应用服务器;
(7)客户端与应用服务器间建立起了一条加密通道,双方通过此通道来交换数据。
2. 系统功能模块及实现
(1)认证模块。认证模块主要实现身份认证、密钥分发等功能,采用基于公钥密码体制的改进Kerberos认证协议来对用户进行身份认证,是模型的核心部分。
认证模块由认证客户端模块、认证服务器端模块组成。当客户端代理接到来自客户端的任意请求时,先判断是否为客户端代理启动后接收到的第一个请求,如果是,则客户端代理必须先去认证服务器进行身份认证。
(1)认证客户端。认证客户端主要包括六个模块,分别为:A S请求模块、TGS请求模块、GSSAPI接口模块、Kerberos GSSAPI模块、票据列出模块、票据销毁模块。
AS请求模块主要功能是用户获取TGS的票据TGT。当用户进行身份认证时,AS请求模块被调用,从AS服务器中获取TGT。AS请求模块包括获取Ticket模块和报错子模块。通过调用ECC加密模块,对每条信息进行必要的安全处理;TGS请求模块主要用于获得应用服务器的票据。在调用TGS请求之前,客户端必须己经得到TGT,以便用TGT向TG服务器证明自己的身份。GSSAPI接口模块用于实现与客户端代理的接口,客户端代理调用GSSAPI接口模块来进行身份认证;Kerberos GSSAPI模块被GSSAPI接口模块调用,真正实现建立安全上下文,报文保护级别协商以及对每条报文的保护。通过调用Kerberos GSSAPI模块,用户获得与代理服务器进行加密通信的会话密钥。票据列出模块用于列出保留在缓存中的主要实体名和当前所有活动票据的内容。票据销毁模块用于销毁所有的票据,以防止他人窃取票据,当用户断开与服务器的连接时,系统会调用该模块来销毁用户的票据。
(2)认证服务器。认证服务器模块主要包括KDC模块、GSSAPI接口模块Kerberos GSSAPI模块以及其他辅助模块。
KDC模块主要完成用户身份认证和票据分发等功能,包括AS请求处理子模块和TGS请求处理子模块。它与认证客户端的AS请求模块和TGS请求模块一起工作,来完成身份认证和票据分发功能;GSSAPI接口模块用于实现与代理服务器的接口,代理服务器调用GSSAPI接口模块来进行身份认证,而GSSAPI接口模块则调用Kerberos GSSAPI,用于真正实现建立安全上下文,报文保护级别协商以及对每条报文的保护。
(2)代理模块。代理模块在模型中主要实现客户端应用程序通过代理客户端、代理服务器访问应用服务器的功能,通过采用Socks5协议实现。
代理模块分别在客户端和应用服务器端加载一个代理软件。客户端代理接受客户端的所有请求,经处理后转发给服务器端代理。客户端代理首先与代理服务器建立一个TCP连接,通常SOCKS端口为1080,通过安全隧道,代理服务器认证并接受所有来自客户端软件的通信。若身份得以认证,则安全服务器将请求递交应用服务器,处理请求后并将结果返回安全服务器,安全服务器将此结果返回给客户端。
安全代理服务器在确认客户端连接请求有效后接管连接,代为向应用服务器发出连接请求,安全代理服务器应根据应用服务器的应答,决定如何响应客户端请求,代理服务进程应当连接两个连接,客户端与代理服务进程间的连接、代理服务进程与应用服务器端的连接。为确认连接的唯一性与时效性,代理进程应当维护代理连接表或相关数据库。安全代理服务器为所有网络通信提供了一个安全隧道,在建立通道的过程中,存在用户认证的过程。用户经过认证和原始协议请求,通过GSSAPI建立的安全隧道传送。
(3)加密模块。加密模块在系统中主要完成对数据的加解密处理,通过调用椭圆曲线加密算法具体实现。模型中采用ECIES加解密方案,具体实现过程采用bor Zoi算法库。bor Zoi是个免费的C++椭圆曲线加密库,含有完整的源代码,提供了定义在特征值为2的有限域上的算法,提供了加密模块。
三、系统安全性分析
系统提供了应用层的安全解决方案,可作为网络的授权访问控制中心,提供用户到应用服务器的访问控制服务。基于椭圆曲线加密法的网络身份认证,用户可以采用较短的密钥长度来实现较高的安全性,这样既有便于用户的记忆也提高了服务器的计算速度,从而将大大缩短登录时间。在椭圆曲线密码体制中,椭圆曲线Ep(a,b)中p、a、b的任何一个数字改变就产生新椭圆曲线方程,这样既可为用户提供丰富的选择性也可以为服务器节约更广阔的存储空间,同时确保网络信息的保密性、完整性和可用性。
本文通过分析椭圆曲线密码体制,建立了网络身份认证系统模型,该模型采用软硬件协同的方式,基于混合加密体制,使用速度快而安全性高的ECC算法进行加解密、签名与验证签名,对网络的信息建立起良好的保护的屏障,能够很好地抵抗重放攻击、猜测攻击、网络窃听攻击,整个网络身份认证方案简单有效。
参考文献
圆锥曲线密码体制 篇3
关键词：无线传感器网络,圆锥曲线密码,密钥管理,证书服务
0引言
无线传感 器网络 (Wireless Sensor Networks ,WSNs) 是由多种 学科高度 交叉的热 点研究领 域 ,被广泛应 用在军事 监察 、医疗护理 、交通监管 和环境监 测等各类 领域[1]。 然而 , 无线传感 器网络也 面临着诸 如窃听 、 注入 、 陷阱 、 欺骗 、重放 、拒绝服务 和HELLO扩散攻击 等多种安 全风险 ,因此如何 解决安全 问题成为 无线传感 器网络研 究的热点和难 点问题[2]。 由于无线传感器网络 的节点在能量 、 计算能力 、 存储能力 和通信带 宽等方面 有限制 , 传统的密 钥管理方 案无法直 接应用在 无线传感 器网络中 ,使得无线 传感器网 络的密钥 管理面临 着诸多困 难和挑战 。 适用于无 线传感器 网络的一 种比较简 单的密钥 管理方案 是在所有 节点中都 预先存储 一个对称 密钥进行 通信 ,但是如果 其中某一 个节点被 攻击成功 ,则全网络 就不再安 全 ,而且对称 密钥管理 方案限制 了新节点 的加入和 密钥更新 等动态性 操作 ,因此对称 密钥管理 方案不能 满足无线 传感器网 络的动态 性和安全 性需求 。 而非对称 密钥管理 方案既可 以保证网 络的安全 性需求也 可以很好 地满足动 态性需求 , 然而需要 更多的能 量和资源 开销[3]。 但随着大 规模集成 技术的飞 速发展 , 传感器节 点在能量 、 计算能力 、 存储能力 和通信带 宽等方面 都有很大 提高 , 可以通过 有效的控 制把非对 称密码体 制中的部 分方法应 用于无线 传感器网 络中来实 现安全密 钥管理 。
圆锥曲线 密码是一 种比椭圆 曲线密码 更加高效 的非对称 密码体制 ,具有密钥 短 、参数选择 灵活 、实现速度 快和安全 性高等优 点 ,通过将其 应用在无 线传感器 网络的密 钥管理方 案中 ,给出一种 基于圆锥 曲线密码 的无线传 感器网络 密钥管理 方案 (Key Management scheme based on Conic Curve cryptography for wireless sensor network , KMCC ) 。 所给方案 可以有效 实现通信 密钥分配 以及动态 添加新节 点 、密钥更新 和回收 ,并且在密 钥存储空 间 、可扩展性 和抗网络 攻击等方 面都要比 基于椭圆 曲线密码 的无线传 感器网络 密钥管理 方案等经 典的密钥 管理方案 具有更好 的性能 ,因此所给 方案可以 较好地适 用于无线 传感器网 络中 。
1KMCC方案设计
1.1网路模型
假设部署 的无线传 感器网络 中有且仅 有一个基 站 , 且该基站 不会失效 或者被攻 击 。 网络中每 个节点都 能够感知 其邻近的 节点 ,同时假设 在网络初 始化阶段 不存在外 部入侵的 问题 ,即所有节 点都具有 一定抵御 外部攻击 的能力 , 且为每个 节点赋予 唯一的身 份标识ID以抵御Sybil攻击和Newcomer攻击 。 其中 , 基站作为 证书管理 机构 , 用来为每 个节点分 配证书 , 证书内容 应包含与 节点私钥 匹配的公 钥 、节点身份 标识以及 时间戳 。 证书形式 为CAi= ESKCA( PKi, IDi, T ) , i表示某个 节点 , Ci表示节点i的证书 ,SKCA表示基站 的私钥 ,PKi表示节点i的公钥 , IDi表示节点i身份标识 号 ,T表示证书 的有效期 , 且节点i自身私钥 为SKi, 同时被注 入基站的 公钥PKCA。
1.2网络初始化
部署无线 传感器网 络之前 , 需要对整 个网络中 的基站和 所有节点 进行初始 化设置 。 首先需要 构造安全 圆锥曲线C , 然后分别 在其上选 取阶为k的基点P, 并定义圆 锥曲线C上的点加 运算和标 量乘法运 算[4]。 节点i的配置参 数则为 (k ,C/Fq, E , F , G , H ) , k表示有限 域Fq上的素数 ,C表示有限 域Fq上的圆锥 曲线 ,E表示有限 域Fq上的加法 群 ,F表示圆锥 曲线上的Frobenius映射 ,G表示加法 群E上随机选 取的生成 元 ,H表示单向 散列函数 ,且有SKi= KMH ( IDi) , KM表示系统 的主密钥 。
1.3通信密钥建立
部署无线 传感器网 络完成后 , 需要在基 站和节点 间建立通 信密钥 ,具体执行 过程如下 所示 :
( 1 ) 首先 , 每个节点 都通过广 播 “ Hello ” 消息来发 现邻居节 点 , 邻居节点 在收到 “Hello” 消息后回 复确认消 息 ;
(2) 当一对节点i和节点j互相确认 为邻居节 点之后 , 节点i通过利用 公钥证书CAi将自己的 公钥PKi发送给邻 居节点j ,节点i发送给节 点j的消息为 (CAi, t ) = 骔ESKCA( PKi, IDi, T ) , t 」 , 节点j发送给节 点i的消息为 ( CAj, t ) = 骔ESKCA( PKj, IDj, T ) , t 」 , 发送的消 息都包括 时间戳t , 主要作用是为 了保证节点j收到证书的有效性,避免节点i重发已过期证书或防止恶意节点冒充节点i重发过期证书;
( 3 ) 节点i和节点j只有利用 预注入基 站公钥PKCA才能对证 书解密 , 以验证证 书是由基 站发放的 , 并获得邻 近节点的 身份标识 和公钥 。 节点j利用基站 公钥PKCA来验证节点i发送的消 息DPKCA( CAi, t ) = DPKCA骔ESKCA( PKi, IDi, T ) , t 」 = ( PKi, IDi, T , t ) , 节点j获得节点i的身份标 识IDi和公钥PKi; 同样 , 节点i也需要利 用利用基 站公钥PKCA对节点j发送的消息进行验证DPKCA(CAj,t) =DPKCA骔ESKCA(PKj, IDj, T ) , t 」 = ( PKj, IDj, T , t ) , 获得节点i获得节点j的身份标 识IDj和公钥PKj;
( 4 ) 邻居节点i和节点j互相获得 对方的公 钥后 , 利用初始 化预先加 载的私钥SKi= KMH ( IDi) 和SKj= KMH ( IDj) 建立对密 钥Ki , j。 节点i生成对密 钥Ki , j= F ( SKi, H ( IDj) ) , 节点j生成对密 钥Kj , i= F ( SKj, H ( IDi) ) , 由映射F性质可知Ki , j= Kj , i, 则建立起 邻居节点i和j之间对密 钥 。
1.4节点的加入和删除
新节点加 入网络时 , 需要首先 对其配置 身份标识 , 产生新节 点的证书 和私钥 ,再与邻近 节点建立 通信对密 钥 ,具体执行 过程如下 :
( 1 ) 新节点t请求加入 网络时 , 基站首先 为该节点 分配一个 身份标识 号IDt, 用以生成 证书CAt= ESKCA( PKt, IDt, T ) 以及私钥SKt= KMH ( IDt) , 并同时为 该节点预 先注入基 站公钥PKCA;
( 2 ) 新节点t部署后 , 向周围节 点广播 “ Hello ” 消息寻找 邻居节点 , 邻居节点 回复确认 消息后 , 然后新节 点t与邻居节 点之间建 立对立对 密钥Ki , t。
由于整个 网络中每 对邻居节 点的密钥 与其他节 点之间的 对密钥是 相互独立 的 , 所以删除 被捕获或 失效的节 点不会给 其他节点 造成危害 , 节点删除 的执行过 程如下 :
( 1 ) 当一个节 点s能量耗尽 或被捕获 后 , 在网络中 广播该失 效或被捕 获节点s的身份标 识IDs及该节点 已退出的 消息 ,从而其证 书CAs失效 ;
( 2 ) 其余节点 收到节点s的身份标 识IDs退出的消 息后 ,若再有节 点s发送到消 息则直接 丢弃 。
1.5密钥的更新和回收
网络中邻 居节点利 用公私密 钥对更新 对密钥 , 假定是由节点i发起密钥更新请求,具体执行过程如下所示:
( 1 ) 节点i采用节点j的公钥PKj来加密节 点i的身份标 识IDi和一个一 次性随机 数R1, 然后发送 给节点j , 即节点i发送消息EPKj( IDi, R1) 到节点j , 其中R1唯一地标 识节点i更新 ;
( 2 ) 节点j采用节点i的公钥PKi来加密节 点i的一次性 随机数R1和节点j新产生的 一次性随 机数R2, 然后发送 给节点i, 即节点j发送消息EPKi( R1, R2) 到节点i , 其中R2唯一地标 识节点j更新回复 ;
( 3 ) 节点i收到消息EPKi( R1, R2) 进行解密 后 , 得到随机 数R1, 所以节点i确认回复 消息是节 点j发送的后 采用节点j的公钥PKj来加密随 机数R2, 并发送给 节点j , 即节点i发送消息EPKj( R2) 到节点j ;
(4) 节点j收到消息EPKj(R2) 进行解密 得到随机 数R2, 所以节点j可以确认 此次消息 是节点i发送的 ;
( 5 ) 节点i选择通信 会话密钥KD, 并采用自 己的私钥SKi和节点j的公钥PKj加密会话 密钥KD达到密钥 更新报文 消息M,即有M=EPKj( ESKi(KD)) , 然后发送 给基点j 。
( 6 ) 节点j收到密钥 更新报文 消息M = EPKj( ESKi(KD)) , 然后采用 自己的私 钥SKj和节点i的公钥PKi来解密会 话密钥KD, 即有DSKj( DPKi(KD)) , 从而邻居 节点间建 立新的会话密 钥 。
在无线传 感器网络 中 ,如果有节 点发现某 个节点不 合法时 , 需要向基 站对该节 点投不信 任票 , 当基站收 到对这个 节点的不 信任投票 超过一定 的阈值 ,则基站就 会通过广 播节点私 钥的方式 对该节点 的密钥进 行回收 ,具体执行 过程如下 :
(1) 当基站收到对节点e的不信任投票超过阈值d时 , 则向网络 广播发送 密钥回收 消息(SKe, PKe) ;
( 2 ) 网络中节 点在收到 回收消息 ( SKe, PKe) 后 , 查找自己 是否与不 信任节点e是邻居节 点 ,如果不是 邻居节点 则直接丢 弃该消息 ,如果是邻 近节点则 今后不再 接收节点e的消息 , 等到证书 过期后 , 则邻居节 点之间的 对密钥自 动撤销 。
2实验仿真与性能分析
实验仿真 工具采用 伯克利大 学研制的MICA2mote, 使用的是8位ATmega128L处理器 ,4 KB的SRAM以及128 KB的ROM , MAC层协议采 用802 . 11标准协议 , 路由协议 采用DSR协议 , 传感器节 点数目为500, 有且仅有1个基站 。 主要从安 全性 、存储开销 、能耗和可 扩展性四 个方面分 别与E&G方案 、IBC方案和基 于ECC方案三种 经典密钥 管理方案 进行分析 比较 , 以验证所 给KMCC方案的优 越性 。
2.1安全性分析
KMCC方案的安 全是建立 在圆锥曲 线上离散 对数问题 难解性的 基础之上 的 。 在网络通 信密钥建 立过程中 , 攻击者无 法获得圆 锥曲线密 码标量乘 算法的初 始密钥k , 而如果通 过截获网 络通信密 钥协商消 息来推导 出初始密 钥是困难 的 。 当有新节 点加入网 络时 ,由于该节 点没有初 始密钥 ,其现在的 密钥分配 的密钥无 法解密之 前的报文 消息 , 因而能够 保证网络 的后向安 全性 ; 假如攻击 者捕获了 网络中的 一个节点 ,由于邻居 节点之间 的对密钥 只涉及邻 居节点本 身 , 与其余节 点无关 , 为避免攻 击者通过 恢复被捕 获节点初 始密钥获 取通信报 文消息 , 可以通过 密钥更新 方法来更 新密钥 ,从而使得 老的对密 钥不能解 密以后的 报文或生 成冒充的 加密报文 ,从而有效 防止外部 恶意节点 或被捕获 节点的攻 击 ,保证网络 的前向安 全性 。 攻击者即 使捕获控 制了网络 一个节点 ,也不可能 获取其余 节点的密 钥信息和 其他相关 信息 ,并且可以 通过其余 节点的不 信任投票 来删除该 节点 ,所以可以 减少安全 威胁影响 整个网络 ,所以KMCC方案具有 较高的抗 毁性 。
由于攻击 者总是试 图在无线 传感器网 络中通过 捕获控制 传感器节 点来获得 其余节点 密钥信息 ,所以节点 捕获对于 无线传感 器网络是 一种需要 非常重视 的安全威 胁 。 E&G方案由于 节点需要 存储密钥 个数较多 ,如果其中 一个节点 被捕获 ,则极有可 能造成多 个节点的 密钥信息 泄露 , 网络的抗 毁性较差 , 其节点的 密钥被捕 获概率为1-(1-a/P)n [5]。 IBC方案 、 基于ECC方案以及 所给KMCC方案由于 只存储邻 近节点密 钥信息 , 所以单个 节点被捕 获不会扩 散整个网 络 ,IBC方案的节 点密钥被 捕获的概率 为中 ,a表示密钥 环大小 ,P表示密钥 池大小 ,n表示被捕 获的节点 个数 ,m表示网络 节点数目 ,e1表示基于ECC方案的密 钥回收成 功概率 ,e2表示KMCC方案的密 钥回收成 功概率 。 其中 , 节点数m=500 。 假定令a=300 ,P= 1 000 , n = 200 , e1= 0 . 27 , e2= 0 . 35 , 则KMCC方案与E&G方案 、IBC方案和基 于ECC方案的密 钥抵抗被 捕获能力 的比较分 析如图1所示 。
2.2能耗分析
由于无线 传感器网 络节点的 能量有限 , 所以密钥 管理方案 应尽可能 节约能量 消耗 ,密钥管理 方案的能 耗主要包 括运算能 耗和通信 能耗 。 在无线传 感器网络 中 ,节点传输 信息所需 的通信能 耗比执行 计算时的 运算能耗 大得多 ,一般认为 传输1 bit信息100 m所需能量 大约可以 执行3 000条指令 。 对于E&G方案 ,密钥分配 建立阶段 需需执行 单向散列 函数运算 和XOR运算 , 同时需要 进行节点 间的通信 , 当密钥环 超过阈值 时 , 通信能耗 将会大幅 增加 , 当有新节 点加入或 更新密钥 时 , 需要重新 执行密钥 分配过程 ,能耗几乎 相同 。 对于IBC方案 ,需要执行 单向散列 函数运算 、XOR运算和公 钥运算 , 当需要更 新密钥时 ,只需在邻 居节点之 间进行计 算能量和 通信能量 消耗 。 对于基于ECC方案 ,需要执行 单向散列 函数运算 、 椭圆曲线 密码标量 乘运算和 椭圆曲线 点加运算 , 对密钥只 存在于邻 居节点之 间 ,所以只需 考虑邻居 节点之间 的计算和 通信能量 消耗 。 对于KMCC方案 ,需要执行 单向散列 函数运算 、圆锥曲线 密码标量 乘运算和 圆锥曲线 点加运算 , 对密钥只 存在于邻 居节点之 间 , 所以只需 考虑邻居 节点之间 的计算和 通信能量 消耗 ,但是圆锥 曲线密码 标量乘运 算和圆锥 曲线点加 运算优于 椭圆曲线 密码标量 乘运算和 椭圆曲线 点加运算 ,所以KMCC方案比ECC方案所需 能耗更少 。 其中 ,假定网络 中每个节 点的初始 能量为0.5 J。 图2给出了随 网络规模 变化KMCC方案与经 典密钥管 理方案的 能耗分析 比较 。
2.3存储开销分析
假定节点 之间通信 密钥的长 度是相等 的 , 令存储参 数的开销 为Sc, 存储单个 密钥的开 销为Sk, h表示平均 邻居节点 的个数 ,有h= 姨m 。 对于E&G方案 ,只需要存 储节点的 通信密钥 ,所以其存 储开销只 与网络规 模的大小 有关 ,则其单个 节点的存 储开销为m(lnm+9.21)Sk/ h[8]。 对于IBC方案 , 需要存储 邻居节点 的通信密 钥 , 还需存储 系统参数 、系统公钥 、节点公私 钥对以及 身份标识 ,所以其存 储开销与 对网络规 模大小和 参数个数 有关 ,则其单个 节点的存 储开销为Sc+ ( h + 4 ) Sk[9]。 对于基于ECC方案 , 需要存储 邻居节点 之间的通 信密钥 , 还需要存 储公共参数、节点公私钥对以及 节点认证密钥,所以其存储开 销与对网 络规模大 小和参数 个数有关 ,则其单个 节点的存 储开销为Sc+ ( h + 3 ) Sk[10]。 对于所给KMCC方案 , 需要存储 邻居节点 之间的通 信密钥 ,还需要存 储节点公 私钥对和 节点认证 密钥 ,所以其存 储开销与 对网络规 模大小和 参数个数有关,则其单个节点的存储开销为Sc+ ( h + 2 ) Sk。 而且由于IBC方案和基 于ECC方案以及 所给KMCC方案都是 存储邻居 节点之间 的密钥信 息 , 所以网络 规模的增 加节点的存储开销变 化不大 。 则KMCC方案与E&G方案 、IBC方案和基 于ECC方案的存 储开销比 较如图3所示 。
3结束语
圆锥曲线密码体制 篇4
关键词：椭圆曲线密码体制,对称密码体制,非对称密码体制
密码学可以认为是数学的一个分支, 它是密码编码学和密码分析学的总称。通常主要用于保护通信双方实施安全的信息传递, 且不被非授权的第三方知道。密码学的发展经历了三个阶段:手工加密技术、经典加密技术、现代计算机加密技术[1]。当前的密码技术和理论都是基于以算法复杂性理论为特征的现代密码学。
Shannon在1949年发表的“The Communication Theory of Secrecy System”奠定了密码学的理论基础, 并使之成为一门独立的科学。1976年, Diffie&Hellman发表的“New Direction of The Cryptography”首次提出了公钥密码学的基本思想, 开创了公钥密码学的新纪元[2]。
当前通用的密码体制一般基于以下三类数学难题:
1) 基于大整数因子分解。1978年, 麻省理工学院Rivest、Shamir、Adlman三位学者首次发表的RSA公钥密码体制就是基于此的一种公钥密码体系, 简称RSA算法。
2) 基于有限域上离散对数。最著名的有El Gamal、DSA数字签名算法。
3) 基于椭圆曲线离散对数。基于椭圆曲线有限加法群上的椭圆曲线离散对数问题的求解困难性, 同其他公钥密码体制相比较, 在相同安全强度下, 椭圆曲线密码系统具有密钥短、占用空间和带宽小、处理速度快等优势。基于椭圆曲线建立的密码体制还有两大优点:一是可用于构造有限点群的椭圆曲线数量多;二是计算椭圆曲线有限点群的离散对数亚指数算法不存在, 解密算法难度很大, 安全性高。
1 公钥密码算法相关研究
由于对称密码算法在密钥管理、分发和数字签名方面的缺陷, 1976年W.Diffie和M.Hellman提出了一种巧妙的密钥交换协议, 称为Diffie-Hellman密钥交换协议/算法[8], 比如Alice和Bob希望通过公共通信网协商一个会话密钥, 只需要以下操作过程:
1) Alice随机选择一个a∈ (0, p-1) , Bob选择一个b∈ (0, p-1) ;
2) Alice计算gamod p, 发送给Bob;
3) Bob计算gbmod p, 发送给Alice;
4) 双方很容易计算出gabmod p, 即Alice计算 (gb) a, Bob计算 (ga) b
这种算法是安全的, 对于窃听者Charlie, 他只能得到gamod p或者gbmod p, 如果他想构造出gabmod p, 这便属于一个离散对数问题, 我们知道目前这还是一个数学难题。
在公钥密码系统中, 每位计算机网络的通信者都应该拥有两个密钥, 其中一个是对外保密的“私钥”, 另一个是对网络上所有人公开的“公钥”。私钥和公钥都可以对信息加密, 但私钥加密的信息须用对应的公钥解开, 公钥加密则须用对应的私钥解开。使用公钥密码系统, 网络上的双方无需事先传递密钥就能进行保密通信[11]。
首个公钥密码系统由形Rivest、Shamir和Adleman在1978年提出来, 简称为RSA公钥密码[9], RSA的安全性是基于大整数因子分解难题。目前, 国内外大多数使用公钥密码进行加密、解密和数字签名/验证的产品都是基于RSA密码体系。RSA密码体系的安全性完全依赖于大整数因子分解问题, 随着解决因子分解方法的进步及完善、计算机运算速度的不断提高和计算机网络的发展, RSA密码的安全性受到了前所未有的挑战, 人们必须选择更大的整数, 以增加破解的难度。目前, 安全的RSA密码需要的大整数都在1024位以上的二进制长度, 造成了RSA密码实现的代价变得越来越难以任受, 导致了RSA应用的效率越来越低, 成为RSA应用的主要瓶颈。
第二个著名的公钥密码是EGamal密码[10], 它的安全性依赖于离散对数问题。假设G为一个有限乘法循环群, g为G的生成元, x为任意的整数, 如果已知g及gx, 如何求解x的问题在数学上称为离散对数问题。在当前环境下, 当群G选择适当, 且整数x充分大时, 求解是非常困难的, 现己知最快的求解数域上离散对数的方法是亚指数级时间复杂度。
第三个著名的公钥密码是基于有限域上椭圆曲线加法群的离散对数问题, 它是华盛顿大学的Neal Koblitz[4]和在IBM工作的Victor Miller[5]各自独立地提出来的, 这使得研究了150多年的椭圆曲线在密码领域中得以发挥重要作用。椭圆曲线密码体制 (Elliptic Curves Cryptography, ECC) 的数学基础是椭圆曲线上的点构成的Abel加法群中离散对数的计算困难性。可以证明基于有限域上ECDLP的困难性要高于一般乘法群上的离散对数问题的困难性, 而且椭圆曲线域的运算位数远小于传统离散对数, 且很容易使用软件或硬件在计算机上进行实现。同时, 利用ECC实现速度非常快, 在同等安全强度下, ECC所需的计算量、存储量、带宽、开销都较小, 且加密和签名的速度高。因此, ECC特别适用于计算能力、带宽和集成空间受限的地方, 比如Smart卡。由于ECC具有其他公钥密码体制无法替代的优点, ECC从提出就得了到广泛关注, 而且被认为是下一代最通用的公钥密码系统。
2 椭圆曲线基本理论
2.1 椭圆曲线定义
椭圆曲线是一门古老且内容丰富的数学分支, 1985年, Victor Miller和Neal Koblitz各自独立地提出椭圆曲线公钥密码学, 它的基本思想仍然是基于有限域乘法群的公钥密码体制, 用有限域上椭圆曲线构成的群来类比有限域的乘法群, 从而获得类似的公钥密码体制。ECC的安全性是基于椭圆曲线离散对数问题的难解性, 经证明它目前还没有亚指数攻击方法, 所以, ECC具有一些其它公钥密码体制无法比拟的优点。
椭圆曲线并非我们通常意义上的椭圆, 这样命名的原因是因为对椭圆曲线的研究来源于椭圆周长计算问题, 以及所描述的椭圆积分等问题, 这里E (x) 是x的三次或四次多项式。
这里有E (x) =4x3+g2x-g3
所谓椭圆曲线就是在有限域Fp上的Weierstrass方程式, 即:
椭圆曲线的判别式为:Δ=-b22b8-8b43-27b62+9b2b4b6, 且Δ≠0
我们定义E的j-不变量如下:
对于椭圆曲线E, 可用以上方程外加一个特殊点O来表示, 这时方程称为椭圆曲线E的仿射方程。
E={ (x, y) |y+a1xy+a3y=x+a2x+a4x+a6}⋃{O}椭圆曲线E还有一种射影方程表示形式:
2.2 椭圆曲线上点的加法规则
给定一条Fq上的椭圆曲线E, 及其上的任意两点P和Q, 连接P和Q的直线与E交于第3个点-R, 由于-R和无穷远点O可决定一直线, 该直线与E交于一个点R定为P与Q的和, 记为P+Q。可以证明这样定义E上点的加法后, 就使E成为一个Abelian群。具体的运算法则如下:
1) 当P≠Q时, 直线交于椭圆曲线的另一点-R, 过-R做Y轴的平行线交于R。我们规定P+Q=R。如图1所示。
2) 当P=Q相等时, 即过P、Q的直线为过P点的切线。此时切线与曲线E有交点-R, P+Q=P+P=2P=R。如图2所示。
3) 如果直线与Y轴平行, 交椭圆曲线E三个点:两个有相同x坐标的点 (设为P, Q) 无穷远点O。因此, P+Q=O, 于是有-P=Q, 即作为群元素P的逆元Q, 所以有P+ (-P) =O, 在仿射坐标系中与群元素P的x坐标相同。这一关系如图3所示。
4) 逆元:设P= (x, y) ∈E, 根据Weierstrass方程式, 由根与系数的关系易知
5) 现设椭圆曲线上任意两个非零点P (x1, y1) , Q (x2, y2) , 且有P≠-Q, 则设R (x3, y3) 是P与Q的和, L是P, Q连线, 则-R在直线L上。设过P, Q直线L的方程为:y=λx+υ式中,
将以上式子代入一般形式的Weierstrass方程, 可得
特别地, 当P=Q时,
以上加法规则在复数、实数、有理数和有限域GF (p) 上均有效。值得指出的是, 对于有限域GF (p) 的情形, 上述加法规则得到的应是mod p的结果。对于有限域GF (2m) , 由于所用椭圆曲线形式发生变化, 因此上述加法规则应做相应修改, 这方面可参考相关资料。
2.3 椭圆曲线分类
根据域F的特征Char (F) 和j-不变量, 给出不同情况上的椭圆曲线形式:1) Char (F) ≠23
, 时,
2) Char (F) =2时,
E:y+a3y=x+a4x+a6, 若j=0
E:y2+xy=x3+a2x2+a6, 若j≠0
3) Char (F) =3时,
E:y2=x3+a4x+a6, 若j=0
E:y2=x3+a2x2+a6, 若j≠0
一般情况下, 我们总是选取有限域Fq为素域Fp, 或者Fq是F2m (m为某个素数) , 这样选取是从安全性方面进行考虑的。
3 椭圆曲线在密码学中的应用
3.1 椭圆曲线密码体制的建立[7]
首先选取一个基域Fq, 它可以是一个素域, 也可以是一个特征为2的域F2m (m为素数) 。其次在Fq上选取一条椭圆曲线E, 并使其群阶为一个大素数N, 或者是一个大素数与一个小整数的乘积。然后选取E上的一个阶为大素数的n的点P。有限域Fq、曲线E、点P和其阶N均为公开的信息。
3.2 椭圆曲线密钥对的生成
每一个参与者需要完成下述过程:
输入:椭圆曲线参数组pEPn
输出:公钥Q和私钥d。
1) 随机选取d∈R[1, n-1]
2) 计算Q=d P
3) 返回 (Q, d) , Q为公钥, d私钥
3.3 椭圆曲线加密方案
现在假设Alice要向Bob发送信息, 则Alice加密过程如下:
1) Alice找出Bob的公钥QB;
将明文映射到域Fq的点上, 即Fq;
3) Alice随机选出一个整数k∈[1, n-1];
4) 计算点C1= (x1, y1) =k P;
5) 计算点 (x2, y2) =k QB;若x2=0, 则返回第3步;
6) 计算点C2=M+k QB
7) 将已加密的数据 (C1, C2) 发给Bob。
Bob收到密文后, 解密过程如下:
计算M=C2-d C1, 并从点M取出明文。
3.4 椭圆曲线签名方案 (ECDSA)
我们给出基于椭圆曲线的数字签名方案, 称为ECDSA。
ECDSA签名生成:设Alice要对信息M签名后, 传送给Bob, 则Alice要完成以下步骤:
1) 将信息M映射为比特串;
2) 计算Hash值e=H (M)
3) Alice随机选取整数κ∈[1, n-1];
4) 计算点 (x1, y1) =κP;
5) 计算r=x1+e
SB=kB+x1dBxB (modn) (6) Alice应用自己的私钥dA, 计算s=k-dAr (modn)
7) Alice将信息M和签名 (r, s) 发送给Bob
签名验证:Bob收到Alice发过来的信息后, 需要验证是否为Alice所签, 则Bob需要完成以下过程:
1) 找出Alice的公钥QA
2) 计算点 (x1, y1) =sP+rQ
3) 计算Hash值e=H (M)
4) 计算r'=x1+e
5) 当且仅当r=r'时, Alice对信息的签名被Bob认可。
3.5 椭圆曲线密钥生成协议 (ECKEP)
这里给出一个基于椭圆曲线的密钥协议:
设有椭圆曲线参数Fq, E, P和n, Alice的私钥为dA, Bob的私钥为dB而Alice和Bob的公钥分别为QA=dAP= (xA, yA) 和QB=dBP= (xB, yB) 。
1) Alice完成下述步骤
(1) 随机选取整数kA∈[1, n-1];
(2) 计算点 (x1, y1) =RA=kAP
(3) Alice将RA发给Bob
2) Bob完成下述步骤
(1) 随机选取整数kB∈[1, n-1];
(2) 计算点 (x2, y2) =RB=kBP
Bob将RB发给Alice
3) Alice完成下述步骤
(1) 计算整数SA=kA+x1dAxA (modn)
(2) 计算会话密钥K=SA (RB+x2xBQB)
4) Bob完成下述步骤
(1) 计算整数
(2) 计算会话密钥
由于ECC的安全性和优势非常明显, 再加上许多标著名组织在椭圆曲线密码算法标准化方面做了大量工作, 在1998年ECC被确定为ISO/IEC数字签名标准, 1999年椭圆曲线数字签名算法被ANSI确定为数字签名标准。
3.6 椭圆曲线密码体制分析
同以往的公钥密码体制相比较, 椭圆曲线密码体制有以下三个方面的优点[2]。
1) 安全性高
目前, 针对有限域上的离散对数问题攻击的最快算法是指数积分法, 其运算复杂度为:
而攻击椭圆曲线上的离散对数问题的常用算法为大步小步算法, 它的复杂度为:
式中, pmax是椭圆曲线所形成的Abel群的阶的最大因子, 可见椭圆曲线公钥密码体制更安全。
2) 密码长度更小
对以上两种攻击密码算法的复杂度进行比较, 可知在同等安全性能下, 椭圆曲线密码体制算法需要的密钥长度远小于有限域上离散对数问题的公钥密码长度, 因此, 椭圆曲线密码体制更适合于存储空间有限、带宽小、运算速度高的环境中。
3) 算法灵活性更好
通常情况下, 如果有限域GF (p) 确定, 那么其上的循环群也就确定了, 但有限域上的椭圆曲线却可以通过改变曲线参数而进行随机变化, 相应地生成不同的循环群, 从而导致椭圆曲线有着丰富的结构和多种选择, 与RSA/DSA相比较, 在安全性同等的条件下, 椭圆曲线密钥长度更小, 灵活性也高。
4 结论
自公钥密码体系被提出来, 都是以某一含有“陷门”的数学难题作为其安全性基础的, 各种椭圆曲线公钥密码体系的安全性都与相应的椭圆曲线离散对数问题的求解困难性等价。如果离散对数可以计算, 那么从一个用户的公钥就可以推导出相应的私钥, 这样系统就不安全了。目前, 有许多针对椭圆曲线离散对数的攻击算法, 主要有以下几类:针对一般离散对数问题的攻击算法, 比如大步小步算法和Pollard-p算法;针对特殊椭圆曲线的攻击算法, 如针对超奇异型椭圆曲线的MOV类演化算法, 还有针对畸异型椭圆曲线的SSAS多项式时间算法等。
从以上分析可知, 只要选取的椭圆曲线能抵抗上述几种常见的攻击算法, 即选取一条安全的椭圆曲线, 那么椭圆曲线密码的安全性是可以保证的, 但如何才能选取一条安全的椭圆曲线, 这是一个深刻的数学难题, 有待于相关领域的深入研究。总之, 我们在给椭圆曲线选择参数时应该谨慎, 为避免安全隐患, 所选择的椭圆曲线上的离散对数问题必须能够抵抗上述的所有攻击。
参考文献
[1]郭海民, 白永祥.数论在密码学中的应用[J].电脑知识与技术, 2010 (6) .
[2]William Stallings.Cryptography and Network Security–Principles and Practice, Fifth Edition[M].Publish House of Electronics Industry, 2011.
[3]胡向东, 魏琴芳, 等.应用密码学[M].2版.北京:电子工业出版社, 2011.
[4]Victor S.Miller.Elliptic curves and their use in cryptography[J].Mathematics of Computation, 1997 (61) :1-15.
[5]Neal Koblitz.Elliptic curves cryptosystems.Mathematics of Computation, 1987 (177) :203-209.
[6]Miller.Use of elliptic curve in cryptography.In advances in cryptology-CRYPTO’85 (Santa Barbara Calif.) , Spring-Verlag, 1985:417-412.
[7]张方国.超椭圆曲线密码体制的研究[D].西安:电子科技大学, 2001.
[8]吴世忠, 祝世雄.应用密码学[M].北京:机械工业出版社, 2000.
[9]W.Diffie and M.Hellman.New directions in cryptography[J].IEEE Trans.Inf.Thy.1976, 22:644-654.
[10]Rivest, Shamir, Adleman.A method for obtaining digital signatures and public-key cryptosystems[J].Comm Assoc.Computer Math, 1978 (21) :120-126.
[11]EIGamal T.A public key cryptosystem and signature scheme based on discrete logarithms[J].IEEE Trans.Inf.Thy., 1985 (31) :469-472.
圆锥曲线密码体制 篇5
密码芯片由于资源受限,使得其在实施抗功耗攻击过程中存在效率和安全的矛盾,尤其是功耗攻击技术的出现对密码芯片的安全造成了严重威胁。功耗攻击技术是1998 年由Paul Kocher率先提出的一种利用芯片工作时泄露的功耗信息来获取密钥信息的密码分析方法,这种攻击方法实现简单,攻击成功率高,比传统的数学攻击方法具有更大的威胁[1,2,3,4]。根据攻击手段不同,可分为简单功耗分析SPA( Simple Power Attack) 和差分功耗分析DPA( Differential Power Attack) 。由于椭圆曲线密码算法ECC( Elliptic Curve Cryptogram) 与其他的传统公钥密码算法相比,在相同安全性条件下具有所需要的密钥更短,存储空间更小的优点,更适合于密码芯片等资源受限的设备,所以目前出现了大量针对椭圆曲线密码的功耗攻击,主要有零值寄存器功耗分析ZPA( Zero-value Power Analysis) 和零值点功耗分析RPA( Refined Power Analysis)[5,6,7]。
同时,国内外文献也出现了针对椭圆曲线密码的抗功耗攻击分析研究。文献[8]提出了一种基于窗口随机化初始点WBRIP( Window-Based Random Initial Point) 的椭圆曲线密码抗功耗攻击算法,其主要思想是通过将椭圆曲线密码标量的二进制编码进行窗口化,从而掩盖在一个窗口内执行点加操作和倍点操作运算的次数,使得攻击者无法根据中间结果猜测运算过程中执行的具体操作,该算法虽然能够抵抗多种功耗攻击,但在运算效率方面需要进一步改进。文献[9]对上述算法进行改进,给出了一种固定窗口宽度为w的非邻接形式表示算法FWNAF( Fractional Width-w Non Adjacent From) 的椭圆曲线密码抗功耗攻击方案,通过优化编码减少添加伪操作次数,以提高改进方案的运算效率。文献[10]提出了一种高效的窗口随机化初始点EBRIP( Efficient-Based Random Initial Point) 椭圆曲线密码抗功耗攻击算法,通过将窗口宽度为w的非邻接表示形式分成整数部分和分数部分实现抗SPA攻击,然后将基点分成固定部分和可变部分实现DPA、ZPA和RPA攻击,并且可以有效提高运算效率。奇系数梳状算法是椭圆曲线标量乘法运算的一种快速计算方法,通过将添加伪操作和基点掩码技术应用在奇系数梳状算法中,给出一种基于奇系数Comb算法OCM( Odd-only Comb Method) 的椭圆曲线密码抗功耗攻击方案,与WBRIP和EBRIP算法比较,给出的抗功耗攻击算法具有相同的抗功耗安全性,且有更高的运算效率。
1 椭圆曲线标量乘快速算法
椭圆曲线密码的标量乘快速算法主要有双基数系统编码算法[11]、阶乘展开式编码算法[12]和整数拆分表示形式编码算法[13]等。奇系数梳状算法是常用的椭圆曲线标量乘快速算法,与其他快速算法相比具有存储空间小和运算效率高的优点。下面给出椭圆曲线标量乘奇系数梳状快速算法的具体描述。
首先,给出椭圆曲线密码的标量乘法运算如式( 1) 所示:
其中,标量k采用二进制编码,n为编码长度,ki为编码系数。
通过对椭圆曲线密码的正奇数标量采用奇系数梳状算法进行重新编码,则有椭圆曲线密码标量的奇系数梳状形式编码如式( 2) 所示:
其中,标量的奇系数梳状算法编码长度,奇系数编码系数li≠0,s为奇系数梳状算法编码系数的二进制编码长度,n为标量的二进制编码长度。奇系数梳状算法编码系数的二进制编码系数为lij,且若当j = 0 时,有li0∈ { - 1,1} ; 若当j > 0 时,有lij∈ { - 1,0,1} 。令l为奇系数梳状编码后的标量,则椭圆曲线密码标量乘法运算形式变化成如式( 3) 所示:
其中,Pi为预计算点,通过预计算可以构造出预计算表,且有Pi= ( u( s - 1)2( s - 1) t+ … + ui2it+ … + u12t+ 1) ·P,且ui∈{ 0,1} 。
将所给已知标量进行奇数化,即如果标量k是正奇数,则有l = k + 1; 然而如果标量k是正偶数,则有l = k + 2。因为对原标量k进行了奇数化,所以在返回结果Q时需要增加一次后处理:如果标量k是奇数,则需增加操作Q = Q - 2P; 如果标量k是偶数,则需增加操作Q = Q - P 。则如果椭圆曲线密码标量经过重新编码后,奇系数梳状标量乘法运算如算法1 所示[14]:
算法1奇系数梳状椭圆曲线密码标量乘快速算法
2 基于OCM的抗功耗攻击方案
算法1 中,由于奇系数编码系数li均不为0,所以在执行步骤6 的过程中,总是执行相同的操作顺序,即每执行一次倍点操作就需要执行一次点加操作,具有相同的能量图谱,没有明显的功耗差异,使得攻击者无法利用功耗差异信息猜测密钥信息,并且在步骤7 中都执行了一次点加操作运算,所以也不会泄露所给已知标量的奇偶性,因此算法1 可以有效抵抗SPA攻击。然而,由于基点P是已知的,使得中间结果与输入之间存在相关性,攻击者可以利用中间结果信息猜测密钥信息,而且所给已知的基点中同时也存在有特殊点被攻击者利用实施ZPA和RPA攻击,所以算法1 无法抵抗DPA、ZPA和RPA攻击。
通过结合掩码技术[15],引入一个随机点,将每一个小标量乘法运算的基点进行随机化,以掩盖小标量和功耗之间的相关性,从而使得攻击者无法通过多次猜测获取密钥信息。则有引入随机点R后,基于奇系数Comb编码标量乘法运算Q = l P变换为如式( 4) 所示:
由于引入了一个随机点,所以在返回结果Q时,需要再增加一次后处理进行恢复: 如果标量k是奇数,则需增加操作Q =Q - 2P - R; 如果标量k是偶数,则需增加操作Q = Q - P - R 。下面给出基于奇系数梳状算法的椭圆曲线密码抗功耗攻击方案,如算法2 所示:
算法2奇系数梳状椭圆曲线密码抗功耗攻击算法
3 算法性能分析
算法2 中,通过引入随机点R,将预计算表中的Pi进行随机化,从而可以消除中间结果与功耗之间的相关性信息,并且不会存在可以被攻击者利用的特殊点,所以给出的算法2 可以抵抗DPA、ZPA和RPA攻击。同时,由于算法2 没有系数为0 的系数,因而不存在功耗差异操作,从而具有相同的能量消耗图谱,本身具有抵抗SPA攻击的能力。另外,算法2 通过执行两次后处理操作: 一方面可以掩盖原标量的奇偶性,进一步增强算法的安全性; 另一方面通过减去引入的随机点,可以恢复出真实的返回值。
算法2 的步骤3 中,计算2( s-1) tP,…,2tP需要的运算量为( s - 1) t D,计算( u( s-1)2( s-1) t+ … + ui2it+ … + u12t+ 1) ·P -R需要的运算量为( 2s- 1) A,则构造预计算表所需总的运算量为( 2s- 1) A + ( s - 1) t D。步骤7 中,主循环运算所需总的运算量为t A + t D。步骤8 中,后处理运算所需总的运算量为2A或者2A+ D。因此,算法2 所需的总运算量为( 2s+ t + 1) A + ( st + 1) D。其中,D表示倍点运算,A表示点加运算,t表示奇系数编码长度,s表示奇系数算法编码系数的二进制编码长度,且有,n表示奇数化后的标量的二进制编码长度。表1 给出了算法2 与二进制( BR) 抗功耗攻击算法和WBRIP抗功耗攻击算法的性能比较。
从表1 可以看出,所给算法2 比WBRIP抗功耗攻击算法所需的存储空间小。然而,WBRIP抗功耗攻击算法比所给的算法2 多执行了( 2s -1- 2) 次点加操作运算和( 2s -1+ s - 2) 次倍点操作。所以算法2 在存储空间减少的情况下,具有相同的抗功耗攻击能力,且有更高效的运算效率。目前,一般认为椭圆曲线密码512 比特的密钥是安全的,即t = 512。令s = 4,有t = 128。另外,文献[16]给出在仿射坐标系下,倍点运算D = 24M,点加运算A = 23M,M表示模乘运算。表2 给出了算法2 与BR抗功耗攻击算法和WBRIP抗功耗攻击算法的运算效率比较。
从表2 可以看出,所给算法2 的总运算效率比BR抗功耗攻击算法提高34. 98% ,比WBRIP抗功耗攻击算法提高2. 36% 。其中,算法2 比WBRIP抗功耗攻击算法所需预计算大的多,然而由于预计算表可以预先存储到密码芯片中,因而需要考虑主要是主循环运算,算法2 的主循环运算效率比WBRIP抗功耗攻击算法的主循环运算效率提高了60. 04% ,比BR抗功耗攻击算法的主循环运算效率提高了74. 71% ,而WBRIP抗功耗攻击算法的主循环运算效率比BR抗功耗攻击算法只提高了36. 70% 。由此可知,所给算法2 可以同时兼顾安全和效率两个方面,进一步提高密码芯片的运算效率,能够很好地满足资源受限的各类应用环境中。
4 结语
椭圆曲线密码算法是密码安全芯片中的主流加密算法,而奇系数梳状算法是椭圆曲线密码中的一种快速标量乘算法。由于功耗攻击的出现,使得密码安全芯片的安全性受到比较大的威胁,因而通过结合奇系数梳状快速标量乘算法和基点掩码技术给出的抗功耗攻击算法,可以有效抵抗多种功耗攻击,并且同其他传统抗功耗攻击算法相比,所给算法可以进一步有效提高运算效率,很好地解决了资源受限的密码芯片效率和安全的矛盾问题。因而所给算法可以很好地应用各种资源受限的应用系统中,具有很好的理论研究意义和实际推广应用价值。
摘要：针对资源受限的密码芯片在抵抗功耗攻击中存在效率和安全两个方面的矛盾。通过将标量采用奇系数梳状算法进行编码,然后结合预计算表将椭圆曲线标量乘法运算转化为一组小标量乘法运算,并利用基点掩码技术实施抗功耗攻击,提出一种基于奇系数Comb的椭圆曲线密码抗功耗攻击方案。算法性能分析结果表明:与传统的抗功耗攻击方案相比,给出的抗功耗攻击方案不仅可以抵抗简单功耗攻击、差分功耗攻击、零值寄存器功耗攻击和零值点功耗攻击,并且能够在存储空间和主循环运算量基本保持不变的情况下具有更高效的运算效率,在各种资源受限的应用系统中具有较好的实际应用价值。
圆锥曲线密码体制 篇6
当前最著名、应用最广泛的公钥系统RSA是在1978年在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制,是一种分组密码体制。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性[2]。RSA系统是公钥系统的最具有典型意义的方法,大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。
2 RSA公钥密码体制简介
2.1 密码体制概述与RSA算法
2.1.1 对称密码体制
对称密码体制是一种传统密码体制,也称为私钥密码体制。在对称加密系统中,加密和解密采用相同的密钥。因为加解密密钥相同,需要通信的双方必须选择和保存他们共同的密钥,各方必须信任对方不会将密钥泄密出去,这样就可以实现数据的机密性和完整性。比较典型的算法有DES(Data Encryption Standard数据加密标准)算法及其变形Triple DES(三重DES),GDES(广义DES);欧洲的IDEA;日本的FEAL N、RC5等。对称密码算法的优点是计算开销小,加密速度快,是目前用于信息加密的主要算法。它的局限性在于它存在着通信的双方之间确保密钥安全交换的问题。另外,由于对称加密系统仅能用于对数据进行加解密处理,提供数据的机密性,不能用于数字签名。因而人们迫切需要寻找新的密码体制。
2.1.2 非对称密码体制
非对称密码体制也叫公钥加密技术,该技术就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中,加密和解密是相对独立的,加密和解密会使用两把不同的密钥,加密密钥(公开密钥)向公众公开,谁都可以使用,解密密钥(秘密密钥)只有解密人自己知道,非法使用者根据公开的加密密钥无法推算出解密密钥,顾其可称为公钥密码体制。最有影响的公钥密码算法是RSA,它能抵抗到目前为止已知的所有密码攻击。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法,算法的名字以发明者的名字命名。RSA算法的安全性依赖于大数分解问题的难解性。算法中使用的公钥和私钥都是两个大素数(大于100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积[3]。
RSA算法在ISAKMP/Oakley框架中被用做一种可能的身份认证方式。Diffie-Hellman密钥交换算法是ISAKMPIOakley框架的一个关键组成部分。在一个密钥协商会话的开始阶段通信参与方通过使用Diffe-Hellman算法产生双方共享的密钥,这些密钥将被用于密钥协商协议的后续步骤。
在实际应用中,人们通常将对称密钥算法和公钥密码算法结合在一起使用,以实现最佳性能。即使用某个对称密钥密码体制来加密需传递的机要信息,而同时使用RSA等非对称密钥密码体制来传送DES的密钥。这样就可以综合发挥两种密码体制的优势,即DES高速简便性和RSA密钥管理的方便和安全性。
2.2 RSA体制的算法过程
RSA密码体制使用了模n的非负最小完全剩余系中的运算,这里n是两个不同的素数p和q的乘积[3]。RSA体制的算法过程如下:
首先产生密钥,过程如下:
1)随机产生两个长度为K/2位的素数P和Q。
2)计算公钥public Key=P*Q;(public Key是k位的长度)。
3)随机产生一个加密密钥key E,2<=key E<=Φ(n)-1,其中GCD(key E,Φ(n))=1。
注意这是保证解密密钥key E×key D mod(Φ)(n)=1有解的充要条件,Φ(n)称为n的欧拉函数,值为:Φ(n)=(P-1)*(Q-1)。
4)求解解密密钥key D=key E-1 mod(n),key E-1为解密密钥key D的逆元,此公式原方程为(key E×key D mod(n)=1)。
由此公钥,加密密钥和解密密钥全部产生。
其次,对明文加密或对密文进行解密,过程如下:
1)加密:C=Mkey E mod public Key;其中M表示明文,C表示密文。
2)解密:M=Ckey D mod public Key;其中M表示明文,C表示密文。
2.3 RSA体制的实现
RSA密码体制的实现是一个比较复杂的过程,它涉及到素数的产生、大整数模运算等数学运算。RSA体制中,p、q均为大的素数,如何有效地产生大素数将是实现RSA体制所需解决的第一个问题。
通常情况下,人们使用一种概率算法来产生大素数。这是因为p、q都是大素数,如果使用因子分解的办法来求素数p、q,这样的难度与对RSA进行攻击(既分解大合数)实际上是相同的,在计算机是可行的。
概率算法的工作过程一般并不着眼于产生素数,而是首先随机地产生一个大奇数,然后使用概率性算法判定该奇数是否为素数(这样的过程一般称为素性检测)。
2.4 RSA公钥密码体制的优势[4]
1)机密性(Confidentiality):保证非授权人员不能非法获取信息,通过数据加密来实现;
2)确认(Authentication):保证对方属于所声称的实体,通过数字签名来实现;
3)数据完整性(Data integrity):保证信息内容不被篡改,入侵者不可能用假消息代替合法消息,通过数字签名来实现;
4)不可抵赖性(Nonrepudiation):发送者不可能事后否认他发送过消息,消息的接受者可以向中立的第三方证实所指的发送者确实发出了消息,通过数字签名来实现。
可见公钥密码体制系统能够满足网络信息安全的所有主要目标。
3 在ASP.NET中实现RSA加密解密的主要方法[5]
在.Net Framework中提供常用的加密算法类中,支持RSA相关的类主要有两个:RSA类和RSACrypto Service Provider类。RSA类是“表示RSA算法的所有实现均从中继承的基类”,而RSACrypto Service Provider类是“使用加密服务提供程序(CSP)提供的RSA算法的实现执行不对称加密和解密”。另外,“表示RSA算法的标准参数”的RSAParameters结构也是很重要的,它保存了RSA算法的参数。
RSA参数的产生:RSA参数的类型就是上面提到的RSAParameters结构,其包含了D、DP、DQ、Exponent、Inverse Q、Modulus、P、Q八个字段。加密时仅需要Exponent和Modulus两个值,可看成公钥。解密时所有字段都需要,可看成私钥。下面这段程序显示了如何产生RSA两个参数:
RSACrypto Service Provider rsa=new RSACrypto Service Provider();
RSAParameters rsa Params Exclude Private=rsa.Export Parameters(false);
RSAParameters rsa Params Include Private=rsa.Export Parameters(true);
RSACrypto Service Provider类的Export Parameters(bool)方法用于导出RSA参数,true表示导出上述八个字段的“私钥”,false表示导出“公钥”。
使用RSA参数进行加密解密:这一步需要把上面两个参数导入到RSACrypto Service Provider类对象中,再用它对数据进行加密。如下面的代码所示,我们可以写一个函数来完成加密过程:
解密时只要把rsa.Import Parameters(rsa Params Exclude Private)换成rsa.Export Parameters(rsa Params Exclude Private),再把Encrypt换成Decrypt就行了。
保存和加载RSA参数:RSA参数可以保存为XML格式,下面代码说明了如何保存和加载(只列出了关键部分)
保存:
4 结论
RSA公开密钥加密算法发展至今,在电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法,在各领域的应用广泛。本文详细论述了RSA公钥体制的算法、安全性以及应用优势,以及利用当前常用的ASP.NET技术,简述设计实现对传输文件的RSA加密解密过程。
摘要：针对当前互联网常用密码安全技术——RSA公钥密码体制,该文简述了其算法原理、优势、安全性,并通过ASP.NET语言设计实现RSA加密解密。
关键词：互联网,RSA加密,解密,ASP.NET
参考文献
[1]杨义先,纽心忻,李名选.网络信息安全与保密[M].北京:北京邮电大学出版社,2001.
[2]辛运炜.密码学算法[M].北京:电子工业出版社,1998.
[3]Douglas R.Stinson.密码学原理与实践[M].北京:电子工业出版社,2003:131-132.
[4]安全技术——RSA公钥密码体制安全性分析.http://jxzhoumin.javaeye.com/blog/196011.
公钥密码RSA体制及安全性分析 篇7
公钥密码[1]是1976年提出的一类新的密码体制,公钥密码体制RSA[2]是1977年由美国麻省理工学院的Ron Rivest,Adi Shamir和Len Adleman在题为《获得数字签名和公开密钥密码系统的方法》的论文中提出的。RSA是一个基于数论的非对称密码体制,其名称来自于三位科学家的姓名首字母。RSA算法是和一个能同时用于数据加密和数字签名的算法,是公钥密码体制中最优秀、影响最大的加密算法。RSA的安全性是基于大整数素因子分解的困难性,在理论上一直未能得到证明。RSA经历了各种攻击,至今未能被完全攻破。
1 RSA 算法及分析
1.1 RSA算法描述
(1)找到2个大素数p,q。
(2)做乘法:n=pq;欧拉函数值φ(n)=(p-1)(q-1)。
(3)随机选取加密密钥e,满足gcd(e,(p-1)(q-1))=1。
(4)满足ed≡1mod(p-1)(q-1),则d=e-1mod((p-1)(q-1))。
(5)d和n互素。公钥是(n,e),私钥是(n,d)。
(6)两个素数p和q销毁(保密,不能泄露出去)。
1.2 RSA算法分析
加密消息m时,将m看成一个大整数,把其分成比n小的数据分组。按公式加密:
ci=m
解密消息时,取第一个加密后的分组ci并计算式(2):
mi=c
例如:设p=37,q=41(十进制),那么:n=pq=1517,随机选取e=17作为公钥。将n=1517和e=17公开,并对p和q保密。为了得到解密指数,需要找到e=17模(p-1)(q-1)的乘法逆元,于是可以通过使用欧几里得算法得到:
d=e-1mod1517=593
加密消息:m=1234567。
在此例中,按3位数字一分组就可以进行加密:
m1=123;
m2=456;m3=007(不足在左边填充0)。
加密:
12317mod1517=1107=C1;
45617mod1517=1292=C2;
00717mod1517=645=C3;
密文:C=11071292645
解密消息时需要密钥进行相同的指数运算。
如:1107593mod1517=123=m1
消息的其余可用同样的方法恢复出来。
2 几种针对RSA的攻击方法
2.1 RSA的公共模数攻击[3]
为了密钥管理的方便,对一个网络用户群的系统可以选取一个共同的RSA-n密码体制,而不同的人拥有不同的e和d。这样系统的安全性将受到威胁。一般的情况是同一信息用不同的公钥加密,这些公钥共模而且互素,那么该信息无需私钥就可以得到恢复。设m为信息明文,用两个互素的公钥e1,e2加密,公开模数为n,那么就有:
C1=me1modn
C2=me2modn
攻击者知道n,e1,e2,C1和C2,就能得到m。因为e1和e2互素,所以通过欧几里得算法可以知道存在r,s,使得re1+se2=1,且r,s中必有一个是负数,设r>0。再用欧几里得算法计算:
C
则(C
mre1+se2modn=
m
恢复出了明文。
对于RSA的公共模数攻击,解决的办法是不共享n。
2.2 低指数攻击[4]
2.2.1 小加密密钥e攻击
为了提高加密速度,尽量选取较小的加密密钥e。但是如果e选取过小,则系统是不安全的。
例如:对RSA-n,设明文为m,0≤m≺n。如果随机取e过小,则可能有:me≺n。那么C=(memodn)=me,这就是普通的指数,即
所以使用加密指数e=216+1=65537(费马素数!)可以避免一些对小加密密钥e的攻击。
2.2.2 小解密密钥d攻击
1990年Micgael Wiener证明了,若d的长度小于模n长度的
对于低指数攻击,对付的办法就是e和d都取较大的值。
2.3 选择密文攻击[5]
由于RSA密文是通过公开渠道传播的,攻击者可以获取密文。假设攻击者为A,密文收件人为T,A得到了发往T的一份密文c,他想不通过分解质因数的方法得到明文。换句话说,他需要m=cd。
为了恢复m,找一个随机数r,r<n,当然有T的公钥(e,n)。他计算:
x=re%n(用T的公匙加密r)
y=xc%n(将临时密文x与c相乘)
t=r-1%n
A知道RSA具有下面的一个特性:
如果x=re%n,那么r=xd%n
因此他想办法让T对y用T自己的私匙签名(实际上就是把y解密了),然后将结果u=yd%n寄回给A。A只要简单地计算:m=tu%n
上面结论的推导是:
tu%n=r-1yd%n=r-1xdcd%n=cd%n=m
对于选择密文攻击,可以采取的办法有两条:一是采用好的公钥协议,保证工作过程中实体不对其他实体任意产生的信息解密,不对自己一无所知的信息签名;二是决不对陌生人送来的随机文档签名。
3 RSA加密算法的安全性
RSA的安全性基础是数论和计算复杂性理论中的下述论断:求两个大素数的乘积是计算机上容易的,但要分解两个大素数的乘积求出他的素因子在计算上是困难的。在理论上,RSA的安全性取决于分解的困难性,但在数学上至今还未证明分解模就是攻击RSA的最佳方法,也未证明分解大整数就是NP问题,可能有尚未发现的多项式时间分解算法。
下文是几种因数分解的算法:
(1)试探除法,一种最老也是最笨的办法,穷举所有小于sqrt(n)的素数,耗时以指数率增长。
(2)二次筛法,对10110以内的数是最快的算法。
(3)MPQS,QS的改进版本,要快一些。
(4)分区筛法(NFS),目前对大于10110的数是最快的算法。曾被用来成功地分解过第九费马数。这些算法代表了人们对大数分解(也就是对RSA攻击)的探索历程。最好的算法具有超多项式率(次指率)的时间复杂度,NFS具有最接近于多项式率的表现。
但是随着计算机能力的提高和因子分解算法的不断改进,其中计算能力的提高包括由于计算机网络的发展所导致的联网众多计算机进行分布式计算能力的大力提高,将会对RSA的安全性造成较大威胁。
4 结束语
RSA算法是第一个同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛、最优秀的公钥方案之一。专家指出,就目前的计算机水平用1024-BITS的密钥是安全的,2048-BITS是绝对安全的。但是他们并不指望这个局面延续到下世纪,他们只是指出:如果RSA像有些人说的那样脆弱,就不可能从1978年一直保持到现在还没有被攻破。
摘要：RSA算法是一种公钥密码算法。RSA是一个基于数论的非对称密码体制,RSA的安全性是依赖于大整数素因子分解的困难性问题。其经历了各种攻击,至今未能被完全攻破。
关键词：公钥密码,RSA算法,加密,解密,安全性
参考文献
[1]Diffie W,Hellman M.A New Direction in Cryptography[J].IEEETrans on Info.Theory,1976,22(6):644-654.
[2]Rivest R L,Shamir A,Adleman L.A Method for Obtaining DigitalSignatures and Public-key Cyptosystem[J].Comm ACM,1978,21(2):120-126.
[3]Delaurentis J M.A Further Weakness in the Common Modulus Proto-col for the RSA Cryptosystem[J].Cryptologia,1984,8(3):253-259.
[4][美]Paul garrett.密码学导引[M].吴世忠,译.北京:机械工业出版社,2003.
【圆锥曲线密码体制】推荐阅读：
圆锥曲线教学07-24
圆锥曲线成形面07-13
圆锥曲线的简单应用07-10
解读高考圆锥曲线试题07-28
圆锥曲线中的共性问题06-08
圆锥曲线中的两个性质06-12
圆锥曲线中的最值问题05-19
椭圆曲线密码05-08
圆锥轴承06-08
圆锥体积公式07-13