Realizing arbitrary-precision modular multiplication with a fixed-precision multiplier datapath

Grossschaedl, Johann and Savaş, Erkay and Yumbul, Kazım (2009) Realizing arbitrary-precision modular multiplication with a fixed-precision multiplier datapath. In: 2009 International Conference on ReConFigurable Computing and FPGAs, ReConFig09, Cancun, Mexico (Accepted/In Press)

[thumbnail of This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing) and publisher's version/PDF ; author cannot archive post-print (ie final draft post-refereeing)] PDF (This is a RoMEO green publisher -- author can archive pre-print (ie pre-refereeing) and publisher's version/PDF ; author cannot archive post-print (ie final draft post-refereeing))
new_multiplier_johann.pdf

Download (132kB)

Abstract

Within the context of cryptographic hardware, the term scalability refers to the ability to process operands of any size, regardless of the precision of the underlying data path or registers. In this paper we present a simple yet effective technique for increasing the scalability of a fixed-precision Montgomery multiplier. Our idea is to extend the datapath of a Montgomery multiplier in such a way that it can also perform an ordinary multiplication of two n-bit operands (without modular reduction), yielding a 2n-bit result. This conventional (nxn->2n)-bit multiplication is then used as a “sub-routine” to realize arbitrary-precision Montgomery multiplication according to standard software algorithms such as Coarsely Integrated Operand Scanning (CIOS). We show that performing a 2n-bit modular multiplication on an n-bit multiplier can be done in 5n clock cycles, whereby we assume that the n-bit modular multiplication takes n cycles. Extending a Montgomery multiplier for this extra functionality requires just some minor modifications of the datapath and entails a slight increase in silicon area.
Item Type: Papers in Conference Proceedings
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 26 Nov 2009 23:35
Last Modified: 26 Apr 2022 08:53
URI: https://research.sabanciuniv.edu/id/eprint/12987

Actions (login required)

View Item
View Item