Algorithms and Parallel Computing

17.1 INTRODUCTION

There are many excellent books on applied cryptography that explain the ideas discussed in this chapter such as finite Galois fields and the basic mathematical operations performed in them [101, 102]. It is assumed that the reader of this chapter is already familiar with these concepts and wants to know how the algorithms could be implemented in parallel hardware. A number of cryptographic algorithms (e.g., the Advanced Encryption Standard [AES], elliptic curve cryptography [ECC]) rely heavily on GF(2^m) multiplication [103]. All these algorithms require fast, inexpensive, and secure implementation of multiplication over GF(2^m). Therefore, the design of efficient high-speed algo­rithms and hardware architectures for computing GF(2^m) multiplication are highly required and considered. Hardware implementation techniques for GF(2^m) multiplier include traditional techniques [104, 105] and processor array (PA) techniques [106–108]. Traditional multipliers are not attractive since their hardware structures are irregular and could be quite different for different m values. Moreover, as m gets larger, the propagation delay increases, which causes unavoidable performance deterioration. On the contrary, PA multipliers do not suffer from the above prob­lems. They have regular structures consisting of a number of replicated basic cells. Furthermore, since each basic cell is only connected to its neighboring cells, signals propagate at a high clock speed [107]. In 1984, Yeh ...