A new modular exponentiation architecture for efficient design of RSA cryptosystem

Ming-Der Shieh, Jun Hong Chen, Hao Hsuan Wu, Wen Ching Lin

Research output: Contribution to journalArticle

53 Citations (Scopus)

Abstract

Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular multiplication algorithm is used to relax the process of quotient determination, and the carry-save addition (CSA) is employed to reduce the critical path delay. In this paper, based on the inherent data dependency between the modular multiplication and square operations in the H-algorithm of modular exponentiation, we present a new modular exponentiation architecture with a unified modular multiplication/square module and show how to reduce the number of input operands for the CSA tree by mathematical manipulation. The developed architecture has the following advantages. 1) There is no need to convert the carry-save form of an operand into its binary representation at the end of each modular multiplication. In this way, except the final step to get the result of modular exponentiation, the time-consuming carry propagation can then be eliminated. 2) The number of input operands for the CSA tree is reduced in a very efficient way. 3) The hardware saving is achieved with very limited impact on the original critical path delay when designed with two distinct modular multiplication and square components. Experimental results show that our modular exponentiation design obtains the least hardware complexity compared with the existing work and outperforms them in terms of area-time (AT) complexity as well.

Original languageEnglish
Article number4579747
Pages (from-to)1151-1161
Number of pages11
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume16
Issue number9
DOIs
Publication statusPublished - 2008 Sep 1

Fingerprint

Cryptography
Hardware
Communication

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

@article{966d0a5b3ce24c71a64f833eb74e4ccf,
title = "A new modular exponentiation architecture for efficient design of RSA cryptosystem",
abstract = "Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular multiplication algorithm is used to relax the process of quotient determination, and the carry-save addition (CSA) is employed to reduce the critical path delay. In this paper, based on the inherent data dependency between the modular multiplication and square operations in the H-algorithm of modular exponentiation, we present a new modular exponentiation architecture with a unified modular multiplication/square module and show how to reduce the number of input operands for the CSA tree by mathematical manipulation. The developed architecture has the following advantages. 1) There is no need to convert the carry-save form of an operand into its binary representation at the end of each modular multiplication. In this way, except the final step to get the result of modular exponentiation, the time-consuming carry propagation can then be eliminated. 2) The number of input operands for the CSA tree is reduced in a very efficient way. 3) The hardware saving is achieved with very limited impact on the original critical path delay when designed with two distinct modular multiplication and square components. Experimental results show that our modular exponentiation design obtains the least hardware complexity compared with the existing work and outperforms them in terms of area-time (AT) complexity as well.",
author = "Ming-Der Shieh and Chen, {Jun Hong} and Wu, {Hao Hsuan} and Lin, {Wen Ching}",
year = "2008",
month = "9",
day = "1",
doi = "10.1109/TVLSI.2008.2000524",
language = "English",
volume = "16",
pages = "1151--1161",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

A new modular exponentiation architecture for efficient design of RSA cryptosystem. / Shieh, Ming-Der; Chen, Jun Hong; Wu, Hao Hsuan; Lin, Wen Ching.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 16, No. 9, 4579747, 01.09.2008, p. 1151-1161.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A new modular exponentiation architecture for efficient design of RSA cryptosystem

AU - Shieh, Ming-Der

AU - Chen, Jun Hong

AU - Wu, Hao Hsuan

AU - Lin, Wen Ching

PY - 2008/9/1

Y1 - 2008/9/1

N2 - Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular multiplication algorithm is used to relax the process of quotient determination, and the carry-save addition (CSA) is employed to reduce the critical path delay. In this paper, based on the inherent data dependency between the modular multiplication and square operations in the H-algorithm of modular exponentiation, we present a new modular exponentiation architecture with a unified modular multiplication/square module and show how to reduce the number of input operands for the CSA tree by mathematical manipulation. The developed architecture has the following advantages. 1) There is no need to convert the carry-save form of an operand into its binary representation at the end of each modular multiplication. In this way, except the final step to get the result of modular exponentiation, the time-consuming carry propagation can then be eliminated. 2) The number of input operands for the CSA tree is reduced in a very efficient way. 3) The hardware saving is achieved with very limited impact on the original critical path delay when designed with two distinct modular multiplication and square components. Experimental results show that our modular exponentiation design obtains the least hardware complexity compared with the existing work and outperforms them in terms of area-time (AT) complexity as well.

AB - Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular multiplication algorithm is used to relax the process of quotient determination, and the carry-save addition (CSA) is employed to reduce the critical path delay. In this paper, based on the inherent data dependency between the modular multiplication and square operations in the H-algorithm of modular exponentiation, we present a new modular exponentiation architecture with a unified modular multiplication/square module and show how to reduce the number of input operands for the CSA tree by mathematical manipulation. The developed architecture has the following advantages. 1) There is no need to convert the carry-save form of an operand into its binary representation at the end of each modular multiplication. In this way, except the final step to get the result of modular exponentiation, the time-consuming carry propagation can then be eliminated. 2) The number of input operands for the CSA tree is reduced in a very efficient way. 3) The hardware saving is achieved with very limited impact on the original critical path delay when designed with two distinct modular multiplication and square components. Experimental results show that our modular exponentiation design obtains the least hardware complexity compared with the existing work and outperforms them in terms of area-time (AT) complexity as well.

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

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

U2 - 10.1109/TVLSI.2008.2000524

DO - 10.1109/TVLSI.2008.2000524

M3 - Article

VL - 16

SP - 1151

EP - 1161

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 9

M1 - 4579747

ER -