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

Warning The system is temporarily closed to updates for reporting purpose.

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)

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)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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
ID Code:12987
Deposited By:Erkay Savaş
Deposited On:26 Nov 2009 23:35
Last Modified:24 Jul 2019 09:52

Repository Staff Only: item control page