Kyo Min Ku
Mobilab Inc.
Korea
email: kmku@mobilab.co.kr
This paper presents a MSB-first exponentiation over GF(2m) using a cellular automata for public key crypto system.
The AB2 multiplication is the basic structure for MSB-first exponentiation. For more efficient exponentiation, it is necessary to develop more efficient AB2 multiplier.
Most previous research activities related to AB2 multiplication have focused on a systolic array. In a research, AB2 multiplication is performed on a systolic array in 3m clock cycles using mxm cells, while other presents an algorithm that can perform AB2 multiplication in 2m+m/2 clock cycles using (mxm)/2 cells.
The purpose of the current paper is to investigate and develop a simple and efficient architecture for the exponentiation over GF(2m), which is the basic computation for all public key crypto systems.
Accordingly, a new structure is proposed which facilitates AB2 multiplication for effective exponentiation on GF(2m) using a cellular automata. And then we propose a new architecture for exponentiation using only one proposed AB2 multiplier. The proposed structure can perform AB2 multiplication in m clock cycles using m cells, (3m-2) AND gates, m 2-input XOR gates, (m-1) 3-input XOR gates and 1 (m-1)-bit register, 2 m-bit registers with a cellular automata. Therefore, the exponentiation can be performed in (m2+m-2) clock cycles using (3m-2) AND gates, m 2-input XOR gates, (m-1) 3-input XOR gates, 2 Muxes, 3 m-bit registers, 1 (m-1)-bit register.
As a result, the performance of the AB2 multiplier is much more efficient in terms of time and space than that of the previous researches. And the proposed architecture for exponentiation is much more efficient in terms of space even though it is the same in terms of time.