An Improvement in the VLSI Implementation of Montgomery Algorithm

Abstract

Abstract: Modular exponentiation of large operands is the kernel operation in many public-key cryptosystems, RSA algorithm for instance. Montgomery algorithm is often used as a solution. In the VLSI implementation of Montgomery algorithm, the speed is the top target. An improvement is proposed with little or even no increase in the hardware area but apparently saving much time.

Key words: Montgomery, RSA, VLSI Implementation

摘要： 速度与面积是数字集成电路设计的两个重要目标，由于它们之间通常是一种相互制约的关系，所以往往要在一定程度上进行折中。作者提出的改进方法可以在几乎不增加硬件面积的条件下有效地提高速度。

关键词: Montgomery, RSA, VLSI硬件实现

CLC Number:

ZHANG Yihao,TIAN Ze,YU Dunshan,SHENG Shimin. An Improvement in the VLSI Implementation of Montgomery Algorithm[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

张怡浩,田则,于敦山,盛世敏. 一种Montgomery模乘算法硬件实现的改进电路[J]. 北京大学学报（自然科学版）.

[1]	ZHOU Rong, WU Chaodong, ZHANG Yanan. Outpainting Reconstruction of Sandstone Thin-Section Image Based on Generative Adversarial Network [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(2): 231-241.
[2]	GAO Xiaoqian, ZHOU Xiabing, ZHANG Min. A Multi-information Perception Based Method for Question Answering in Multi-party Conversation [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(1): 21-29.
[3]	YANG Erguang, LIU Mingtong, ZHANG Yujie, MENG Yao, HU Changjian, XU Jin’an, CHEN Yufeng. Unsupervised Syntactically Controllable Paraphrase Network for Adversarial Example Generation [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021, 57(1): 83-90.
[4]	YANG Shuangtao, FU Bo, YU Chenchen, HU Changjian. Multi-Turn Conversation Rewriter Model Based on Masked-Pointer [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2021, 57(1): 31-37.
[5]	ZHANG Qinglin, DU Jiachen, XU Ruifeng. Sarcasm Detection Based on Adversarial Learning [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2019, 55(1): 29-36.
[6]	ZHANG Qihui, CAO Jian, CAO Xixin, YU Dunshan, ZHANG Xing. Design and Implementation of an Asynchronous Low Power RSA Circuit Structure [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2018, 54(6): 1351-1354.
[7]	MA Nan,ZHAO Chunsheng,DENG Zhaoze,TAO Jiangchuan,YU Renjie,CHEN Jing,BIAN Yuxuan. A Modified Method for Calibrating the Supersaturations in DMT Cloud Condensation Nuclei Counter [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2014, 50(5): 805-811.
[8]	WANG Teng,WANG Xin’an,XIE Zheng,HU Ziyi. Low-Cost VLSI Implementation of Motion Estimation for H.264/AVC Encoders [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2014, 50(4): 768-780.
[9]	WANG Tian,CUI Xiaoxin,LIAO Kai,LIAO Nan,HUANG Ying,ZHANG Xiao,YU Dunshan. Montgomery Multiplier Based on Secondary Booth Encoding in RSA Encryption [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2014, 50(4): 642-646.
[10]	GAO Jiangbo,ZHOU Qiaofu,CHANG Qing,LI Shuangcheng. Evaluating the Ecological Service Function of Soil Conservation Based on RUSLE and GIS [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2009, 45(1): 151-157.
[11]	YANG Zhixin,XIE Weishi. Study of Directed Forgetting by Using Messages Related Item as Cues [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2007, 43(6): 858-862.
[12]	WEN Lan,GAN Shaobo. Obstruction Sets, Quasi-Hyperbolicity and Linear Transversality [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2006, 42(1): 1-10.
[13]	LIU Qiang,MA Fangzhen,TONG Dong,CHENG Xu. Design Features of a High Throughput RSA Cryptoprocessor [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2005, 41(5): 754-763.
[14]	LIU Qiang,MA Fangzhen,TONG Dong,CHENG Xu. RSA Cryptoprocessor Based on a Redesigned Systolic Array [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2005, 41(3): 495-500.
[15]	SONG Yong,LIU Hong. A New Automatic Seal Image Retrieval Method Based on Curves Matching [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2004, 40(1): 85-90.

An Improvement in the VLSI Implementation of Montgomery Algorithm

一种Montgomery模乘算法硬件实现的改进电路

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics