资源描述：
《CRT_RSA算法安全性分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、信息安全中文核心期刊《微计算机信息》(管控一体化)2009年第25卷第1-3期文章编号:1008-0570(2009)01-3-0054-02CRT-RSA算法安全性分析SecurityofCRTbasedRSAAlgorithm（解放军信息工程大学）费晓飞胡捍英FEIXiao-feiHUHan-ying摘要:论文研究了引入中国剩余定理(CRT)的RSA算法,分析了其面临的主要安全威胁情形。针对具体的实现算法,分别给出了瞬时出错攻击、长期出错攻击和随机出错攻击方法与过程,发现大合数N会被分解。并提出了提高CRT-RSA算法安全性的
2、思路与对策。关键词:中国剩余定理;RSA算法;安全性;出错攻击中图分类号:TP393文献标识码:AAbstract:AfteranalyzingCRTbasedRSAalgorithm,wethinkofthethreatmodels,usetransientfaultattack,longlivedfaultattackandrandomfaultattacktocheckthesecurityofthealgorithm,andfindoutthatitispossibletofactorN.Finally,thecounte
3、rmea-sureispointedout.技Keywords:CRT;RSA;Security;FaultAttack术1引言RSA算法的安全性进行分析。公开密钥算法———RSA算法的安全性依赖于大合数分解，2基于CRT的RSA算法创公钥和私钥都是两个大素数的函数。为保证RSA算法有足够2.1中国剩余定理的加密强度，电子商务的SET(SecureElectronicTransaction)协中国剩余定理（CRT）：已知n1,n2,…,nk为两两互素的正整新议规定CA(CertificateAuthority)使用2048比特的R
4、SA密钥，其数，则同余方程组他实体使用1024比特的RSA密钥。密钥长度越大，大合数分解X≡bimodni的难度也越大，算法安全性也就越高。这样，在使用RSA对数模N有唯一解，其中i=1,2,…,k，bi为正整数，N=nln2…nk。据进行处理时，就需要进行大量的模幂运算，模幂运算的效率根据高斯算法(Gauss’sAlgorithm)，中国剩余定理的解为决定了RSA算法的数据吞吐率。X=(b1M1y1+b2M2y2+…+bkMkyk)modN，一般的模幂运算都采用二进制法或k进制法，设指数e二其中N=nl×n2×…×nk，Mi=N
5、/ni=n1n2…ni-1…ni+1…nk，i=1,2,进制表示为…,k,y满足y=Mi-1modn。由此可见，中国剩余定理为对高位iiie=(ee…ee)=e2i,e∈[0,1]宽(如1024bit)大数的模幂运算转化成对低位宽(如512bit)相对k-1k-210ii则k进制的模幂运算流程如下：较小的数进行模幂运算提供了可能。输入：m,e,n；输出C=memodn。2.2RSA中CRT的引入（1）每次扫描r比特，则k=2r，预先计算Mwmodn(w=2,3,4,在RSA算法中，n=pq,p,q是两个长度接近的大素数。由于…,k
6、-1)，并保存下来。n是两个素数的乘积，所以可令（2）将指数e分成s个r比特单元F，i=0,1,2,…,s-1。C=md(modp)ip，（3）计算C=modnC=md(modq)q，（4）for循环（从i=s-2到i=0）再根据中国剩余定理求出最终结果。根据费马小定理，计1）C=modn算上面两式仅需计算C=md1(modp)2）如果Fi≠0，则计算p，C=CC=md2(modq)，·modnq（5）返回C即为所得。其中d1=dmod(p-1)，d2=dmod(q-1)。这样把幂指数d减少r=1时，即为二进制算法，它是k进制的最
7、简单形式。算法至d1，d2。由于d的长度接近于n，而d1,d2能减少至n的一的时间复杂度为半，大大减少了计算次数。O(t)=(3/2)k3，基于中国剩余定理，RSA模幂运算可转化为以下运算过程：正因为算法复杂度较高，运算过程需要消耗大量的资源和（1）计算时间，RSA算法的应用受到很大的限制。Cp=Cmodp，而中国剩余定理（CRT）对于提高RSA算法的模幂运算效Cq=Cmodq；率有显著作用，因而被广泛应用。本文主要对此类基于CRT的（2）计算费晓飞:博士研究生讲师Mp=Cp^Dpmodp，-54-360元/年邮局订阅号：82-9
8、46《现场总线技术应用200例》您的论文得到两院院士关注信息安全Mq=Cq^Dqmodq；计算了一个错误值C’p≠Cp(modP)，而被正确计算出来。C’p和其中Dp=Dmod(p-1)，Dq=Dmod(q-1)，对于给定素数p、qCq就联合产生一
