基于身份公钥密码体制

基于身份公钥密码体制（共4篇）

基于身份公钥密码体制 篇1

近年来无线通信正在迅速发展,笔记本式计算机,PAD等终端手持设备以其方便灵活性在无线通信中迅速发展,但无线通信的安全至关重要,现在越来越多的焦点转向用户身份的安全认证。在用户被授权接入网络以前,GSM和UMTS等蜂窝网使用对称加密算法去执行认证和会话密钥管理。对于无线局域网[1](WLAN),对称加密算法RC4的WEP(Wired Equivalent Privacy)协议中说明:即使对无线接入控制采用对称加密技术的认证机制,安全漏洞还是很容易被发现。同时对于克服安全漏洞的无线通信的公钥加密认证协议相继被提出,但大多计算复杂度都很高,后来有人提出使用ECC(Elliptic Curve Cryptosystems)方法进行加密和会话,尽管减少了一些计算复杂度,但没有对用户会话密钥进行检验,网络没有得到认证,用户无法辨认。

本文使用了对称加密算法AES和非对称加密算法NTRU和HASH函数在无线网络中构建双向认证和会话密钥管理协议。NTRU[2]是一种新的公钥加密体制。它是一个在多项式环Z[X]/(XN-1)上的密码系统。NTRU的优点是在高安全等级时有较高的加解密速度、签名验证速度和密钥生成速度,因此被使用在无线网络环境中。NTRU的安全是基于多项式环上的最近向量问题,也是一个NP问题。

1 无线通信网络安全要求

相比有线,无线传输的信息更容易被窃取和篡改,一些常见的无线通信威胁包含窃听移动用户身份和用户谈话内容,假装合法用户,追踪用户位置。因此,安全认证是非常重要的,所以无线网络基本安全要求是:1)无线传输信息保密;2)用户位置信息保密;3)防止认证中的伪装;4)防止重复攻击;5)防止不可抵赖性服务。

此外,由于非对称加密有一定的计算复杂度,认证机制应该有更少的计算复杂度和用户存储要求。交换信息应该保持在有限带宽范围。

2 无线通信双向认证协议

协议主要符号名称及其代表意义如表1所示。

由于NTRU[3]系统工作在多项式环R= Z[X]/(XN-1),元素F∈R将被看成一个多项式或向量

$\mathit{F}={\displaystyle \sum _{i=0}^{{\rm N}-1}F}{}_i^{}X{}_{}^i=[F{}_0^{},F{}_1^{},\cdots ,F{}_{{\rm N}-1}^{}](1)$

使用“*”表示在R中的卷积运算。例如,设F∈R和G∈R,使H=F*G可表示为

${\rm H}{}_{{\rm K}}={\displaystyle \sum _{i+j\equiv k(\text{m}\text{o}\text{d}{\rm N})}F}{}_{i}G{}_i$,0 ≤ k < N (2)

因为H=F+G,在多项式环R= Z[X]/(XN-1)计算H 的系数为

HK=FK+GK (3)

