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

李杨 1; 2; 王劲林 1; 叶晓舟 1; 曾学文 1

doi:10.7652/xjtuxb201702008

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 面向嵌入式处理器的优化Montgomery模乘算法
- An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors
- 西安交通大学学报 2017年51卷第2期页码：47-52+127
- 作者机构：
  
  1. 中国科学院声学研究所国家网络新媒体工程技术研究中心,北京,100190
  2. 中国科学院大学电子电气与通信工程学院,北京,100049
- 作者简介：
- 基金信息：
  
  : 2016-06-20。作者简介: 李杨(1990—),女,博士生;叶晓舟(通信作者),男,研究员。基金项目: 中国科学院战略性先导科技专项课题资助项目(XDA06010302);中国科学院声学研究所知识创新工程资助项目(Y154191601)
- DOI：10.7652/xjtuxb201702008
  中图分类号： TP309.7
- 网络首发：2017-02-10，
  
  纸质出版：2017
- 稿件说明：
移动端阅览
李杨 1, 2, 王劲林 1, 等. 面向嵌入式处理器的优化Montgomery模乘算法[J]. 西安交通大学学报, 2017,51(2):47-52+127.

An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors[J]. 2017, 51(2): 47-52+127.
李杨 1, 2, 王劲林 1, 等. 面向嵌入式处理器的优化Montgomery模乘算法[J]. 西安交通大学学报, 2017,51(2):47-52+127. DOI： 10.7652/xjtuxb201702008.

An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors[J]. 2017, 51(2): 47-52+127. DOI： 10.7652/xjtuxb201702008.

摘要

针对嵌入式系统中频繁的内存存取影响Montgomery模乘算法效率的问题

提出了一种优化的分离连续操作数缓存算法。该算法基于连续操作数缓存算法并进行优化

应用于计算多精度乘法和约减两部分

将整个计算分块使得每块内操作数只被加载一次; 为了不破坏操作数加载的连续性

在多精度乘法和约减之间采用分离集成的方式; 通过动态地使用寄存器和有效的缓存操作数来减少嵌入式系统中算法使用内存存取操作的总量

实现提高模乘算法效率的目的。实验结果表明:在使用MIPS64架构的处理器上

当模数为1 024 bit时

与应用广泛的粗粒度集成操作数扫描算法相比

该算法的效率提高了4.17%。在嵌入式系统中

可将该算法应用于公钥密码体系中的模乘运算

在提高模乘效率的同时提高公钥密码算法的运算效率。

Abstract

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.

关键词

Keywords

references

RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems [J]. Communications of the ACM, 1983, 26(2): 96-99.

HANKERSON D, VANSTONE S, MENEZES A. Guide to elliptic curve cryptography [M]. Berlin, Germany: Springer-Verlag, 2004: 1-21.

MONTGOMERY P L. Modular multiplication without trial division [J]. Mathematics of Computation, 1985, 44(170): 519-521.

KOC C K, ACAR T, KALISKI B S. Analyzing and comparing Montgomery multiplication algorithms [J]. IEEE Micro, 1996, 16(3): 26-33.

CHU D, GROBSCHADL J, LIU Zhe, et al. Twisted Edwards-form elliptic curve cryptography for 8-bit AVR-based sensor nodes [C]∥Proceedings of the ACM Workshop on Asia Public-Key Cryptography. New York, USA: ACM, 2013: 39-44.

GROBSCHADL J, HUDLER M, KOSCHUCH M, et al. Smart elliptic curve cryptography for smart dust [M]∥ Quality, Reliability, Security and Robustness in Heterogeneous Networks. Berlin, Germany: Springer-Verlag, 2012: 623-634.

LIU Zhe, GROBSCHADL J, WONG D S. Low-weight primes for lightweight elliptic curve cryptography on 8-bit AVR processors [M]∥ Information Security and Cryptology. Berlin, Germany: Springer International Publishing, 2013: 217-235.

LIU Zhe, WENGER E, GROBSCHADL J. Mote-ECC: energy-scalable elliptic curve cryptography for wireless sensor networks [M]∥ Applied Cryptography and Network Security. Berlin, Germany: Springer International Publishing, 2014: 361-379.

ZHANG Yang, GROBSCHADL J. Efficient prime-field arithmetic for elliptic curve cryptography on wireless sensor nodes [C]∥Proceedings of the 11th International Conference on Computer Science and Network Technology. Piscataway, NJ, USA: IEEE, 2011: 459-466.

SEO H, LIU Zhe, NOGAMI Y, et al. Montgomery multiplication and squaring for optimal prime fields [J]. Computers and Security, 2015, 52: 276-291.

SEO H, KIM H. Multi-precision multiplication for public-key cryptography on embedded microprocessors [M]∥ Information Security Applications. Berlin, Germany: Springer-Verlag, 2012: 55-67.

DUSSE S R, KALISKI B S. A cryptographic library for the Motorola DSP56000 [C]∥Proceedings of the ACM. Berlin, Germany: Springer-Verlag, 1990: 230-244.

MENEZES A J, VANSTONE S A, OORSCHOT P C V. Handbook of applied cryptography [M]. Boca Raton, FL, USA: CRC Press, 1996: 67-80.

COMBA P G. Exponentiation cryptosystems on the IBM PC [J]. IBM Systems Journal, 1990, 29(4): 526-538.

MIPS Technologies, Inc. MIPS64 architecture for programmers: Volume II The MIPS64 instruction set revision 3.0: MD00087 [EB/OL].(2010-03-25)[2016-06-01]. http:∥www.doc88.com/p-49790009 4247.html.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

EBSILON软件在热电联产系统优化中的应用综述

超临界二氧化碳向心透平轮背间隙内风阻损失及流动特性研究

采用机器学习的大规模并行程序I/O性能建模与预测方法

不同板叠材料热声热机能量转换过程数值模拟研究

电子级超纯氮深冷空分流程节能优化研究