资源描述：
《论文英语翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、PublicKeyCryptologyIn1978,RonaldRivest,AdiShamir,andLeonardAdelmanpublished“AMethodforObtainingDigitalSignaturesandPublicKeyCryptosystems.”Inthispaper,theauthorsdescribeamethodofsendingcodedmessagesusingapairofpubliclyavailableintegers.Thismethodiswidelyc
2、alledtheRSApublickeycryptosystem.WebeginwitharesultoncongruencesthatextendsFermat’sLittleTheorem.Theorem1Supposethatpandqaredistinctprimesandkisanyinteger.Then(a)ForanyintegerawithGCD(a,pq)=1,a^k(p-1)(q-1)≡1(modpq)(1)(b)Foranyintegera,a^k(p-1)(q-1)+1≡a(mo
3、dpq)(2)Proof(a)IfGCD(a,pq)=1,thenaisnotdivisiblebyporq;itisrelativelyprimetoboth.ThusbyFermat’sTheorem,wohavea^p-1≡1(modp),andsoa^k(p-1)(q-1)≡1^k(q-1)=1(modp).Similarly,a^k(p-1)(q-1)≡1(modq).Thusthereexistintegersrandswitha^k(p-1)(q-1)=1+rp=1+sq.Itfollows
4、thatrp=sq,andsinceqisnotdivisiblebyp,smustbe,says=pt.Thena^k(p-1)(q-1)=1+pqtanda^k(p-1)(q-1)≡1(modpq).(b)Ifaisrelativelyprimetopq,theresultfollowsfrom(1)bymultiplyingbothsidesbya.Ifnot,thenaisdivisiblebyeitherporqorboth.Ifaisdivisiblebypq,thenbothsidesof(
5、2)arecongruentto0modpqandarethereforecongruenttoeachother.Intheremainingcase,aisdivisiblebyexactlyoneoftheintegersporq,andwithoutlossofgenerality,wemaysupposethatitisp.Thena=b^s,withs≥1andbrelativelyprimetopq.Wenoteforlaterreferencethatbmustsatisfy(2).Sin
6、cepisrelativelyprimetoq,wecanshowasintheproofofpart(a)thatforsomeintegerr,p^k(p-1)(q-1)=1+rq.Multiplyingbypthenshowsthatp^k(p-1)(q-1)≡p(modpq),andtherefore(p^s)^k(p-1)(q-1)=(p^k(p-1)(q-1)+1)^s≡p^s(modpq).Weseethatbothbandp^ssatify(2),andthereforesodoesthe
7、irproducta.DecodingSincesischosentoberelativelyprimeton,s，theremainderclassofsmodn,hasamultiplicativeinversetintheringZn.Thusforsomeintegerrwehavest≡1(modn)orst=1+k(p-1)(q-1)forsomeintegerk.WecanfindtbyusingtheEuclideanalgorithm.Ifwereceivetheintegery=x^s
8、(modm),wecomputey^t(modm)andapplyTheorem1.Sincem=pq,Theorem1(a)guaranteesthaty^t=x^st=x^1+k(p-1)(q-1)≡x(modm).Sincexdoesnotexceedm,wehavey^t(modm)=x,sowehaverecoveredtheoriginalintegerx.Wedothistoallreceivedintegers
