Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring over GF(2^m)

Citations Over TimeTop 10% of 2009 papers

Abstract

Multiplication and squaring are main finite field operations in cryptographic computations and designing efficient multipliers and squarers affect the performance of cryptosystems. In this paper, we consider the Montgomery multiplication in the binary extension fields and study different structures of bit-serial and bit-parallel multipliers. For each of these structures, we study the role of the Montgomery factor, and then by using appropriate factors, propose new architectures. Specifically, we propose two bit-serial multipliers for general irreducible polynomials, and then derive bit-parallel Montgomery multipliers for two important classes of irreducible polynomials. In this regard, first we consider trinomials and provide a way for finding efficient Montgomery factors which results in a low time complexity. Then, we consider type-II irreducible pentanomials and design two bit-parallel multipliers which are comparable to the best finite field multipliers reported in the literature. Moreover, we consider squaring using this family of irreducible polynomials and show that this operation can be performed very fast with the time complexity of two XOR gates.

Related Papers

• → Hybrid multiplier for GF (2 m ) defined by some irreducible trinomials(2004)8 cited
• GF(2^m)상의 기약 3 항식을 이용한 승산기 설계 ( A Design of Multiplier Over GF(2^m) using the Irreducible Trinomial )(2001)
• Low Space Complexity Bit Parallel Multiplier For Irreducible Trinomial over GF($2^n$)(2008)
• Normal basis of finite field GF(2 super m)(1986)
• Montgomery Multiplier and Squarer in GF(2 m )(2000)