基于Frobenius映射的快速标量乘算法

《基于Frobenius映射的快速标量乘算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据计算机研究与发展ISSN1000—12391CN1l一1777／TPJournalofComputerResearchandDevelopment45(9)：1561～1566。2008基于Frobenius映射的快速标量乘算法殷新春h2侯红祥1谢立21(扬州大学信息工程学院江苏扬州225009)2(南京大学计算机软件新技术国家重点实验室南京210093)(xeyin@yzu．edu．cn)FastScalarMultiplicationAlgorithmBasedonFrobeniusMappin

2、gYinXinchunl～，HouHongxian91，andXieLi21(SchoolofInformationandEngineering，YangzhouUniversity，Yangzhou，Jiangsu225009)1(StateKeyLaboratoryforNovelSoftwareTechnology，NanjingUniversity，Nanjing210093)AbstractEllipticcurvecryptosystem(ECC)isanovelpublickeycryptos

3、ystem，whichwillbetheprimarystandardforapplicationinthefuture．ThecapabilityofECCdependsontheefficiencyofscalarmultiplication．Furthermore，fastscalarmultiplicationalgorithmonKoblitzcurveisthetopdemandingtaskintheresearchofscalarmultiplication．Afterthereductio

4、nofTNAF(k)，asuperoperationalgorithmbasedonFrobeniusmappingisproposed，whichisCombalgorithm．Atpre-computestage，inordertoestablishapre-computetable，thealgorithmcalculatesthecoordinateofsomepointsonellipticcurvecorrespondingtoanysequenceatafixedlengthof，．witht

5、hehelpofFrobeniusmapping．Ontheotherhand，atevaluationstage，thealgorithmemploysthereductionofTNAF(k)aswellasthepre—computetabletoimprovetheefficiencyofthewholeCombalgorithm．BecauseofhighperformanceofFrobeniusmapping，Combalgorithmdoesn’trelatetopointdoubling．

6、AndafterarrangingofCombmatrix，thequantityofpointadditionneededbythealgorithminthispaperis1／5～1／4timesofthatneededbytraditionalalgorithms．Inaddition，theefficiencyofthealgorithmisfasteratleastabout67％thanthetraditionalCombalgorithmwitharbitrarylengthofrowina

7、nycoordinate．Keywordsellipticcurvecryptosystem(ECC)；scalarmultiplication；Koblitzcurve；Frobeniusmapping；Combalgorithm摘要标量乘法的效率决定着椭圆曲线密码体制的性能，而Koblitz曲线上的快速标量乘算法是标量乘法研究的重要课题，在标量k的TNAF约简基础上，给出了一种基于Frobenius映射的上层运算：Comb算法．在预计算阶段，该算法利用Frobenius映射对宽度为r的序列计算其对应椭圆

8、曲线上的点，从而建立预计算表，在累加赋值阶段结合约简后的TNAF(k)和预计算表来提高效率．Comb算法基于高效的FrobeniUS映射无须进行倍点运算，经过Comb矩阵的组合，其所需点加量是传统算法的115～1／4，"-3行数，．任意时，其效率在任意坐标下比传统Comb算法提高至少67％．关键词椭圆曲线密码体制；标量乘法；Koblitz曲线；Frobenius映射；Comb算法中图法分类号TP301．6收稿日期