FPGA IMPLEMENTATION OF RSA PUBLIC_KEY CR

Vol.23No.5JOURNALOFELECTRONICS(CHINA)September2006FPGAIMPLEMENTATIONOFRSAPUBLIC-KEYCRYPTOGRAPHICCOPROCESSORBASEDONSYSTOLICLINEARARRAYARCHITECTUREWenNuanDaiZibinZhangYongfu(InstituteofElectronicTechnology,ThePLAInformationEngineeringUniversity,Zhengzhou450004,China)AbstractInordertomakethetypicalMontgomery’salgorithmsuitableforimplementationonFPGA,amodifiedversionisproposedandthenahigh-performancesystoliclineararrayarchitectureisdesignedforRSAcryptosystemonthebasisoftheoptimizedalgorithm.Theproposedsystolicarrayarchitecturehasdis-tinctivefeatures,i.e.notonlythecomputationspeedissignificantlyfastbutalsothehardwareoverheadisdrasticallydecreased.Asamajorpracticalresult,thepapershowsthatitispossibletoimplementpublic-keycryptosystematsecurebitlengthsonasinglecommerciallyavailableFPGA.KeywordsRSA;Montgomery’salgorithm;Systoliclineararray;Modularmultiplication;Modularexpo-nentiationI.IntroductionModularexponentiationsoflargeintegersarethebasicoperationsforwell-knowncryptographicalgorithmsinpublic-keycryptosystemssuchastheRSAcryptosystem.Insuchamodularexponentia-tion,modularmultiplicationwithnumerousmodulus(e.g.1024bit)isperformedasitselementaryopera-tion.Becauseofitslowefficiency,itbecomesabot-tleneckofthecomputationspeed.Therearemanyalgorithmsformodularmultiplicationoperation,oneofthemostattractivemethodsisMontgomery’sal-gorithm[1].DuetotheextremelylongoperandsofRSAcryptography,systolicstructureswiththepurelynearestneighbourcommunicationwillbeadvantageousifveryhighclockfrequencyisneededtoachievehighspeed.BasedonMontgomery’sal-gorithmasystolicplanararraywasproposedbyC.D.Walter.Justlikeothersystolicarraystructuresformodularmultiplicationproposedbefore,thelargesystolicarrayslimittheirapplicationswhereshortlatencyandsmallareaareneeded.Here,asystoliclineararraystructureformodularmultipli-cationisdevelopedinthispaper,whichhasdistinc-tivefeaturesthatnotonlythecomputationspeedissignificantlyfastbutalsothehardwareoverheadisdrasticallydecreased.Furthermore,theinternalmodularizationofthepresenteddesignprovidesaneasywaytotestnewarchitecturesfortheimple-mentationoftheRSAalgorithminordertoimproveperformance.TheprototypeisfabricatedinAlteraCycloneseriesFPGA.With130MHzclockfre-quency,thethroughputcanreach61.5kbit/s.1Manuscriptreceiveddate:November26,2004;reviseddate:May8,2005.Communicationauthor:WenNuan,bornin1980,male,Master.InstituteofElectronicTechnology,ThePLAInformationEngineeringUniversity,Zhengzhou450004,[e-mail]-keycryptographywasinventedbyRivest,Sharmir,andAdlemanin1978[2].Thealgo-rithm’ssecurityisbasedonthediscretealgorithminfinitefields,i.e.itiseasytocomputetheproductoftwolargeprimenumbers,anditishardtoanalyzetheprimefactoronthecontrary.RSAalgorithmcanbesimplydescribedasfollows,wheremistheplaintext,andcisthecipher:(1)Choosetwolargeprimenumberspandq;(2)ComputethemodulusM=pqandP(M)=(p1)(q1);(3)Choosee,0eM,suchthat(e,P(M))=1,defineeasPK(PublicKey)orSK(SecretKey);(4)Computed,theinverseofeinZ*P(M),ed≡1modP(M),definedasSKorPK;(5)Encryption:computec=mPKmodM,0mM1;(6)Decryption:computem=cSKmodMThemodulusnandthepublicexponentearepublished;thevalueofdandtheprimenumberspandqarekeptsecret.III.Montgomery’sAlgorithmandtheOptimization1.Montgomery’salgorithmThecorearithmeticofRSAismodularexponen-tiation,whichcanbeperformedbyaseriesofmodularmultiplications.Therefore,forhighspeedRSAcryptosystem,itisimportanttoefficientlycal-culatemodularmultiplication,whichisgenerallyconsideredasacomplicatedarithmeticoperationbecauseofinherentmultiplicationanddivisionop-erations.Theclassicalmethodtocomputemodularmultiplicationisbyperformingthemultiplicationandthensubtractingthemodulusseveraltimesuntiltheresultislessthanthemodulus.ThisapproachisinefficientandsuffersfromlowspeedandmassWENetal.FPGAImplementationofRSAPublic-keyCryptographicCoprocessorBasedonSystolicLinearArrayArchitecture719hardwareresource.Montgomery’salgorithm,ontheotherhand,reversestheorderoftreatingthedigitsofthemultiplicand,usingtheleastsignificantbitsoftheintermediateresulttoperformanadditionratherthanasubtraction,andperformsashiftdownopera-tioninsteadofashiftupoperationoneachiteration.Ithasbeendesignedtomeetthepredominantre-quirementsofmostmoderndevices:smallchipareaandlowpowerconsumption.Thismethodisrepre-sentedasafunctionMRED(T):Algorithm1MRED(T)computesaMontgomeryreductionofT10,2,2,gcd(,)1mmiiiTRMRMmMR−====∑(1)BEGIN(2)q=(TmodR)M'modR(3)U=(T+qM)/R(4)IFU≥MTHENU=UM(5)RETURNU(6)ENDIfwechoosetherightR,apowerof2inwhichwerepresentmultiple-precisionintegers,thendivideitbyRandreductionmodulusRaretrivial.WithsuchanR,Montgomeryreductionisnomoreex-pensivethantwomultiple-precisionproducts.TheMREDfunctioncomputesaMontgomeryproductoftheform:MRED(A,B,M)=(ABR−1)modM.Un-fortunately,theextrafactorofR−1ispickedupinthecalculation,somepreviousandpostcalculationsarerequiredtoproducethecorrectresult,andwewilldiscusshowtouseMREDfunctiontocomputeZ=(AB)modMlater.2.AlgorithmoptimizationWenowconsiderahardwareimplementationofAlgorithm1.TocomputeStep(2)weneedanm×mb