面向嵌入式处理器的优化Montgomery模乘算法  

An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors

作　　者：李杨[1,2] 王劲林[1] 叶晓舟[1] 曾学文[1] 

机构地区：[1]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190 [2]中国科学院大学电子电气与通信工程学院,北京100049

出　　处：《西安交通大学学报》2017年第2期47-52,127,共7页Journal of Xi'an Jiaotong University

基　　金：中国科学院战略性先导科技专项课题资助项目(XDA06010302);中国科学院声学研究所知识创新工程资助项目(Y154191601)

摘　　要：针对嵌入式系统中频繁的内存存取影响Montgomery模乘算法效率的问题,提出了一种优化的分离连续操作数缓存算法。该算法基于连续操作数缓存算法并进行优化,应用于计算多精度乘法和约减两部分,将整个计算分块使得每块内操作数只被加载一次;为了不破坏操作数加载的连续性,在多精度乘法和约减之间采用分离集成的方式;通过动态地使用寄存器和有效的缓存操作数来减少嵌入式系统中算法使用内存存取操作的总量,实现提高模乘算法效率的目的。实验结果表明:在使用MIPS64架构的处理器上,当模数为1 024bit时,与应用广泛的粗粒度集成操作数扫描算法相比,该算法的效率提高了4.17%。在嵌入式系统中,可将该算法应用于公钥密码体系中的模乘运算,在提高模乘效率的同时提高公钥密码算法的运算效率。An improved separated consecutive operand caching algorithm is proposed to focus on the problem that frequent memory-access operations affect the efficiency of Montgomery modular multiplication on embedded processors. The algorithm carefully applies the general idea of consecutive operand caching and optimization to two calculation parts- multiplication and reduction. It separates the whole calculation into many blocks and loads operand in each block only once. The separately integrated mode is used between multiplication and reduction to keep the consecutiveness of operands. The number of memory-access operations on embedded processor is significantly reduced by dynamically using registers and efficient caching of operands. Experiments on processor with MIPS64 structure show that when the modulus is 1 024 bits, the proposed algorithm outperforms the coarsely integrated operand scanning algorithm by a factor of 4.17%. The proposed algorithm can be used for public-key cryptography to improve the efficiency of both the modular multiplication and the public-key algorithms.

关 键 词：MONTGOMERY模乘 嵌入式系统 连续操作数缓存算法 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]