中国剩余定理

RSA20092220093230120232013424RSA400715RSAChineseRemainderTheoremandRSAPublicKeySystemTangRongSchoolofMathematics&StatisticsSouthwestUniversityChongqing400715AbstractBasedontheChineseremaindertheoreminnumbertheory,thispapermainlydothefollowing:First,thispaperexpoundstheoriginoftheChineseremaindertheorem.ThisarticlefromthehistoricaloriginoftheChineseremaindertheoremtounderstandthistheoremanditsproofmethod,anddiscussandanalyzetheideasandprinci-plesofthetheorem.InadditionthispaperalsodiscussedtheChineseremaindertheoremincomputerapplicationofbignumbers.Second,fromtheperspectiveofcryptography,afastpublic-keyencryptional-gorithmbasedonChineseremaindertheoremisdiscussedinthispaperanditsprinciple,processandperformanceisanalyzed.KeywordscryptographyChineseremaindertheorembignumbercalcula-tionRSApublickeysystem1141.1.1\\\\\\\\[1]\:8:x´2mod3(1)x´3mod5(2)x´2mod7(3)70£2+21£3+15£2¡105£2=231247\\[2]\\[3]\\\702115(1)153571213751705731214(2)15227213357022315£2+21£3+70£2=233(3)23335710523k132k253k372k1yk132\a=b=c(a+kb)=b=c(k)cnk1+k232k1+k2+k332k2,k3(1)k2k33k1+k2+k332(2)k1k35k1+k2+k353(3)k1k27k1+k2+k372k1+k2+k3(1)k13257(2)k25337(3)k372355732k13753k23572k3k1;k2;k3k157323121.2ww357xyz8:w=3x+2(4)w=5y+3(5)w=7z+2(6)w3x¡5y=1(7)3x=7z(8)314(5)x=7z=3z=3k;k2Nx=7ky=(21k¡1)=5=4+(k¡1)=5(k¡1)=5=t1;t12Nk=5t1+1x=35t1+7(9)y=t1+4(10)z=15t1+3(11)w=105t1+23(12)t1=0w=231.3\131517(1)(2)(3)\\1247\\\(11701250)[4]\1801(17771855)\414\\(ChineseRemainderTheorem)1.4x´dimodpi(1·i·s)[5]1().m1;m2;m3;¢¢¢;mka1;a2;a3;¢¢¢;arx´ai(modmi)i=1;2;3;¢¢¢;rM=m1;m2;m3;¢¢¢;mkx=rXi=1aiMiyimodMMi=Mmii=1;2;3;¢¢¢;r.(Mi;mi)=1M0iyiMiM0i+yimi=1M0iMiM0i´1(modmi)MiM0i´0modmi1·j·ii6=jx0´aiMiM0i´ai(modmi)1·j·ixx´x0(modmi)1·j·ix´x0(mod[m1;m2;m3;¢¢¢;mr])(mi;mj)=1[m1;m2;m3;¢¢¢;mr]=mx0´x0modm1.5m1;m2;¢¢¢;mn2Ma0·amnnamia(amodm1;amodm2;¢¢¢;amodmn)nminn(1)(2)514100100100100[6]9998979599£98£97£95=89403930123684(33;8;9;89)123684mod99=33123684mod98=8123684mod97=9123684mod95=89413456(32;92;42;16)123684413456(33;8;9;89)+(32;92;42;16)=(65mod99;100mod98;51mod97;105mod95)=(65;2;51;10)123684413456(65;2;51;10)x´65mod99x´2mod98x´51mod97x´10mod9565£98£9795+2£99£97£95+51£99£98£95+10£99£98£97=3397886480´537140mod894039300x=y894039305371402.RSA2.1DESAES[7]nn(n¡1)=2(n¡1)nn(n¡1)=2(n¡1)n614[8]BAABB1976Di±eHellmanRivestShamirAdleman1977RSA[9]RSARSA1970JamesEl-lisRSACli®ordCocks19732.2RSARSApqnn=pqpqRSAEulerRSA[10]1().nnnn'(n)1.'(6)=2'(8)=4'(7)=6n'(n)=n¡12().a;bgcd(a;b)gcdgcd(a;b)=gcd(b;a)=gcd(¡a;b)=gcd(j¡aj;j¡bj)RSA3().na(a;n)=1a'(n)´1modn.714.(a1;a2;a3;¢¢¢;a'(n))n(a;n)=1(aa1;aa2;a3;¢¢¢;aa'(n))n'(n)Yi=1ai=kYi=1aaimodna'(n)´1modnn4().ppa2Nap¡1´1modpRSA[11]5.pqn=p¢qx(0·xn)kxk'(n)+1´xmodn.p-x4xp¡1´1modp'(p)=(p¡1)j'(n)xk'(n)+1´xk'(n)x´xmodppjxx´0modpxk'(n)+1´xmodpxk'(n)+1´xmodqxk'(n)+1´tp+xmodqtxk'(n)+1´t0q+xmodqt0tp+x=t0q+xtp=t0q(p;q)=1qjt(pjt0)xk'(n)+1´spq+x(s=t=q)xk'(n)+1´xmodn2.3RSApq150n=pq'(n)=(p¡1)(q¡1)n'(n)pqnpq'(n)ee:e'(n)gcd(e;'(n))=1e'(n)1d=e¡1(mod'(n))ed=1(mod'(n))dedRSAPK=(e;n)SK=(d;n)K=(n;p;q;e;d)jn=pq;p;qed=1(mod'(n))RSAf(x)=xtmod(n)(t2Kx2Zn)RSA'(n)pqPK=(e;n)SK=(d;n)814c=Epk(m)=me(modn)1·m·n¡1m=Dsk(c)=cd(modn)1·c·n¡1RSAm1n¡1m2[1;n¡1]mnm=msnS+ms¡1nS¡1+¢¢¢+m1n+m0m=(m0;m1;¢¢¢;ms)mi2[1;n¡1];0·i·sc=(c0;c1;¢¢¢;cs)c1m1(1)RSA[12](a)n=p¢q()'(n)=(p¡1)(q¡1)(b)ee:1·e'(n)gcd(e;'(n))=1(c)e¢d=1(mod'(n))dnep;q;d(d)c=Epk(m)=me(modn)(e)m=Dsk(c)=cd(modn)RSA(2)RSAp=13q=17n=13£17=221'(n)=12£16=192e=71dd=e¡1mod'(n)=71¡1mod192=119nepqdRS(a)m5Aemcc=memodn=571mod221=112AcB(b)BAcdBAm[13]m=edmodn'(n)='(pq)=(p¡1)(q¡1)gcd(e;'(n))=1pqmde´1(mod'(n))de=1+k'(n)kcd´(me)d´m1+k'(n)´m(m'(n))k´m¢1k´mmodnnecpqdnd'(n)pqdndc=memodncem914m3´3(mod85)31:2599::::::85m=7nBpqpq100p¡1np¡12.4RSARSAneABABneRSARSARSARSADES100[14]RSA(1)RSA[15](a)npq'(n)=(p¡1)(q¡1)dRSA(b)n'(n)'(n)de´1mod'(n)dRSAd'(n)n'(n)nn'(n)(c)n'(n)dn'(n)d(ed-1)'(n)p+q=n+1¡'(n)dnd'(n)RSARSAn[15]2.5RSA(1)RSA1014(a)nne1e2(e1;e2)=1me1e2c1=me1(modn)=c2=me2(modn)c1c2rsre1+re2m(b)pn1=pq1n2=pq2(n1;n2)=pn1;n23.RSA[16]3.1[17]33.1.1k6pt(t2[1;6])¡=(lmn)6£6bitª¡ª=ª¡=I6n=p1p2¢¢¢p6li,lipi¡n[18]lijli´lijmodpt(t2[1;6])lijptliptlin=p1p2¢¢¢p6limodnbnb1;b2¢¢¢;b5l6;p1;p2;¢¢¢;p6ª3.1.2mm=(m1;m2;m3;m4;m5)T°°2Znc´b1m1+b2m2+¢¢¢+b5m5+°modn11143.1.3cs´l6c(modn)si´s(modpi)sis(modpi)(m1;m2;m3;m4;m5;°)T=B(s1;s2;s3;s4;s5;s6)Tm=(m1;m2;m3;m4;m5)T3.23.2.1RSA322[19]3.2.2n61998bitRSA-1024[19]4.\(1)(a)1214(b)RSARSA\\[1].[M].[2].[M].1247[3].[M].1592[4]PulrichLibbrecht.Chinesemathematicsinthethirteenthcentury[M].OverseaPublishingHouse,2006[5].[M].,1998[6].[J].:,Vol.37,No.4(2012).[7].[M].2004[8]PaulGarrett.[M].,2003[9]DouglasR.Stinson.CryptographyTheoryandPratice[M].2003[10].[M].2003[11],.()[M].,1986[12],,.RSA[J].,Vol.20,No.3(2003).[13],.[M].,2005[14]WadeTrappe,LawrenceC.Washington.CryptigraphywithCodingTheory[M].,2004.[15].[M].,2002[16]WDi±eandMEHellmanNewDirectioninCryptography[J].IEEETransactionsonIn-formationTheory,Vol.32,No.14(1976).[17].RSA[J].,Vol.27,No.3(2006).[18],,.[J].,Vol.27,No.10(2008).[19],,.[J].,Vol.35,No.3(2008).1314j.!20134241414RSA2220093230120232009201212121.2.(1)(2)RSA3.Latex(1)201212