资源描述：
《中国剩余定理在rsa解密中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、文章编号：1001-9383(2003)03・0138・06中国剩余定理在RSA解密中的应用贺毅朝I，刘建芹2,陈维海彳(11石家庄经济管理学院信息工程系,石家庄()5()()0();21石家庄信息工程职业学院,石家庄0500353.中国华融资产管理公司石家庄办爭处，石家庄050000)【摘要】在分析RSA密码算法实现原理的基础上，若重论述了利用单基数转换法(SRC)和混合基数转换法(MRC)计算屮国剩余定理惟一解的方法以及利用这两种方法快速实现RSA的解密算法。【关键词】PKC算法；川国剩余定理；RSA算法【中图分类号】TP311.56;O156【文献标识码】AThea
2、pplicationofCRTtoRSAdecryptionHEY2chao!JL1UJian2qin2,CHENWei2hai3(I•CollegeofInformationEn^ineering,ShijiazhuangUniversityofEaonnomi(^9Shijiazhuang()50000,China;2.ShijiazhuangInformationEngineeringVocationalCollegetShijiazhuang050035,China;3.ShijiazhuangOfficeofChinaHuarongAssetsManagemen
3、tsCorporation,Shijiazhuang0500009China)AbstractBasedonanalysisoftheprincipleofRSAimplementation,theapplicationissuesofSin2gle2RadixConversion(SRC)andMixed2RadixCbnversion(MRC)algorithmsonChineseRemain^derTheorem(CRT)andhigh2speedrealizalionofRSAdecryptionusingabovemethodswereilliuminatede
4、mphatically.Keyw)rdsPKCalgorithm;ChineseRemainderTheorem(CRT);RSAalgorithm1978年美国麻省理工学院的三位教授R.L.Rivest,A.Shamir和M.Adleman捉出了一种以基于因子分解的指数函数作为单向陷门函数
5、(One2wayTrapdoorFunclion)的公开密钥密码算法(Public2KeyCryplosyslemPKC)，即著名的RSA算法$。RSA算法是第一个较完善的PKC算法，也是非常容易理解和实现的PKC算法。它既可用于对传输信息的加密，也可用于数字签名系统，是当前民用与商
6、业中使用故广泛的公开密钥密码算法Z—，己被国际标准化组织ISO、ITU和SWIFT接受为标准。RSA的安全性是基丁-分解大数的难度该算法在经受了多年深入的密码分析之后，虽然密码分析者既不能证明同时也不能否定其安全性，但这恰恰说明了RSA算法的可信度。因此，可以毫不怀疑地断言：RSA是安全的PKC算法。屮国剩余定理(又称孙子定理)是数论中的基木定理，但在计算机密码学屮冇着重要的应用。例如在Ra：bin密码算法屮用于解密运算。在RSA密码算法中，屮国剩余定理同样可用RSA的解密运算，而且使RSAM解密速度大约提高4倍左右，这无论对于软件还是硬件实现RSA密码算法都是非常重要的
7、。E收稿日期:2003-()3-()7作者简介:贺毅朝(1969-)，男，硕士，讲师，主要从事汁算机密码学和算法分析与设计研究1RSA密码算法随机选取两个不同的大素数〃和g(约为150位或更大的十进制数几计算它们的乘积N=pq耳相应MEuler函数(EulerTotientFunction)<(N)=(p-i)(q-1)的值,将N公开,而将<(N)、p与q保密;显然,如果在不知道N的素因子p与q的前提下，计算<(N)的值是属于NP问题，极难实现。再随机选取一个正整数"使e•满足条件:e8、id算法(ExtendedEuclideanAlgorithm)3计算d=e'1(mod<(N)),即计算满足ed—](modVN))的d。将e公开，而将〃保密，就确定了RSA算法的公开密钥PK=(e,N),私人密钥SK=(dN)，密钥空间.•K={(N,p,q,e,d)N=pq,p与g为不同大素数,ed三1(mod<(N))}。相应地.RSA算法中的单向陷门函数为0幻=xr(modN丿(其中t且xWZQ,称为RSA函数。具秘密陷门信息为及索数八q的值。确定公钥PK=(e,N)和私钥SK=(d,N)Z后，RSA算法的加密运算
