Recently, cryptographic applications based on finite fields have attracted much interest. This paper presents two new algorithms, called time-dependent and time-independent multiplication algorithms over a finite field GF(2m) by employing an interleaved conventional multiplication and a folded technique. The proposed algorithms permit efficient realization of the bit-parallel multiplication using iterative arrays. The results show that our proposed time-dependent and time-independent multipliers save about 38% and 54% space complexity as compared to the traditional multipliers, respectively.

Recently, cryptographic applications based on finite fields have attracted much interest. This paper presents a transformation method to implement low-complexity Montgomery multipliers for all-one polynomials and trinomials. Using this method, we propose a new bit-parallel systolic architecture for computing multiplications over GF(2/sup m/). These new multipliers have a latency m+1 clock cycles and each cell incorporates at most one 2-input AND gate, two 2-input XOR gates, and four 1-bit latches. Moreover, these new multipliers are shown to exhibit significantly lower latency and circuit complexity than the related systolic multipliers and are highly appropriate for VLSI systems because of their regular interconnection pattern, modular structure, and fully inherent parallelism.

Two operations, the cyclic shifting and the inner product, are defined by the properties of irreducible all one polynomials. An effective algorithm is proposed for computing multiplications over a class of fields GF(2/sup m/) using the two operations. Then, two low-complexity bit-parallel systolic multipliers are presented based on the algorithm. The first multiplier is composed of (m+1)/sup 2/ identical cells, each consisting of one 2-input AND gate, one 2-input XOR gate, and three 1-bit latches. The other multiplier comprises of (m+1)/sup 2/ identical cells and mXOR gates. Each cell consists of one 2-input AND gate, one 2-input XOR gate, and four 1-bit latches. Each multiplier exhibits very low latency and propagation delay and is thus very fast. Moreover, the architectures of the two multipliers can be applied in computing multiplications over the class of fields GF(2/sup m/) in which the elements are represented with the root of an irreducible equally spaced polynomial of degree m.

A conference key distribution system (CKDS) can provide a common secret communication key to a set of M stations. A CKDS based on Lagrange interpolating polynomial is introduced. It is easy to see that breaking this system is equivalent to break the Diffie-Hellman public-key distribution system. This conference key is selected by the conference chairstation and hidden in the Lagrange interpolating polynomial. Recovering this key by each participating station only requires M-1 multiplications and M-2 additions over a finite field GF(P).>