An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors

doi:10.7652/xjtuxb201702008

您当前的位置：

首页 >

文章列表页 >

An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors

更新时间：2025-07-09

- An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors
- Vol. 51, Issue 2, Pages: 47-52+127(2017)
- 作者机构：
  
  1. 中国科学院声学研究所国家网络新媒体工程技术研究中心,北京,100190
  2. 中国科学院大学电子电气与通信工程学院,北京,100049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201702008
  CLC： TP309.7
- Online First：10 February 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
An Optimized Montgomery Modular Multiplication Algorithm for Embedded Processors[J]. 2017, 51(2): 47-52+127.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

I/O Performance Modeling and Prediction Method for Large-Scale Parallel Applications Using Machine Learning

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Review of the Application of EBSILON Software in Combined Heat and Power System Optimization

Related Author

No data

Related Institution

No data

⁰