Fast scalable radix-4 Montgomery modular multiplier

Sheng Hong Wang; Wen Ching Lin; Jheng Hao Ye; Ming-Der Shieh

doi:10.1109/ISCAS.2012.6271962

Fast scalable radix-4 Montgomery modular multiplier

Sheng Hong Wang, Wen Ching Lin, Jheng Hao Ye, Ming-Der Shieh

Department of Electrical Engineering

Research output: Contribution to conference › Paper › peer-review

23 Citations (Scopus)

Abstract

Montgomery modular multiplication is widely applied to public key cryptosystems like Rivest-Sharmir-Adleman (RSA) and elliptic curve cryptography (ECC). This work presents a word-based Booth encoded radix-4 Montgomery modular multiplication algorithm for low-latency scalable architecture. The data dependency resulting from the inherent right shifting of the intermediate results in the conventional radix-4 Montgomery modular multiplication algorithm is alleviated; thus the latency between the neighboring process elements (PEs) is exactly one cycle. The number of the equivalent operands in the accumulation is not increased with operand reduction scheme. Implementation results based on the same technology show that compared to other Booth encoded radix-4 Montgomery modular multipliers, the proposed design achieves at least 23% time reduction for accomplishing one 1024-bit Montgomery modular multiplication.

Original language	English
Pages	3049-3052
Number of pages	4
DOIs	https://doi.org/10.1109/ISCAS.2012.6271962
Publication status	Published - 2012 Sep 28
Event	2012 IEEE International Symposium on Circuits and Systems, ISCAS 2012 - Seoul, Korea, Republic of Duration: 2012 May 20 → 2012 May 23

Other

Other	2012 IEEE International Symposium on Circuits and Systems, ISCAS 2012
Country	Korea, Republic of
City	Seoul
Period	12-05-20 → 12-05-23

All Science Journal Classification (ASJC) codes

Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/ISCAS.2012.6271962

Fingerprint Dive into the research topics of 'Fast scalable radix-4 Montgomery modular multiplier'. Together they form a unique fingerprint.

Cite this

@conference{5d21c60a58164095b5ca9dcb7f056daa,

title = "Fast scalable radix-4 Montgomery modular multiplier",

abstract = "Montgomery modular multiplication is widely applied to public key cryptosystems like Rivest-Sharmir-Adleman (RSA) and elliptic curve cryptography (ECC). This work presents a word-based Booth encoded radix-4 Montgomery modular multiplication algorithm for low-latency scalable architecture. The data dependency resulting from the inherent right shifting of the intermediate results in the conventional radix-4 Montgomery modular multiplication algorithm is alleviated; thus the latency between the neighboring process elements (PEs) is exactly one cycle. The number of the equivalent operands in the accumulation is not increased with operand reduction scheme. Implementation results based on the same technology show that compared to other Booth encoded radix-4 Montgomery modular multipliers, the proposed design achieves at least 23% time reduction for accomplishing one 1024-bit Montgomery modular multiplication.",

author = "Wang, {Sheng Hong} and Lin, {Wen Ching} and Ye, {Jheng Hao} and Ming-Der Shieh",

year = "2012",

month = sep,

day = "28",

doi = "10.1109/ISCAS.2012.6271962",

language = "English",

pages = "3049--3052",

note = "2012 IEEE International Symposium on Circuits and Systems, ISCAS 2012 ; Conference date: 20-05-2012 Through 23-05-2012",

}

TY - CONF

T1 - Fast scalable radix-4 Montgomery modular multiplier

AU - Wang, Sheng Hong

AU - Lin, Wen Ching

AU - Ye, Jheng Hao

AU - Shieh, Ming-Der

PY - 2012/9/28

Y1 - 2012/9/28

N2 - Montgomery modular multiplication is widely applied to public key cryptosystems like Rivest-Sharmir-Adleman (RSA) and elliptic curve cryptography (ECC). This work presents a word-based Booth encoded radix-4 Montgomery modular multiplication algorithm for low-latency scalable architecture. The data dependency resulting from the inherent right shifting of the intermediate results in the conventional radix-4 Montgomery modular multiplication algorithm is alleviated; thus the latency between the neighboring process elements (PEs) is exactly one cycle. The number of the equivalent operands in the accumulation is not increased with operand reduction scheme. Implementation results based on the same technology show that compared to other Booth encoded radix-4 Montgomery modular multipliers, the proposed design achieves at least 23% time reduction for accomplishing one 1024-bit Montgomery modular multiplication.

AB - Montgomery modular multiplication is widely applied to public key cryptosystems like Rivest-Sharmir-Adleman (RSA) and elliptic curve cryptography (ECC). This work presents a word-based Booth encoded radix-4 Montgomery modular multiplication algorithm for low-latency scalable architecture. The data dependency resulting from the inherent right shifting of the intermediate results in the conventional radix-4 Montgomery modular multiplication algorithm is alleviated; thus the latency between the neighboring process elements (PEs) is exactly one cycle. The number of the equivalent operands in the accumulation is not increased with operand reduction scheme. Implementation results based on the same technology show that compared to other Booth encoded radix-4 Montgomery modular multipliers, the proposed design achieves at least 23% time reduction for accomplishing one 1024-bit Montgomery modular multiplication.

UR - http://www.scopus.com/inward/record.url?scp=84866617748&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866617748&partnerID=8YFLogxK

U2 - 10.1109/ISCAS.2012.6271962

DO - 10.1109/ISCAS.2012.6271962

M3 - Paper

AN - SCOPUS:84866617748

SP - 3049

EP - 3052

T2 - 2012 IEEE International Symposium on Circuits and Systems, ISCAS 2012

Y2 - 20 May 2012 through 23 May 2012

ER -