Low Complexity Implementation of Unified Systolic Multipliers for NIST Pentanomials and Trinomials Over $\textit{GF}(2^{m})$
1
Citation
29
Reference
10
Related Paper
Citation Trend
Abstract:
Systolic finite field multiplier over GF(2 m ) based on the National Institute of Standards and Technology (NIST) recommended pentanomials or trinomials can be used as a critical component in many cryptosystems. In this paper, for the first time, we propose a novel low-complexity unified (hybrid field size) systolic multiplier for NIST pentanomials and trinomials over GF(2 m ). We have proposed a computation-corebased design strategy to obtain the desired low-complexity unified multiplier for both NIST pentanomials and trinomials. The proposed multiplier can swift between pentanomial-based and trinomial-based multipliers through a control signal. First of all, a novel strategy is briefly introduced to implement a certain matrix-vector multiplication, which can be packed as a standard computation core (or computation core like). Then, based on the computation-core concept, a novel unified multiplication algorithm is derived that it can realize both the pentanomialbased and trinomial-based multiplications. After that, an efficient systolic structure is presented that it can fully employ the introduced computation core. A detailed example of the proposed unified multiplier (for GF(2 163 ) and GF(2 233 )) is also presented. Both the theoretical and field-programmable gate array implementation results show that the proposed design has efficient performance in area-time-power complexities, e.g., the proposed design (the one performs GF(2 163 ) and GF(2 233 ) multiplications) is found to have at least 14.2% and 13.3% less area-delay product and power-delay product than the combination of the existing individual GF(2 163 ) and GF(2 233 ) multipliers (best among all competing designs), respectively. Because of its structural regularity and functional flexibility, the proposed unified multiplier can be used as an intellectual property core for various cryptosystems.Keywords:
Trinomial
NIST
GF(2)
Trinomial
GF(2)
Cite
Citations (3)
This paper considers the design of low-complexity bit-parallel dedicated finite field multiplier. A systematic design approach of Mastrovito (1988) multiplier is proposed, which is applicable to GF(2/sup m/) generated by an arbitrary irreducible polynomial. This approach extensively exploits the spatial correlation of matrix elements in Mastrovito multiplication to reduce the complexity. The developed general Mastrovito multiplier is highly modular, which is desirable for VLSI hardware implementation. Meanwhile, the presented approach can be used to develop efficient Mastrovito multipliers for several special irreducible polynomials, such as a trinomial and equally-spaced-polynomial, and further find some other special irreducible polynomials which can also lead to low-complexity multipliers.
Trinomial
GF(2)
Irreducible polynomial
Primitive polynomial
Cite
Citations (8)
Trinomial
GF(2)
Polynomial basis
Modular arithmetic
Irreducible polynomial
Primitive polynomial
Cite
Citations (9)
Montgomery multiplication in GF(2/sup m/) is defined by a(x)b(x)r/sup -1/(x) mod f(x), where the field is generated by a root of the irreducible polynomial f(x), a(x) and b(x) are two field elements in GF(2/sup m/), and r(x) is a fixed field element in GF(2/sup m/). In this paper, first, a slightly generalized Montgomery multiplication algorithm in GF(2/sup m/) is presented. Then, by choosing r(x) according to f (x), we show that efficient architectures of bit-parallel Montgomery multiplier and squarer can be obtained for the fields generated with an irreducible trinomial. Complexities of the Montgomery multiplier and squarer in terms of gate counts and time delay of the circuits are investigated and found to be as good as or better than that of previous proposals for the same class of fields.
Trinomial
GF(2)
Primitive polynomial
Irreducible polynomial
Cite
Citations (72)
Trinomial
GF(2)
Primitive polynomial
Polynomial basis
Basis (linear algebra)
Irreducible polynomial
Standard basis
Cite
Citations (10)
A new high regular structure of partial parallel multiplier for irreducible trinomial generated finite field is proposed. Through the analysis of multiplication over finite field GF(2m),generated by irreducible trinomial,the basic computation format is deduced.The novel multiplier structure is designed based on the basic computation format.According to the complexity analysis, the multiplier has the same complexity with the optimal designs up to date.Meanwhile,it can be configured according to specific demands of all kinds of applications.
Trinomial
Cite
Citations (0)
A trade-off between performance and area is important to design an efficient hardware structure for arithmetic operations in GF(2m). Proposed is a hybrid multiplier for GF(2m) with an irreducible trinomial, which can be constructed in variable structures depending on such a performance area trade-off.
Trinomial
GF(2)
Cite
Citations (8)
The efficient hardware design of finite field multiplication is an very important research topic for and efficient implementation of cryptosystem based on arithmetic in finite field GF(). We used special generating trinomial to construct a bit-parallel multiplier over finite field with low space complexity. To reduce processing time, The hardware architecture of proposed multiplier is similar with existing Mastrovito multiplier. The complexity of proposed multiplier is depend on the degree of intermediate term and the space complexity of the new multiplier is lower than existing multiplier's. The time complexity of the proposed multiplier is equal to that of existing multiplier or increased to ) but space complexity is reduced to maximum 25%.
Trinomial
GF(2)
Polynomial basis
Finite field arithmetic
Cite
Citations (0)
Recently, a considerable number of studies have been conducted on pairing based cryptosystems. The efficiency of pairing based cryptosystems depends on finite fields, similar to existing public key cryptosystems. In general, pairing based ctyptosystems are defined over finite fields of chracteristic three, GF(), based on trinomials. A multiplication in GF() is the most dominant operation. This paper proposes a new most significant digit(MSD)-first digit- serial multiplier. The proposed MSD-first digit-serial multiplier has the same area complexity compared to previous multipliers, since the modular reduction step is performed in parallel. And the critical path delay is reduced from 1MUL+(log +1)ADD to 1MUL+(log )ADD. Therefore, when the digit size is not , the time delay is reduced by one addition.
Trinomial
GF(2)
Modular arithmetic
Numerical digit
Cite
Citations (0)