本文使用NTRU加密算法和签名算法构建认证协议,在NTRU算法中基本的安全参数{N,p,q,Lf,Lg,Lm}能共享,系统参数为{Dmin,Dmax,L&#x03D5;,Lw}。通常指定P =3,p和q互为素数。在参数中,{Lf,Lg,L&#x03D5;,Lw,Lm}被指定为N-1阶多项式样本空间。Dmin和Dmax是验证NSS签名的边界参数。Dev(a,b)表示在多项式环a(mod q)和b(mod q)系数不同的个数。

假设在协议中有一个发证机构CA(Certifying Authority)创造和分发证书给用户和网络认证服务器AS(Authentication Server)。CA包含一个请求接入的临时身份,这个身份可能是用户或AS。文中不区分MS即用户和订阅者。

在用户和AS执行真正的注册之前,首先从CA获得自己的证书,也就是初始化。文中假设发布证书是足够安全的。

2.1 双向认证初始化过程

在初始化中,CA发布证书给用户和AS,CA先为NSS签名算法产生公钥和私钥对,随机选择两个多项式:f∈Lf,g∈Lg满足f=f0+pf1和g=g0+pg1,f0和g0通常是固定的(f0=1和g0={1,-1})。然后计算公钥

h≡f${}_q^{-1}$*g(mod q) (4)

f${}_q^{-1}$是f的逆,满足

f${}_q^{-1}$*f≡1(mod q) (5)

CA产生公钥PKCA=h,保密私钥SKCA=f。假设用户和AS都知道f0和g0。

在用户初始化过程中,用户首先选择两个随机多项式SKu∈Lf和gu∈Lg,然后根据加密算法计算公钥PKu。用户保留公私钥对,然后通过安全信道发送信息,信息包含公钥和IDu给CA,在CA收到信息后,CA使用私钥和NSS签名算法时信息进行签名,信息是HASH函数对公钥、临时身份TIDu和作为用户证书Cu的有限期限tu的串联,用户的CA有唯一的TIDu,成功后,CA发送证书Cu,PKCA,TIDu和tu给用户,收到后,用户核查证书信息。

同理在初始化中提到的AS也从CA得到Cs,TIDs,ts和PKCA。

2.2 双向认证执行过程

在初始化完成后,认证过程开始执行。图1显示了详细的执行过程。

步骤1:用户发送信号给服务器尝试登入,在图中省略这步,接入后,AS选择随机多项式rs。然后AS发送证书Cs同时携带公钥PKs,临时身份TIDs和证书有效时间ts和rs给用户。

步骤2:在步骤1收到信息后,用户首先核查ts是否有效。假如不是,认证过程将被终止。反之,用户根据NSS签名算法[4]核查AS的证书,在核查中,用户选择3个随机多项式: &#x03D5;u,ru1,ru2,其中ru1是作为密钥[5],加密签名ru2防止中间攻击,并且ru2被用作对验证AS的应答。然后,用户通过NTRU加密算法加密ru1||ru2得到eu。

随后,用户通过签名HASH函数的摘要,即串联TIDu,TIDs,eu和rs计算su,这是作为使用NSS签名的应答。最后,用户发送eu和Cu,TIDu,PKu,tu,su给AS。

步骤3:收到用户的信息后,AS核查tu,假如过期,认证终止。反之,验证用户的证书,首先用HASH函数计算用户的PKu,TIDu和tu,得到mu。然后根据NSS,核查Dev(f0*mu,Cu)∈[Dmin,Dmax]是真的还是假的,假如是真的,还需要核查Dev[g0*mu,Cu*PKCA(mod q)]是否在[Dmin,Dmax]中。假如都通过了,则验证了用户的证书。然后解密eu去获得ru1和ru2。为了判断ru1的正确性,和核查用户的身份篡改和假扮,AS仍然需要验证签名su。假如所有以上验证都通过了,用户通信是合法的,然后产生ru2的签名ss,用户可以使用ss验证AS的身份,然后发送用对称密钥ru1加密的签名ss给用户。

步骤4:在收到加密数据后,用户计算D(E(ru1,ss),ru1)去获得AS的签名ss。然后用户通过NSS签名算法验证AS的身份。假如通过了,用户和AS之间的验证就完成了。最后通过TIDu,TIDs,ru2和rs获得会话密钥Ksu

Ksu=h(TIDu||TIDs||ru2||rs) (6)

3 方案性能分析

3.1 安全性分析

该方案很好地满足了上文描述的安全要求,在协议的时间认证过程中真实的身份没有传输,只有使用临时的身份,因此,攻击者不能窃取用户的身份和发送追踪攻击。攻击者可以在无线通信时通过中断信息传输来攻击协议,攻击者也能获得用户和AS的公钥,但是很难从公钥找到私钥,因为很难在最大格中找到最短向量。所以,攻击者不能找到加密信息,并且伪造签名。协议也能防止攻击者假冒用户或AS,用户到AS的应答被用户签名,攻击者不能得到用户的私钥和伪造签名,因此,这种攻击也是失败的。

直到认证结束,两边都能计算会话密钥。每一次认证,会话密钥是不同的,因为随机数ru2是被保密和更新的。随机数的更新使得会话密钥更新,因此协议能有效抵制已知明文攻击。用户侧协议的计算复杂度比其他协议更低,因为通过NTRU加密的基本运算仅仅涉及小于255的数。NTRU加密和解密比ECC[6]快大约2个数量级。

此外,仍然可以优化算法提高协议安全,通过采用填补技术,NTRU能防止选择密文攻击,使得方案更安全。通过低汉明权重的使用,加密解密和签名速度能被提高。

3.2 高效性分析

以下NTRU算法的实现完全采用Java语言编写[7], JDK为SUN公司提供的J2SE5.0, 模拟器为SUN公司提供的WTK2.2。试验用PC的CPU为AMD Athlon 2.20 GHz。试验分别对RSA (Rivest-Shamir-Adleman)、ECC和NTRU进行加密数据分析,结果如表2所示。

由表2可见,在相对安全级下,NTRU在加解密速度上较ECC[8]和RSA算法有明显优势,所以使用NTRU算法加快了加密速度,解决了在双向认证过程的延时问题,使无线通信加密过程在安全状态下运行。

下图2为3种加密算法签名认证过程的时延曲线,其中NTRU比ECC和RSA明显时延短,最后趋于稳定。

4 小结

本文提出了运用NTRU公钥加密算法、对称加密算法和HASH函数的一种新的双向认证方案,该协议不仅能克服一些常见的安全漏洞,也能满足无线非对称加密的需求。目前NTRU算法仍然在发展,有待完善,其安全等级高、速度快、计算复杂度低等特性,使其适于为将来的无线通信网络提供安全保障。

摘要：安全问题是无线通信网络亟待解决的关键问题之一,因为无线通信中的身份问题存在严重的安全威胁,容易受到多种攻击。针对此问题提出了一种新的无线通信方案,基于NTRU(Number Theory Research Unit)公钥加密体制的双向认证和密钥管理协议,使用非对称加密算法、HASH函数和NSS(NTRU Signature Scheme)签名算法等技术建立这个协议。在执行双向认证和会话密钥管理协议中包含协议初始化和协议执行两个过程。该协议较目前公钥加密提供了更低的计算复杂度,加快了运行速度,增加了安全性。

关键词：双向认证,NTRU,NSS,无线通信

参考文献

[1]张斌,汤红波,张汝云,等.下一代无线局域网安全性研究[J].电视技术,2007,31(1):62-64.

[2]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring based publickey cryptosystem.[C]//Proc.Algorithmic Number Theory.Berlin:Springer-Verlag,1998:267-288.

[3]HOFFST EIN J,PIPHER J,SILVERMAN J H.NTRU:a new high speedpublic key cryptosystem[C]//Proc.ANTS.Berlin:Springer-Verlag,1998:267-288.

[4]JEFFREY H,JILL P,SILVERMAN J H.NSS:the NTRU signaturescheme[C]//Proc.Eurocrypt2001.[S.l.]:Springer-Verlag,2001:211-228.

[5]DAEMEN J,RIJNDEAN V.高级加密标准(AES)算法-RIJNDEAL的设计[M].北京:清华大学出版社,2003.

[6]MENEZES A J,OORSCHOT P C,VANSTONE S A.应用密码学手册[M].北京:电子工业出版社,2005.

[7]徐迎晓.安全性编程实例[M].北京:清华大学出版社,2004.

[8]金纯,聂增丽.数字电视多媒体消息业务认证系统安全研究[J].电视技术,2011,35(11):01-04.

基于身份公钥密码体制 篇2

从1978年Mc Eliece[1]提出M公钥密码体制以来,基于纠错码的公钥密码体制引起了广大学者的高度重视。1986年,Niderreiter[2]又提出N公钥体制。传统的M体制和N体制是以Goppa码为基础的,加解密简单,安全性高,但是存在公钥量大,传信率低等弱点,因此很少在实际中应用。随着纠错码的发展,用除Goppa码外的其他高性能纠错码,如BCH码,RS码,秩距离码,代数几何码及LDPC码等不同的码类构造公钥体制成为许多学者研究的主要内容,极大地促进了基于纠错码的公钥密码体制的发展。随着计算机水平的提高,传统的单公钥密码体制已经不再满足安全性需求。2008年,岳殿武、 张颖等人[3]利用双公钥对基于代数几何码的M公钥密码体制进行改进,提高了密码体制的安全性。2010年,杜伟章、杨磊鑫等人[4]也利用双公钥对传统的N公钥密码体制进行改进,增加解密复杂度, 提高了安全性。另一方面,在复杂环境下,实际传输信道中产生的错误一般是突发错误或者是突发错误和随机错误并存。尤其是在复杂环境的高速移动无线电波传输下,反射、绕射和障碍物的吸收都会使信号发生多径衰落,导致接收端收到数据可靠性下降。 此外,大部分纠错码都是在编码较长的时候能够有很好的性能,例如LDPC码,码长越长,越能够体现出其巨大的优势,然而在许多时候,例如对空传输控制指令,通信系统传输的编码都较短,RS码是通信系统中比较常用的码类,具有很强的纠正短突发错误的能力,构造简单,容易实现,尤其适合编码较短的情况。根据以上特点,本文提出基于RS的双公钥Niderreiter密码体制,既提高了纠错能力,又适合在编码较短的情况使用,且易于工程实现,在山峰、 海面等复杂环境下实用性较高,且安全性较传统的基于纠错码的公钥密码体制高。

1基本概念

1.1N公钥密码体制

设G为GF( 2) 上的( n,k,l) 二元既约Goppa码的k × n阶生成矩阵,设H为 ( n - k) × n阶一致校验矩阵,S是 ( n - k) × ( n - k) 阶可逆矩阵,P是n × n阶置换矩阵,计算H' = SHP ,令公钥为H' ,私钥为S、H、P ,明文m是GF( 2) 上长为n的比特向量,密文c是GF( 2) 上长为n - k的比特向量。

加密算法:

集合M是由GF ( 2 ) 上所有汉明重量等于t的n维矢量构成,。 而c与m实质上就是伴随式与错误图样的关系,且码能纠t个错误,因此, c与m之间必然存在一一映射关系,从而保证解密唯一性 。

解密算法:

1计算c ( ST)-1= m PTHT;

2利用Goppa码的快速译码算法对m PTHT进行快速译码,得到m PT,计算m PT( PT)-1,恢复明文m 。

目前,对于N体制最有效的攻击方法是解线性方程组,攻击式 ( 1 ) 的工作因 子为WN= ( n - k)3Ckn/ Ckn - t。设n = 1024 ,k = 1024 - 10t ,当t = 41时,N体制具有最高安全性,最高工作因子为WN= 282。传统N体制的加密、解密实际上是进行Goppa码的译码,根据Goppa码的快速译码算法,其计算复杂度为O( n log2n) 。N体制的公钥量是 ( n k) × n ,传信率是 ( log2Ctn) /( n - k) 。当n = 1024, t = 41时,N体制公钥量为42万比特,传信率为0. 59,由此可知,N体制公钥量较大,而传信率较小。 根据工作因子、公钥量及传信率随t的变化关系,在N体制中,t应该选用小的。

综上所述,虽然传统N体制的加解密有Goppa码的快速译码算法,计算复杂度较小,但是由于公钥量较大,传信率较低,不宜投入工程应用。

1. 2 RS 码

RS码,Reed-Solomon codes,由Irving Reed和Gus Solomon两人[5]于1960年首次提出,是一类具有很强突发性错误处理能力的多进制BCH码,在卫星通信、磁记录系统及数字电视传输等领域得到广泛应用。

RS码是q进制的BCH码 ,q = 2m,即每个q进制码元均可以表示成为m比特。每个码元取值为q元符号集 {0,α0,α1,…,αq -2} ,实际情况通常取q = 2m,使得q元符号集的非零元素 { α0,α1,…,αq -2} 是GF( 2m) 上的元素。一个可以纠正任意小于或者等于t个错误的RS码基本参数如下:

码长: n = q - 1;

校验位长: r = n - k = 2t ;

最小距离: d = n - k + 1 ;

生成多项式:

生成矩阵: G = [IkQk × r];

校验矩阵: H = [(Qk ×r)T,Ir]。

RS码的译码与其他线性分组码基本一致,分为三个步骤:

1根据接收到的码字计算伴随式S ;

2根据伴随式得到错误图样E ;

3根据接收码字与错误图样进行纠错计算,完成译码。

如果传输的信号是二元数据流,则连续m比特表示一个码元。由于任何少于m比特的差错都可能造成一个或者连续两个码元错误,所以RS码虽然能够纠正t个码元,但是只能够纠正任意连续 ( t - 1) m + 1个比特错误。根据这一特性,RS码成为二元信号传输中纠正短突发错误的首选纠错码之一。

2基于RS码的双公钥Niderreiter密码体制构建

根据RS码的特点,构建基于RS码的双公钥Niderreiter密码体制。密码体制流程如图1所示。

其中,公钥分别为Pk1和Pk2 ,Pk1 ,Pk1的私钥为Sk1 ,Pk2的私钥为Sk2 。

2.1参数设计

设多元 ( n1,k1,t1) 码C1和 ( n2,k2,t2) 码C2是GF( 2q) 上的RS码,n2= n1- k1,其生成矩阵G1、G2阶数分别为k1× n1,k2× n2,校验矩阵H1、H2阶数分别为 ( n1- k1) × n1,( n2- k2) × n2,纠错能力分别为。 在GF ( 2q) 上随机选取阶非奇异矩阵S1和阶非奇异矩阵S2,在GF ( 2 ) 上随机选取n1× n1阶可逆置换矩阵P1和n2× n2阶可逆置换矩阵P2,将两个矩阵中的 “1” 元素随机转换成多元域中非零的其他任意元素 。

计算

其中,H'1和H'2分别采用P1和P2替代传统N公钥密码体制中的置换矩阵,使得相同参数的P1和P2都增加至 ( 2m- 1)nn! 种,可以提高该体制的安全性。

最后可得参数如下:

公钥: H'1,H'2;

私钥: S1,H1,P1,S2,H2,P2,q 。

2.2加密算法

计算

其中,m为n1维明文向量,c1为 ( n1- k1) 维向量;

计算

其中,c2为 ( n2- k2) 维密文向量。

c2与m的关系,实质上是伴随式和错误图样的关系,因为该码能对t = min{ t1,t2} 个错误进行纠错,所以c2与m之间必定存在一一映射关系,从而保证解密唯一性。

2.3解密算法

当收到密文c2之后,通过以下步骤进行解密计算得到明文m :

1计算c2( S2T)-1,c2( S2T)-1= c1( P2TH2TS2T) ( S2T)-1= c1P2TH2T,通过RS码的快速译码算法对伴随式c2( S2T)-1进行译码,可以得到c1P2T。

2右乘 ( P2T)-1,计算c1P2T( P2T)-1得到c1。

3计算c1( S1T)-1,c1( S1T)-1= m H'1T( S1T)-1= m P1TH1TS1T( S1T)-1= m P1TH1T,通过RS码的快速译码算法对伴随式c1( S1T)-1进行译码,可以得到m P1T。

4右乘 ( P1T)-1,计算m P1T( P1T)-1,恢复明文m。

3安全性分析

经过双重RS码编码加密,体制安全性较传统的基于纠错码的公钥密码体制有了明显的提高。密码分析者进行分析需要的工作量接近于一次RS码加密的两倍。

现对该密码体制就可能的密码分析手段进行安全分析。

3.1直接译码攻击

c2与H'2、c1与H'1本质上就是伴随式与错误图样的关系。直接解方程( 4) 和( 5) ,就可以求出明文m 。但是,根据纠错码理论可知,一般线性码的最大似然译码是NPC问题,进而可以得出上述求解也为NPC问题,故该攻击方法不成立。

3.2直接解方程组

分析该密码体制最为常见的分析手段就是解线性方程组。与原始的分析N体制的方法不同,该方法需要分成两个步骤进行分析。

Step1:

设c2对应明文m = ( m1,m2,…,mn) ,令

设公钥分别为

式中,h'i和h″i分别为H'1和H'2的第i列,且

则有:

Step2:

在上述结果的基础上,分析方法类似,删除的分量数目为k1,最后解方程求得明文m 。

根据此密码分析方法,在Step1中解方程的工作因子为,密码分析者选取的概率为,因此在Step1中密码分析者分析 该体制的 工作因子 为; 同理,在Step2中密码分析者 分析该体 制的工作 因子为综上所述,通过该方法进行密码分析 的工作因 子为。 该工作因 子不是多项式时间,该密码分析算法不可行 。

3.3RS码码字特点攻击

相对于传统的基于Goppa码的M体制和N体制而言,采取RS码的N体制在相同参数的条件下的码字数目远远低于前者,密码分析者很容易猜出体制的私钥H1,也就是说,该方案以RS码为外码的安全性关键在于猜出一致性校验矩阵H1之后通过H'1分解出S1和P1的难度。文献[5]证明M体制在泄露私钥生成矩阵G的前提下仍然难以分解出S和P ,其难点在于求解二次非线性方程组的算法。同理,在N体制中,根据置换矩阵PT= P-1的特点,令H' = SHP ,则,则:

该问题转化为已知求解S的问题,一旦S被求解, P也可求解 。

将式( 6) 展开,化为n( n - k) 个联立的( n - k)2元二次非线性方程组。该问题最终转化成求解二次非线性方程组的问题。虽然目前没有求解二次非线性方程组的有效算法,但是一旦找到该算法,体制安全性将不复存在。因此,本方案将置换矩阵P1中的 “1”元素随机转换成多元域中其他非零元素,使得P1T≠ P1-1,此时矩阵分解问题再不能转化为求解二次非线性方程组问题,即使求解二次非线性方程组的算法被找到,在本方案中也不能从H'1中分解出S1和P1,且本方案是基于RS码的双公钥密码体制,公钥密码体制的安全性显著提高。

4性能分析

RS码是通信系统中常用的信道编码,构造简单,纠错能力尤其是纠正短突发错误的能力极强,尤其适合长度较短的编码。对于通信传输编码较短的信道,例如对空传输控制指令,遥控数据量较小,对纠错能力要求较高,尤其适合基于RS码的双公钥密码体制。该公钥密码体制的公钥量为 ( n1- k1) × n1+ ( n2- k2) × n2,纠错能力为t = min{ t1,t2} ,传信率为,公钥量为107400比特, R =0. 6217 。 显然,随着t的增加,该双公钥密码体制的公钥量增加 。 图1为当n1= 1024 , n2= 100时该双公钥N密码体制的传信率R随t的变化关系 。

从图2可得,随着纠错能力的提高,该密码体制的传信率降低。表1为不同的公钥密码体制的性能比较。

可以看出,与传统基于纠错码的公钥密码体制相比,该密码体制公钥量有所增加,但是在安全性有所提高的前提下,传信率也显著提高,尤其适合在通信编码较短或者环境较为复杂恶劣的情况下。

5结束语

纠错与加密结合,尤其是双公钥加密,对复杂环境下的密码系统是相当有意义的。根据信道传输编码的特点,选择合适的纠错码构建公钥密码体制,使得纠错能力、实用性、安全性都能得到兼顾。本文提出了基于RS码构建双公钥Niderreiter密码体制,克服了传统基于纠错码的公钥密码体制传信率低、实用性不强等弱点,可靠性和安全性较高,能够良好地适应编码长度较短的信道。在信道编码长度较短的情况下,该公钥密码体制一定能发挥重要的作用。

摘要：首先简要介绍了N公钥密码体制、RS码的基本概念,然后针对通信信道编码较短的情况提出了基于RS码的双公钥Niderreiter密码体制,最后对这种密码体制的安全性和性能进行了详细分析,证明了其安全性和性能要优于传统的基于纠错码的公钥密码体制,在复杂环境或者信道编码较短情况下的实用性也较高。

公钥密码RSA体制及安全性分析 篇3

公钥密码[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${}_i^e$(mod n) (1)

解密消息时,取第一个加密后的分组ci并计算式(2):

mi=c${}_i^d$(mod n) (2)

例如:设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${}_1^{-1}$modn,

则(C${}_1^{-1}$)-rC${}_2^s$modn=(me1)r(me2)smodn=

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,这就是普通的指数,即$m=\sqrt[e]{C}$。

所以使用加密指数e=216+1=65537(费马素数!)可以避免一些对小加密密钥e的攻击。

2.2.2 小解密密钥d攻击

1990年Micgael Wiener证明了,若d的长度小于模n长度的$\frac{1}{4}$时,利用连分数可在多项式时间内计算出d。这一论点使用了连分式的经典数论理论以及如何找到用有理数对二次无理数最合理的逼近方法。也就是说,对于1024位的模数,解密指数应该至少为256位。在1999年,D.B,G.Durfee,在preprint中报告这个结果可以被“改进”到甚至对于更大的解密指数也可以进行快速破解。

对于低指数攻击,对付的办法就是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.

基于身份公钥密码体制 篇4

一、椭圆曲线密码体制

椭圆曲线加密法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算法进行加解密、签名与验证签名,对网络的信息建立起良好的保护的屏障,能够很好地抵抗重放攻击、猜测攻击、网络窃听攻击,整个网络身份认证方案简单有效。

参考文献