Search

During the past decade, elliptic curve cryptography (ECC) has been widely deployed in different scenarios as the main asymmetric cryptosystem due to its smaller key length and relatively higher speed compared with other asymmetric cryptosystems. The most critical operation in ECC computation is point multiplication. In some popular applications such as signature verification schemes, the double point multiplication can be exploited. In this paper, we propose an algorithm and its corresponding architecture to speed up the double point multiplication using a modified binary differential addition chain. The proposed method is highly parallelizable and has been implemented on Virtex-4, Virtex-5, and Virtex-7 over ${{GF}}(2^{163})$ , ${{GF}}(2^{233})$ , and ${{GF}}(2^{283})$ , respectively. Experimental results using hardware implementation on Virtex-4 indicate that the proposed architecture achieves 63% and 16% improvements compared with the previous double point multiplication implementation in terms of required time and efficiency over ${ {GF}}(2^{233})$ , respectively. Additionally, the proposed architecture shows time reduction compared with twice the execution time of the best previous single point multiplication by 39% while achieving 258% higher efficiency. The proposed architecture has also been implemented on ASIC, and the results show that the proposed work improves time and energy consumption compared with the previous work.

Systolic finite field multiplier over $\textit {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 $\textit {GF}(2^{m})$ . We have proposed a computation-core-based 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 pentanomial-based 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 $\textit {GF}(2^{163})$ and $\textit {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 $\textit {GF}(2^{163})$ and $\textit {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 $\textit {GF}(2^{163})$ and $\textit {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.

This paper proposes a scalable and unified digit-serial structure, with low space complexity to perform multiplication and inversion operations in $GF(2^{m})$ , based on the bit serial multiplication algorithm and the previously modified extended Euclidean inversion algorithm. In this structure, the multiplier and inverter shares the data-path and thus saves more area resources and power than the case of using separate data-path for each operation. Also, this structure is suitable for fixed size processor that only reuse the core and does not require to modulate the core size when the field size $m$ is modified. This structure is extracted by applying a nonlinear methodology that gives the designer more flexibility to control the processing element workload. Implementation results for of the proposed scalable and unified digit-serial design and previously reported efficient designs show that the proposed scalable structure achieves a significant reduction in area ranging from 64.3% to 85.5% and also achieves a significant saving in energy ranging from 21.9% to 92.5% over them, but it has lower throughput compared with them. This makes the proposed design more suitable for constrained implementations of cryptographic primitives in ultra-low power devices, such as wireless sensor nodes and radio frequency identification devices.

Systolic implementation of Karatsuba algo- rithm (KA)-based digit-serial multiplier over $GF(2^{m})$ on field- programmable gate array (FPGA) platforms has many attractive features, such as efficient tradeoff in area-time complexity and high-throughput rate. But on the other side, it suffers from high register-complexity, which leads to increase in area and power consumption. In this paper, we present an algorithm and architecture for efficient FPGA implementation of KA-based digit-serial systolic multiplier over $GF(2^{m})$ based on the National Institute of Standards and Technology (NIST) recommended polynomials. A number of efficient techniques have been explored and used to realize efficient implementation of these multipliers. First, we propose a novel KA-based approach, where the computational complexity is significantly reduced compared with the existing one. Second, we propose efficient register minimization techniques, such as redundant register removal, two-stage pipelining, and register sharing to reduce the register complexity of the proposed structure. Third, we adopt an efficient FPGA-specific digit-parallel implementation strategy to optimize the area-time–power complexities of the proposed structure on FPGA platforms. The results obtained from FPGA synthesis indicate that the proposed multiplier (for field based on NIST trinomial $GF(2^{233})$ ) has significantly lower area–time–power complexities than the existing designs, e.g., the proposed structure could achieve 65.7% and 73.6% reduction on area-delay product and power-delay product over the best of existing KA-based systolic structures, respectively.

In this paper, we propose two new algorithms and their hardware implementations for the normal basis multiplication over GF( $p^{m}$ ), where $p \in \{2, 3\}$ . In this case, the proposed multipliers are designed using serial and digit-serial hardware architectures. The normal basis multipliers over GF( $2^{m}$ ) and GF( $3^{m}$ ) are based on two proposed algorithms to compute the multiplication matrices $T_{k}$ in order to speed-up the execution time and to reduce the area resources. It can be seen that the new hardware architecture for the NB multiplier over GF( $2^{m}$ ) has the best characteristics of area complexity presented by Reyhani [16] and time complexity presented by Azarderakhsh and Reyhani [31] . The proposed hardware architectures for the normal basis multipliers over GF(2163), GF(2233), GF(2283),GF(2409), GF(389) and GF(3233) were described in VHDL, and simulated and synthesized using Modelsim and Quartus Prime v16, respectively.

Multiplication is an essential operation in cryptographic computations. One of the important finite fields for such computations is the binary extension field. High-throughput low-complexity multiplication architectures lead to more efficient cryptosystems. In this paper, a high-throughput low-complexity unified multiplier for triangular and dual bases is presented, and is referred to as basic architecture. This multiplier enjoys slightly simpler and more regular structure due to use of the mentioned bases. Additionally, structurally improved architectures have been proposed, which have smaller time complexity than basic ones. This is achieved by the use of parallel processing method. Experimental results show that the proposed basic multipliers implemented using trinomials and pentanomials have, respectively, 37.51% and 68.54% reduction in AT (area $\times$ time). Furthermore, the proposed structurally improved multipliers implemented using trinomials and pentanomials have 94.86% and 34.22% reduction in AT, respectively.

In the literature, the generalized $(a, b)$ - way Karatsuba algorithm (KA) is a well-known high-precision technique for implementing a subquadratic digit-serial multiplication. We present here the corrections to the space and complexities pertaining to addition operations in $(a, b)$ -way KA approach.

The type-II optimal normal basis (ONB) is popularly used to represent $GF(2^{m})$ for elliptic curve cryptosystems. It is shown in the literature that multiplication in binary fields, including those represented by type-II ONB, shifted polynomial basis, and dual basis, can be transformed into non-symmetric Toeplitz matrix-vector product (TMVP) formulation. In this paper, we show that type-II ONB multiplication can be realized by two symmetric TMVPs (STMVP). Moreover, we have proposed a novel folded TMVP block recombination (TMVPBR) for the computation of STMVP. Based on the proposed folded TMVPBR approach, we have proposed a new digit-serial structure for type-II ONB multiplication, while traditional parallel ONB multipliers are based on non-symmetric TMVPBR approach to achieve subquadratic space complexity architecture. The proposed digit-serial structure also involves subquadratic space complexity. By the theoretical analysis as well as from synthesis result, however, we find that the proposed architecture has significantly less area and less area-delay product compared to the existing digit-serial type-II ONB multipliers.

Recently, finite field multipliers having high-throughput rate and low-latency have gained great attention in emerging cryptographic systems, but such multipliers over GF(2 m ) for National Institute Standard Technology (NIST) pentanomials are not so abundant. In this paper, we present two pairs of low-latency and high-throughput bit-parallel and digit-serial systolic multipliers based on NIST pentanomials. We propose a novel decomposition technique to realize the multiplication by several parallel arrays in a 2-dimensional (2-D) systolic structure (BP-I) with a critical-path of 2TX, where TX is the propagation delay of an XOR gate. The parallel arrays in 2-D systolic structure are then projected along vertical direction to obtain a digit-serial structure (DS-I) with the same critical-path. For high-throughput applications, we present another pair of bit-parallel (BP-II) and digit-serial (DS-II) structures based on a novel modular reduction technique, where the critical-path is reduced to (TA+TX), TA being the propagation delay of an AND gate. A strategy for data sharing between a pair of processing elements (PEs) of adjacent systolic arrays has been proposed to reduce area-complexity of BP-I and BP-II further. From synthesis results, it is shown that the proposed multipliers have significantly lower latency and higher throughput than the existing designs. To the best of authors' knowledge, this is the first report on low-latency systolic multipliers for finite fields where latency is independent of field-order.

Karatsuba algorithm (KA) is popularly used for high-precision multiplication by divide-and-conquer approach. Recently, subquadratic digit-serial multiplier based on $(a,2)$ -way KA decomposition is proposed in [1]. In this paper, we extend a $(a,2)$ -way KA to derive a generalized $(a,b)$ -way KA decomposition with $a\neq b$ . We have shown that $(a,2)$ -way KA and mult-way KA are special cases of the proposed $(a,b)$ -way KA decomposition. Based on the proposed KA decomposition, we have established two types of subquadratic digit-serial multipliers, namely, the KA-based multiplier and the recombined KA-based multiplier. From theoretical analysis, as well as, from synthesis results we have shown that the proposed KA-based multipliers have significantly less delay and less area-delay product (ADP) compared to the existing naive digit-serial multipliers.

Karatsuba algorithm (KA) is popularly used for high-precision multiplication of long binary polynomials. The only well-known subquadratic multipliers using KA scheme are, however, based on conventional two-operand polynomial multiplication. In this paper, we propose a novel approach based on 2-way and 3-way KA decompositions for computing three-operand polynomial multiplications. Using these novel KA decompositions, we present here a new subquadratic Montgomery multiplier. Our proposed multiplier involves less area and less delay compared to the schoolbook three-operand multiplier as well as the two-operand multipliers based on conventional KA decomposition. We have used the proposed three-operand Montgomery multiplication to derive a novel efficient scheme for m-ary exponentiation, and proposed a novel architecture for exponentiation. We have analyzed the complexities of proposed design, and shown that the proposed exponentiator can have a small lower bound on time complexity amounting to √m-1 multiplication delays, while traditional exponentiators require nearly m multiplication delays. From synthesis results, it is shown that the proposed exponentiator using subquadratic three-operand multiplier approach has significantly less time complexity, less area-delay product, and less power consumption than the existing exponentiators. Moreover, exponentiation-based cryptosystems, such as pairing based cryptography, could achieve high-speed operation using by our proposed multiplier and m-ary exponentiator.

Finite field GF(2m) arithmetic is becoming increasingly important for a variety of different applications including cryptography, coding theory and computer algebra. Among finite field arithmetic operations, GF(2m) multiplication is of special interest because it is considered the most important building block. This contribution describes a new low latency parallel-in/parallel-out sequential polynomial basis multiplier over GF(2m). For irreducible GF(2m) generating polynomials f(x)=xm+xkt+xkt-1+⋯+xk1+1 with m ≥ 2kt-1, the proposed multiplier has a theoretical latency of 2kt+1 cycles . This latency is the lowest one found in the literature for GF(2m) multipliers. Furthermore, the condition m ≥ 2kt-1 is specially important because the five binary irreducible polynomials recommended by NIST for elliptic curve cryptography (ECC) implementation verify this condition.

Low density parity check (LDPC) codes over GF(2m) are an extension of binary LDPC codes with significantly higher performance. However, the computational complexity of the encoders/decoders for these codes is also higher. Hence there is a substantial lack of hardware implementations for LDPC over GF(2m) codes. This paper proposes a novel variation of the belief propagation algorithm for GF(2m) LDPC codes. The new algorithm results in a reduced hardware complexity when implemented in VLSI. The serial architecture of the novel decoding algorithm and two other algorithms for LDPC over GF(2m) are implemented on an FPGA. The results show that the proposed algorithm has substantial advantages over existing methods. We show that the implementation of LDPC over GF(2m) decoder is feasible for short to medium length codes. The additional complexity of the decoder is balanced by the superior performance of GF(2m) LDPC codes.

Novel systolic and super-systolic architectures are presented for polynomial basis multiplication over GF(2m) based on irreducible trinomials. By suitable cut-set retiming, we have derived here an efficient bit-level-pipelined bit-parallel systolic design for binary field multiplication which requires fewer gates and registers and involves nearly half the time-complexity of the corresponding existing design. We have also suggested a digit-level-pipelined design, which involves lower latency, and fewer registers compared with the bit-level-pipelined structure. Moreover, we have proposed a super-systolic design consisting of a set of systolic arrays in a systolic-pipeline and a pipelined systolic-block design consisting of a pipelined blocks of concurrent systolic arrays. The super-systolic designs have the same average computation time and the same critical path as the proposed bit-level-pipelined design, but can be used to reduce the latency by a factor O(radic(m)) at the cost of marginally higher number of XOR gates and bit-registers. The hardware complexities of proposed super-systolic designs are nearly three times that of the existing bit-parallel structures, but offer very high throughput compared with the others for large values of m. For the field orders m = 233 and m = 409, the proposed structures offer, respectively, ten and eleven times more throughput than the others.

An arithmetic unit (AU) that performs all basic arithmetic operations in the finite field GF(2m) is presented, where m is an arbitrary integer. The presented finite field AU consists of an arithmetic processor, an arithmetic logic unit, and a control unit. The proposed AU has low circuit complexity and is programmable, so that any error-correcting decoder that operates in GF(2m) can be easily implemented with this AU.

A new nonpipelined bit-parallel-shifted polynomial basis multiplier for GF(2n) is presented. For some irreducible trinomials, the space complexity of the multiplier matches the best results available in the literature, and its gate delay is equal to T A+lceillog2nrceilTX, where TA and TX are the delay of one two-input and and xor gates, respectively. To the best of our knowledge, this is the first time that the gate delay bound TA+lceillog2nrceilTX is reached. For some irreducible pentanomials, its gate delay is equal to TA +(1+lceillog2nrceil)TX. NIST has recommended five binary fields for the elliptic curve digital signature algorithm applications: GF(2163), GF(2233), GF(2 283), GF(2409), and GF(2571), but no irreducible trinomials exist for three degrees, viz., 163, 283 and 571. For the three corresponding binary fields, we show that the gate delay of the proposed multiplier is TA+(1+lceillog2nrceil)TX. This result outperforms the previously known results

New classes of linearly independent (LI) transforms that possess fast forward and inverse butterfly diagrams and their corresponding polynomial expansions over Galois Field (2) [GF(2)] are introduced in this paper. The transforms have the smallest computational complexity among all known LI transforms and therefore can be calculated in shorter time when the computation is done by software. Alternatively, the transforms can also be calculated easily and efficiently using hardware. Here, the recursive definitions and fast transform calculations of four basic fastest LI transforms are first given. The definitions are then extended to generate a larger family of LI transforms with the same computational cost through reordering and permutation. Various properties of the transforms and relations between them are presented followed by their hardware implementations as well as experimental results for some binary benchmark functions.

This paper presents a very large-scale integration implementation of Galois field arithmetic for high-speed error-control coding applications that is based on the field GF(p/sup m/) with m a small integer such as 2 or 3 and p a prime of sufficient value to generate the required field size. In this case, the Galois field arithmetic operations of addition, multiplication, and inversion are based on architectures using blocks that perform integer arithmetic modulo p. These integer arithmetic operations modulo p have previously been implemented with low delay power products through the use of one hot coding and barrel shifters circuits based on transistor arrays. In this paper, the same one hot coding and barrel shifters circuits are used to construct circuits that implement addition, multiplication, and inversion over GF(p/sup m/). The circuits for GF(p/sup m/) addition and multiplication with p/spl ne/2, achieve a lower power-delay product than designs based on GF(2/sup m/). Also, the architecture for GF(p/sup m/) inversion can be efficiently implemented when m=2 or m=3.