Search

Arithmetic operations over binary extension fields $GF(2^{m})$ have many important applications in domains such as cryptography, code theory and digital signal processing. These applications must be fast, so low-delay implementations of arithmetic circuits are required. Among $GF(2^{m})$ arithmetic operations, field multiplication is considered the most important one. For hardware implementation of multiplication over binary finite fields, irreducible trinomials and pentanomials are normally used. In this brief, low-delay FPGA-based implementations of bit-parallel $GF(2^{m})$ polynomial basis multipliers are presented, where a new multiplier based on irreducible trinomials is given. Several post-place and route implementation results in Xilinx Artix-7 FPGA for different $GF(2^{m})$ finite fields are reported. Experimental results show that the proposed multiplier exhibits the best $delay$ , with a delay improvement of up to 4.7%, and the second best $Area\times Time$ complexities when compared with similar multipliers found in the literature.

In this article, a new architecture of bit-serial polynomial basis (PB) multipliers over the binary extension field $GF(2^m)$ G F ( 2 m ) generated by irreducible trinomials is presented. Bit-serial $GF(2^m)$ G F ( 2 m ) PB multiplication offers a performance/area trade-off that is very useful in resource constrained applications. The architecture here proposed is based on LFSR ( Linear-Feedback Shift Register ) and can perform a multiplication in $m$ m clock cycles with a constant propagation delay of $T_{A} + T_{X}$ T A + T X . These values match the best time results found in the literature for bit-serial PB multipliers with a slight reduction of the space complexity. Furthermore, the proposed architecture can perform the multiplication of two operands for $t$ t different finite fields $GF(2^m)$ G F ( 2 m ) generated by $t$ t irreducible trinomials simultaneously in $m$ m clock cycles with the inclusion of $t(m-1)$ t ( m - 1 ) flipflops and $tm$ t m XOR gates.

Quantum computers represent a serious threat to the safety of modern encryption standards. Within symmetric cryptography, Advanced Encryption Standard (AES) is believed to be quantum resistant if the key sizes are large enough. Arithmetic operations in AES are performed over the binary field $${\mathbb {F}}_{2^m}$$ generated by an irreducible pentanomial of degree $$m = 8$$ using polynomial basis (PB) representation. Multiplication over $${\mathbb {F}}_{2^m}$$ is the most complex and important arithmetic operation, so efficient implementations are highly desired. A number of quantum circuits realizing $${\mathbb {F}}_{2^m}$$ multiplication have been proposed, where the number of qubits, the number of quantum gates and the depth of the circuit are mainly considered as optimization objectives. In this work, optimized reversible quantum circuits for $${\mathbb {F}}_{2^8}$$ multiplication using PB generated by two irreducible pentanomials are presented. The proposed reversible multipliers require the minimum number of qubits and CNOT gates, and the minimum depth among similar $${\mathbb {F}}_{2^8}$$ multipliers found in the literature.

Hardware implementations of arithmetic operations over binary finite fields GF(2^m) are widely used in several important applications, such as cryptography, digital signal processing and error-control codes. In this paper, efficient. reconfigurable implementations of bit-parallel canonical basis multipliers over binary fields generated by type II irreducible pentanomials f_(y) = y^m + y^(n+2) + y^(n+1) + y^n + 1 are presented. These pentanomials are important because all five binary fields recommended by NIST for ECDSA can be constructed using such polynomials. In this work, a new approach for CF(2^m) multiplication based on type II pentanomials is given and several post-place and route implementation results in Xilinx Artix-7 FPGA are reported. Experimental results show that the proposed multiplier implementations improve the area x time parameter when compared with similar multipliers found in the literature.

Modular exponentiation with large modulus and exponent, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems. Typically, the Montgomery's modular-multiplication algorithm is used since no trial division is necessary, and the carry-save addition (CSA) is employed to reduce the critical path. In this paper, we optimize the Montgomery's multiplication and propose architectures to perform the least significant bit first and the most significant bit first algorithms. The developed architecture has the following distinctive characteristics: 1) use of digit serial approach for Montgomery multiplication. 2) Conversion of the CSA representation of intermediate multiplication using carry-skip addition. This allows the critical path to be reduced, albeit with a small-area speed penalty; and 3) precompute the quotient value in Montgomery's iteration in order to speed up the operating frequency. In this paper, we present results in Xilinx Virtex 5 and in 0.18-μm application-specified integrated circuit technologies. For fair comparison with previous works, Xilinx Virtex 2 results are reported. Experimental results show that the proposed modular exponentiation and modular-multiplication design obtain the best delay performance compared with the published works and outperform them in terms of area-time complexity as well.

Efficient hardware implementations of arithmetic operations in the Galois field $GF(2^{m})$ are highly desirable for several applications, such as coding theory, computer algebra and cryptography. Among these operations, multiplication is of special interest because it is considered the most important building block. Therefore, high-speed algorithms and hardware architectures for computing multiplication are highly required. In this paper, bit-parallel polynomial basis multipliers over the binary field $GF(2^{m})$ generated using type II irreducible pentanomials are considered. The multiplier here presented has the lowest time complexity known to date for similar multipliers based on this type of irreducible pentanomials.

A new formulation for the canonical basis multiplication in the finite fields GF(2/sup m/) based on the use of a triangular basis and on the decomposition of a product matrix is presented. From this algorithm, a new method for multiplication (named transpositional) applicable to general irreducible polynomials is deduced. The transpositional method is based on the computation of 1-cycles and 2-cycles given by a permutation defined by the coordinate of the product to be computed and by the cardinality of the field GF(2/sup m/). The obtained cycles define groups corresponding to subexpressions that can be shared among the different product coordinates. This new multiplication method is applied to five types of irreducible trinomials. These polynomials have been widely studied due to their low-complexity implementations. The theoretical complexity analysis of the corresponding bit-parallel multipliers shows that the space complexities of our multipliers match the best results known to date for similar canonical GF(2/sup m/) multipliers. The most important new result is the reduction, in two of the five studied trinomials, of the time complexity with respect to the best known results.

Galois (or finite) fields are used in a wide number of technical applications, playing an important role in several areas such as cryptographic schemes and algebraic codes, used in modern digital communication systems. Finite field arithmetic must be fast, due to the increasing performance needed by communication systems, so it might be necessary for the implementation of the modules performing arithmetic over Galois fields on semiconductor integrated circuits. Galois field multiplication is the most costly arithmetic operation and different approaches can be used. In this paper, the fundamentals of Galois fields are reviewed and multiplication of finite-field elements using three different representation bases are considered. These three multipliers have been implemented using a bit-parallel architecture over reconfigurable hardware and experimental results are presented to compare the performance of these multipliers.

Modular exponentiation with large modulus and exponent has been widely used in public key cryptosystems. Montgomery´s modular multiplication algorithm is normally used since no trial division is necessary and the critical path is reduced by using carry-save addition (CSA). In this paper, the Montgomery multiplication is greatly optimized and architectures are proposed to perform the Least-Significant-Bit (LSB) first and the Most-Significant-Bit (MSB) first algorithms. The architecture here presented has the following distinctive characteristics: 1) Use of digit-serial approach for Montgomery multiplication. 2) Conversion of the CSA representation of intermediate multiplication using carry-skip addition which reduces the critical path with a small area-speed penalty. 3) Precompute quotient value in Montgomery iteration in order to speed up operation frequency. In this work, implementation results in Xilinx Virtex 5 and Virtex 2 are reported. Experimental results show that the proposed modular exponentiation and modular multiplication design obtains the best delay performance compared with previous published works and outperforms them in terms of area-time complexity.