一种Montgomery模乘的硬件算法及其实现

:2001208224;:2001210230:100423365(2002)0420276203Montgomery,(,100084):Montgomery,Montgomery,,CSMC016LmCMOS512Montgomery48000,3mm3mm,40MHz,512Montgomery341:;Montgomery;:TN43112;TN492:AAHardwareAlgorithmforMontgomery’sModularMultiplicationandItsImplementationFANGYing2li,GAOZhi2qiang(InstituteofMicroelectronics,TsinghuaUniversity,Beijing100084,P1R1China)Abstract:Ahigh2radixtechniqueisemployedtoimprovetheoriginalMontgomery’salgorithm,andanefficienthardware2orientedalgorithmisproposedtocalculateMontgomeryProduct,whichhasareducedhardwarecom2plexityandincreasedprocessingspeed1Thealgorithmhasbeenimplementedina5122bitMontgomerymodularmultiplierusingCSMC016LmCMOSstandardcelllibrary1Thedevicecontainsabout48kgatesandoccupiesanareaof3mm3mm1Operatingatamaximumclockfrequencyupto40MHz,ittakes341clockcyclesforthemodularmultipliertoaccomplisha5122bitMontgomerymodularmultiplication1Keywords:Modularmultiplier;Montgomery’salgorithm;ASICEEACC:1265B1RSA[1],ö::C=ME(modN):M=CD(modN),M,C,MCNEDMCNEDRSAMCN512,RSAö,,P.L.Mont2gomery1985,:N1,R,RN,(R,N)=1R-1N:0R-1N,RR-1(modN)=1;0NR,NN(modR)=-1AB,Mont2gomery11MontPro(A,B,N){T=AB;M=(TmodR)N(modR);S=(T+MN)öR;32420028MicroelectronicsVol132,4Aug12002ifSNthenS=S-N;returnS;}Montgomery,AB(modN),R-1,ABR-1(modN)([2])MontgomeryMontgomeryAB(modN)Montgomery,:AB(modN)=MontPro(MontPro,(A,B,N),R2,N),MontgomeryRSA2Montgomery1,Montgomery,r,,r2k,krw,(A=(aw-1aw-2a1a0)r,B=(bw-1bw-2b1b0)r,N=(nw-1nw-2n1n0)rn’0r1,n0n’0-1(modr),Montgomery22MontPro(A,B,N){T=AB;S0=0;fori=0tow-1do{mi=(Si+ti)n0(modr);Si+1=(Si+ti+miN)ör;}Sw+1=Sw+TH;ifSw+1NthenSw+1=Sw+1-N;returnSw+1;}2,1,12,Montgomery:1)1,;2),,;3),,3Montgomery3MontPro(A,B,N){S=0;T=0;(1)fori=0tow-1do(2){(c1,s1)=t1+a0bi;(3)t0=s1;(4)m=(s0+t0)n0(modr);(5)(c2,s2)=s0+mn0+t0;(6)forj=1tow-1do(7){(c1,s1)=tj+1+ajbi+c1;(8)tj=s1;(9)(c2,s2)=sj+mnj+c2;(10)sj-1=s2;(11)}(12)tw=c1;(13)sw-1=c2;(14)}(15)c1=1;(16)(c2,s2)=s0+t1;(17)s0=s2;(18)forj=1tow-1do(19){(c2,s2)=sj+tj+1+c2;(20)sj=s2;(21)(c1,s1)=sj-1+not(nj-1)+c1;(22)tj+1=s1;(23)}(24)(c1,s1)=sw-1+not(nw-1)+c1;(25)tw=s1;(26)if(c2Ýc1=1)thenoutput(twtw-1t2t1)r;(27)elseoutput(sw-1sw-2s1s0)r;(28)}(29),A,B,N,Srw,Tr(w+1)s1s2,c1c23,((8)(9))((10)(11)),3(15),ST2SwTH2Sw+1=Sw+THifSw+1N,thenSw+1=Sw+1-N3:,,T1S,S,c2((20)(21));,4:Montgomery277S1N,T1,c1((27)(28)),(26),ST2Sw+1Sw+1-N,ST((27)(28))(c2Ýc1=1),T(2Sw+1-N)((27));S(2Sw+1)((28))3Montgomery311Montgomery:,MontgomeryMont2gomery;MontgomeryMontgomeryMontgomery,11Montgomery312Montgomery:,MontgomeryMont2gomery1),3,,;,,222)MontgomeryMontgomery();2,;kkk+k+2k(k),3(8)(10),(20)(22),333)MontgomeryMontgomeryMontgomery,Montgomery,,;,,,,;,,,;,,,313,CSMC016LmCMOS512Mont2gomery,32Montgomery,Mont2gomery,32+32+64,3232Booth(282)278:Montgomery2002[3].IC[J].,1997;26(1):12111[4],,.[J].,2000;(4):10221061[5].[J].,2000;(12):92131[6].IC[EBöOL].http:[7]TaiHJ,WangJB,ChouHL.Synthesisandproper2tiesofalowhydrothermalstressepoxymoldingcom2poundforelectronicencapsulation[J].PolymerCom2posites,2000;21(6):95329591[8]KimW,BaeJW,ChoiID,etal.Thermallyconduc2tiveEMC(EpoxyMoldingCompound)formicroelec2tronicencapsulation[J].PolymerEngineeringandScience,1999;39(4):75627661[9]PeekR.Liquidencapsulationprotectselectroniccom2ponentsacomplexdispensingprocessrequirespre2cisecontrolofmanyvariables[J].ElectronicPackag2ingandProduction,2001;41(6):542621[10]OkunoA,FujitaN,NagaiK,etal.Propertiesandreli2abilityofliquidepoxyresinforLSIfabricationwiththeprintingencapsulationsystem(PES)[J].Elec2tronics&CommunicationsinJapan,Part2,Electron2ics,1997;80(2):672761[11]MuraiH,TakedaY,TakanoN,etal.Newhalogen2freematerialsforPWB,HDIandadvancedpackagesubstrate[J].CircuitWorld,Part2,2001;27:72111[12]YagisawaT,SuzukiH.Developmentoftheenviron2mentallyfriendlyepoxymoldingcompound[A].Proc50thElectronicsComponentsandTechnologyConf[C].2000,1737217421[13]KiuchiY,IjiM.Developmentofenvironmentallyfriendlyandflame2retardingepoxyresincompoundswithouthalogenandphosphorusderivativesandtheirapplicationtointegratedcircuitpackagesandprintedwiringboards[J].NECTechnicalJournal,2001;54(2):842891[14]LeeHY,YuJ1AdhesionstrengthofleadframesöEMCinterfaces[J].JElectronicMaterials,1999;28(12):1444214471[15]KimJK,LebbaiM,LiuJH,etal.Interfaceadhesionbetweencopperleadframeandepoxymoldingcom2poundeffectsofsurfacefinish,oxidationanddimples[A].Proc50thElectronicsComponentsandTechnol2ogyConf[C].2000,60126081:(1938),(),,,,863,5,90(278)Wallace,25ns,Montgomery40MHz3,Montgomery(w2+5w+5),,w32,512Montgomery,w=512ö32=16,Mont2gomery34148000,3mm3mmMontgomeryMontgomery,4MontgomeryVLSIMontgomery48000,3mm3mm,341,Montgomery:[1]RivestR,ShamirA,AdlemanL1Amethodforob2tainingdigitalsignaturesandpublic2keycryptosys2tems[J]1CommunicationsoftheACM,1978;21(1):12021261[2]MontgomeryPL1Modularmultiplicationwithouttri2aldivision[J]1MathComputation,1985;44(4):51925211:(1975),(),,1999,,,RSAASICIP282:2002