资源描述：
《using LLL-Reduction for solving RSA snd Factorization Problem.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、UsingLLL-ReductionforSolvingRSAandFactorizationProblems:ASurveyAlexanderMayDepartmentofComputerScienceTUDarmstadt64289Darmstadt,Germanymay@informatik.tu-darmstadt.deAbstract.25yearsago,Lenstra,LenstraandLovaszpresentedtheircelebratedLLLlatticereductio
2、nalgorithm.AmongthevariousapplicationsoftheLLLalgorithmisamethodduetoCoppersmithforfindingsmallrootsofpolynomialequations.WegiveasurveyoftheapplicationsofthisrootfindingmethodtotheproblemofinvertingtheRSAfunctionandthefactorizationproblem.Aswewillsee,mo
3、stoftheresultsareofadualnature:Theycaneitherbeinterpretedascryptanalyticresultsorashardness/securityresults.Keywords:LLLreduction,Coppersmith’smethod,RSA,Factoring1IntroductionTheRSAcryptosysteminventedbyRivest,ShamirandAdleman[74]in1977istoday’smosti
4、mportantpublic-keycryptosystem.LetusdenotebyN=pqanRSA-moduluswhichistheproductoftwoprimesp,qofthesamebit-size.Letebeanintegerco-primetoEuler’stotientfunctionφ(N)=(p−1)(q−1).TheRSAencryptionfunctiontakesamessagemtotheethpowerintheringZN.ThesecurityofRS
5、AreliesonthedifficultyofinvertingtheRSAencryptionfunctionontheaverage,i.e.extractingethrootsintheringZN.WecallthisproblemtheRSAinversionproblemortheRSAproblemforshort.Letdbetheinverseofemoduloφ(N).ComputingdthpowersinZNinvertstheRSAencryptionfunction.Si
6、ncedcanbeeasilycomputedwhentheprimefactorizationofNisknown,theRSAcryptosystemisatmostassecureastheproblemofcomputingdandtheproblemoffactoringN.Indeed,onecanshowthatthelasttwoproblemsarepolynomialtimeequivalent.However,itisoneofthemostchallengingproble
7、mstoproveordisprovethepolynomialtimeequivalenceoftheRSAproblemandtheproblemoffactoringN.Thereareresultsthattheseproblemsarenotequivalentunderrestrictedreductions[20].Ontheotherhand,onecanshowthatinrestrictedgenericattackmodels,bothproblemsappeartobeeq
8、uivalent[21,57].DespiteconsiderableeffortstoattackRSA(see[11,53]forsurveys),thecurrentlybestwayisstilltofactortheRSAmodulus.Consequently,researchersfocussedforalongtimeontheconstructionoffactorizationalgorithmsforattackingRSA.Inthisfactorizatio
