改进的Batch RSA算法的设计与实现.pdf

ComputerEngineering口 4 ffc口ff。 计算机工程与应用 改进的BatchRSA算法的设计与实现 李云飞 ，柳 青 ，郝 林 ，刘庆龙 LIYunfei～，LIU Qing2，HAO Lin3，LIU Qinglong 1．云南空管分局 技术保障部，昆明 650200 2．云南大学 软件学院，昆明 650091 3．云南大学 信息学院，昆明 650091 1．TechnicalSuppo~ Department，Yunnan AirTrafficM anagementSub-Bureau-CAAC，Kunming 650200，China 2．SchoolofSotb,vrae，Yunnan University，Kunming 650091，China 3．SchoolofInformation ScienceandEngineering，YunnanUniversiyt，Kunming 650091，China LIYun~i．LIU Qing，HAO Lin，eta1．Designand implementationofimprovedBatchRSA algorithm．ComputerEngineer- ingandApplications，2011。47(29)：107-109． Abstract：Theperfomr anceofBatch RSA decryption hasdirectrelationshipwith hte efficiency ofhtefullsizedmodularex- ponentiation implementation in hte exponentiation phase．ThispaperproposesavariantofBatch RSA algorithm by transfer- ring some decryption computationsto encryption na d using multi-prime technology to reduce modulesand private exponents in modulra exponentiation．The experimentalresultsna d hte theoreticalvaluesshow htathte speed ofhte decryption hasbeen substantially improved． Key words：Batch RSA ；acceleration；decryption；modularexponentiation 摘 要：BatchRSA算法的解密性能与其指数计算阶段的大数模幂运算的实现效率有着直接的关系。提出了一种BatchRSA算 法的改进方案，通过将BatchRSA算法解密时指数计算阶段的一些运算量转移到加密方，运用多素数技术使大数模幂运算的模 位数和指数位数减小来加速BatchRSA的解密过程。理论分析和实验数据表 明该改进算法使得BatchRSA算法的解密性能得 到明显提升。 关键词：BatchRSA；加速；解密；模幂 DOI：10．3778~．issn．1002．8331．2011．29．029 文章编号：1002．8331(2011)29．0107．03 文献标识码：A 中图分类号：TP309 1 引言 些模乘和模逆运算就可以同时解密v和v，。通过使用批处理 RSA算法是 目前应用最为广泛的公钥密码算法n，但由于 技术，RSA算法的解密性能得到了提升，但文献[3]中提到， RSA算法计算模正整数次幂需要耗费大量的计算时问，降低 BatchRSA在密钥长度相对较小的情况下加速并不明显。本 了RSA算法的执行效率，所以如何加速RSA算法特别是解密 文针对这种情况 ，提出了一种改进的BatchRSA算法 ，它有效 时的速度是密码学界一直研究的问题。Fia(第一次提出了通 结合Multi．PrimeRSA4[均减小模幂运算模Ⅳ和RSA．S1系统 过使用批处理技术来加速RSA的解密过程的BatchRSA[2-3]算 的负载均衡的技术，来加速BatchRSA算法解密时的大数模 法：Fiat发现若使用小公钥指数e，和 e，对两