small primitive roots and malleability of rsa moduli

《small primitive roots and malleability of rsa moduli》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SmallprimitiverootsandmalleabilityofRSAmoduliLuisDieulefait†,JorgeJim´enezUrroz∗†Dept.Algebra.UniversitatdeBarcelona´∗Dept.Matem`aticaAplicadaIV.UniversitatPolit`ecnicadeCatalunyaCampusNord,c/JordiGirona,1-3,08034Barcelonae-mail:ldieulefait@ub.es,jjimenez@ma

2、4.upc.eduAbstractIntheirpaper[9],P.PaillierandJ.VillarmakeaconjectureaboutthemalleabilityofanRSAmodulus.Inthispaperwepresentanexplicitalgo-rithmrefutingtheconjecture.ConcretelywecanfactorizeanRSAmodulusnusingverylittleinformationonthefactorizationofaconcrete

3、n′coprimeton.However,webelievetheconjecturemightbetrue,whenimposingsomeextraconditionsontheauxiliaryn′allowedtobeused.Inparticular,thepapershowshowsubtlethenotionofmalleabilityis.Keywords:Cryptography,RSA,Malleability,primitiveroots1IntroductionTheexistenceo

4、fatradeoffbetweenone-waynessandchosenciphertextsecuritydatesarXiv:0801.0030v1[math.NT]29Dec2007backtotheeightieswhen,forexample,itwasobservedin[10,11,4].Insomesense,onecannotachieveone-wayencryptionwithalevelofsecurityequivalenttosolvecertaindifficultproblem,at

5、thesametimeasthecryptosystembeingIND-CCAse-curerespecttoit.Thissocalledparadoxhasbeenattemptedtobeformallyprovedmanytimes,byanumberofauthors,sincefirstobserved.Howevernoonesucceededuntilveryrecently,whenPaillerandVillar(cf.[9])clarifiedthequestionforthecaseoff

6、actoring-basedcryptosystems.Inparticular,theygivepreciseconditionsforcertainsecurityincompatibilitiestoexist.Moreprecisely,theyreformulatetheparadoxintermsofkeypreservingblack-boxreductionsandprovethatiffactoringcanbereducedinthestandardmodeltobreakingone-wa

7、ynessofthecryptosystemthenitisimpossibletoachievechosen-cyphertextsecurity.Astheauthorsmentionintheirpaper(cf.[9]),combiningthisresultwiththesecurityproofscontainedin[2,3]givesaveryinterestingseparationresultbetweentheRandomOraclemodel1andthestandardmodel.Mo

8、reover,assuminganextrahypothesis,whichtheycall“non-malleability”ofthekeygenerator,theyareabletoextendtheresultfromkeypreservingblackboxreductionstothecaseofarbitraryblackboxreductions.Hence,asth