Browse Prior Art Database

A Speedup Technique for High Performance Foster-Montgomery Multipliers used in Security Processors

IP.com Disclosure Number: IPCOM000010391D
Original Publication Date: 2002-Nov-22
Included in the Prior Art Database: 2002-Nov-22
Document File: 6 page(s) / 46K

Publishing Venue

Motorola

Related People

Amir K Daneshbeh: AUTHOR

Abstract

Montgomery multiplication is a modular multiplication technique which does not require a division step after each multiplication. This division step, required to compute a remainder for modulo reduction, is a time consuming step specially for cryptographic applications where the size of the modulus of the underlying field may exceed 4096 bits. The Montgomery multiplication method transforms this costly modulo reduction step into a simpler scheme based on division by multiples of a word-size constant (simply by truncation). This is achieved at the expense of pre-computing an auxiliary correction term, called m, which may require not only a pre-computation but also the storage of the m term which could be as large as the modulus itself. Foster-Montgomery multiplication method demonstrates that the same multiplication architecture can be used to compute m and more importantly, this term can be computed word-wise and as the first cycle of a normal block multiplication process. Hence, no requirement for an extra storage space. However, the data swapping associated with using the same execution unit for different output computations limits the use of pipelining for high performance. The innovation presented here is a solution to speed up a Foster-Montgomery multiplier by using pipelining without associated timing overheads due to the m computation.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 34% of the total text.

A Speedup Technique for High Performance Foster-Montgomery Multipliers used in Security Processors

Amir K Daneshbeh

Abstract
Montgomery multiplication is a modular multiplication technique which does not require a division step after each multiplication. This division step, required to compute a remainder for modulo reduction, is a time consuming step specially for cryptographic applications where the size of the modulus of the underlying field may exceed 4096 bits. The Montgomery multiplication method transforms this costly modulo reduction step into a simpler scheme based on division by multiples of a word-size constant (simply by truncation). This is achieved at the expense of pre-computing an auxiliary correction term, called m, which may require not only a pre-computation but also the storage of the m term which could be as large as the modulus itself. Foster-Montgomery multiplication method demonstrates that the same multiplication architecture can be used to compute m and more importantly, this term can be computed word-wise and as the first cycle of a normal block multiplication process. Hence, no requirement for an extra storage space. However, the data swapping associated with using the same execution unit for different output computations limits the use of pipelining for high performance. The innovation presented here is a solution to speed up a Foster-Montgomery multiplier by using pipelining without associated timing overheads due to the m computation.

Section 1  Introduction

A speedup technique used to increase the performance of a Foster-Montgomery multiplier is proposed. The inclusion of an auxiliary multiplier in a Foster-Montgomery design is presented which computes a m term word wise according to a Foster-Montgomery scheme and this will be used by the main array multiplier releasing the latter from timing constraints due to this computation. This m term can be viewed as a correction term required by the main array multiplier to force the lowest word of its partial product to become zero while each iteration of a multiplication loop proceeds.

Section 2  Foster-Montgomery Multiplication

Montgomery multiplication is a block modular multiplication technique. Modular multiplication is a multiplication to compute a product followed by a modulo reduction step. Modulo reduction is the computation of a remainder of this product divided by the modulus of the underlying field. This can be very time consuming if performed in a naive long division way.

Montgomery multiplication technique described originally by P. L. Montgomery in "Modular multiplication without trial division", Mathematics of Computation, 44:519--521, 1985, provides a means to transform the modulo reduction step of a modular multiplication into a much simpler division by multiples of a word size constant which can be easily implemented by truncation. Moreover, such a transformation provides a means to overlap the two steps in a unified multiply and reduce step. But, su...