TAILIEUCHUNG - Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases

In this paper, we present two vector-level software algorithms which essentially eliminate such bit-wise operations for Gaussian normal bases. Our analysis and timing results show that the software implementation of the proposed algorithm is faster than previously reported normal basis multiplication algorithms. | 34 IEEE TRANSACTIONS ON COMPUTERS VOL. 55 NO. 1 JANUARY 2006 Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases Arash Reyhani-Masoleh Member IEEE Abstract Recently implementations of normal basis multiplication over the extended binary field GF 2m have received considerable attention. A class of low complexity normal bases called Gaussian normal bases has been included in a number of standards such as IEEE 1 and NIST 2 for an elliptic curve digital signature algorithm. The multiplication algorithms presented there are slow in software since they rely on bit-wise inner product operations. In this paper we present two vector-level software algorithms which essentially eliminate such bit-wise operations for Gaussian normal bases. Our analysis and timing results show that the software implementation of the proposed algorithm is faster than previously reported normal basis multiplication algorithms. The proposed algorithm is also more memory efficient compared with its look-up table-based counterpart. Moreover two new digit-level multiplier architectures are proposed and it is shown that they outperform the existing normal basis multiplier structures. As compared with similar digit-level normal basis multipliers the proposed multiplier with serial output requires the fewest number of XOR gates and the one with parallel output is the fastest multiplier. Index Terms Finite field multiplication normal basis Gaussian normal basis software algorithms ECDSA. --------------------- ---------------------- 1 Introduction Arithmetic operations in the finite field GF 2m are extensively used in elliptic curve cryptographic protocols and discrete-log-based cryptosystems 1 . The binary field GF 2m is a set of 2m elements where each of these elements can be represented by a bit string of length m. The field can also be considered as an m-dimensional vector space with m linearly independent elements over GF 2 known as a basis. There are two .

• Toán học
• Efficient Algorithms and Architectures
• The Multiplication algorithms
• Conventional GNB Multiplication
• Gaussian Normal Bases
• The Field Multiplication
• A more efficient algorithm