格理论与格基约减算法在公钥密码分析学中的应用.研究

《格理论与格基约减算法在公钥密码分析学中的应用.研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、山东大学硕士学位论文ABSTRACTLatticeandlatticebasisreductiontheories&algorithmshavebeenactingasefficient&versatiletoolsaswellasplayingamoreandmoreimportantroleinthefieldofcryptanalysisoverthedecades．Backin1990，anattackusingLLLreductionalgorithmsucceededinbreakingthekn

2、apsack·-problem··basedpublic·-keycryptosysteminpolynomialtime．whichisknown硒thefirstsignificantlysuccessfulapplicationofthemethod．SinceDonCoppersmithproposedhisLLLalgorithm—basedmethodswhichCanbeusedforsolvingbothunivariatemodularequationsandbivariateequatio

3、nswithintegercoefficientsandsmallroots，variouskindsofapplicationsofhismethodshaveraisedtoanalyzetheRSAcryptosystemanditsvariantsinthepastfewyears．Forinstance，thelow-exponentattackonRSAproposedbyBoneh&Durfeeintheyear2000，thepartialkeyexposureattacksonRSAprop

4、osedbyB16mer,Ernest，theattacksonmanysortsofRSAvariants，etc．．Amongsttheseachievements，manyresultshavebeenproposedmostrecently．Alltheresultsaboveleadtoanundeniablefactthatnowadayslattice-basedmethodsareplayingamoreandmoreimportant&essentialroleinthefieldofpub

5、lic-keycryptanalysis(Infact．1attice-basedattacksareknown硒oneofthetwomostefficientincryptanalysingRSA-basedsystems，theotheroneisthenumberfieldsieve(NFS))．Moreover，therearestillincrediblymanyapplicationsofthemethodswhich剐℃stillunknownareyettobediscovered．Them

6、ainachievementinthisarticleistheimprovementtotheboundproposedbyCoppersmithontheproblem：factoringwithhighorderbitsknown．AccordingtoCoppersmith,whenh。ws({一os：Ⅳ)ht曲erbb。fp。眦c锄t．act。rⅣw油；npolynomialtime．Inthisnewapproach，itWasprovedthatwhenRSAprivatekeyd<0．483，

7、knowingasmallerfractionofpissufficientinyieldingthefactorizationofNin4山东大学硕士学位论文polynomialtime．Despitethefactthattheresultisasymptotic&heuristic．itcanoutputavalidresultwithalloutstandingprobability．Moreover,itisallefficientalgorithmwhichcallbecompletedintim

8、epolynomial．Besides，severalnewunderstandingsaswellassomeexpansiontotheoriginalapplicationsofCoppersmith’Stheorem，whichmainlyincludestheanalysisofmoregeneralcases，havealsobeenproposedintheformerchapter．