Word-based montgomery modular multiplication algorithm for low-latency scalable architectures

Ming-Der Shieh, Wen Ching Lin

Research output: Contribution to journalArticle

31 Citations (Scopus)

Abstract

Modular multiplication is a crucial operation in public key cryptosystems like RSA and elliptic curve cryptography (ECC). This paper presents a new word-based Montgomery modular multiplication algorithm which can be used to achieve a low-latency scalable architecture for efficient hardware implementations. We show how to relax the data dependency in conventional word-based algorithms so that a latency of exactly one cycle can be obtained regardless of the chosen word size w (w >1). With the presented operand reduction scheme, the proposed scalable architecture can operate at high speeds and suitable data paths can be chosen for specific applications. Complexity analysis shows that the proposed architecture has the lowest latency and area complexity compared to related scalable architectures. Experimental results demonstrate that our design has area, speed, and flexibility advantages over related schemes.

Original languageEnglish
Article number5441286
Pages (from-to)1145-1151
Number of pages7
JournalIEEE Transactions on Computers
Volume59
Issue number8
DOIs
Publication statusPublished - 2010 Jul 6

Fingerprint

Montgomery multiplication
Modular multiplication
Cryptography
Latency
Hardware
Data Dependency
Public-key Cryptosystem
Complexity Analysis
Hardware Implementation
Efficient Implementation
Elliptic Curves
Lowest
High Speed
Flexibility
Cycle
Path
Architecture
Experimental Results
Demonstrate

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{0a29bde040634cfe9c887167dcfe38b5,
title = "Word-based montgomery modular multiplication algorithm for low-latency scalable architectures",
abstract = "Modular multiplication is a crucial operation in public key cryptosystems like RSA and elliptic curve cryptography (ECC). This paper presents a new word-based Montgomery modular multiplication algorithm which can be used to achieve a low-latency scalable architecture for efficient hardware implementations. We show how to relax the data dependency in conventional word-based algorithms so that a latency of exactly one cycle can be obtained regardless of the chosen word size w (w >1). With the presented operand reduction scheme, the proposed scalable architecture can operate at high speeds and suitable data paths can be chosen for specific applications. Complexity analysis shows that the proposed architecture has the lowest latency and area complexity compared to related scalable architectures. Experimental results demonstrate that our design has area, speed, and flexibility advantages over related schemes.",
author = "Ming-Der Shieh and Lin, {Wen Ching}",
year = "2010",
month = "7",
day = "6",
doi = "10.1109/TC.2010.72",
language = "English",
volume = "59",
pages = "1145--1151",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "8",

}

Word-based montgomery modular multiplication algorithm for low-latency scalable architectures. / Shieh, Ming-Der; Lin, Wen Ching.

In: IEEE Transactions on Computers, Vol. 59, No. 8, 5441286, 06.07.2010, p. 1145-1151.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Word-based montgomery modular multiplication algorithm for low-latency scalable architectures

AU - Shieh, Ming-Der

AU - Lin, Wen Ching

PY - 2010/7/6

Y1 - 2010/7/6

N2 - Modular multiplication is a crucial operation in public key cryptosystems like RSA and elliptic curve cryptography (ECC). This paper presents a new word-based Montgomery modular multiplication algorithm which can be used to achieve a low-latency scalable architecture for efficient hardware implementations. We show how to relax the data dependency in conventional word-based algorithms so that a latency of exactly one cycle can be obtained regardless of the chosen word size w (w >1). With the presented operand reduction scheme, the proposed scalable architecture can operate at high speeds and suitable data paths can be chosen for specific applications. Complexity analysis shows that the proposed architecture has the lowest latency and area complexity compared to related scalable architectures. Experimental results demonstrate that our design has area, speed, and flexibility advantages over related schemes.

AB - Modular multiplication is a crucial operation in public key cryptosystems like RSA and elliptic curve cryptography (ECC). This paper presents a new word-based Montgomery modular multiplication algorithm which can be used to achieve a low-latency scalable architecture for efficient hardware implementations. We show how to relax the data dependency in conventional word-based algorithms so that a latency of exactly one cycle can be obtained regardless of the chosen word size w (w >1). With the presented operand reduction scheme, the proposed scalable architecture can operate at high speeds and suitable data paths can be chosen for specific applications. Complexity analysis shows that the proposed architecture has the lowest latency and area complexity compared to related scalable architectures. Experimental results demonstrate that our design has area, speed, and flexibility advantages over related schemes.

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

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

U2 - 10.1109/TC.2010.72

DO - 10.1109/TC.2010.72

M3 - Article

VL - 59

SP - 1145

EP - 1151

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 8

M1 - 5441286

ER -