Multiplier for Public-Key Cryptosystem Based on Cellular Automata - Computer Network Security - page 436

Multiplier for Public-Key Cryptosystem
Based on Cellular Automata *

Hyun Sung Kim 1 and Sung Ho Hwang 2

1 Kyungil University, Computer Engineering
712-701, Kyungsansi, Kyungpook Province, Korea
[e-mail]
2 Pohang University of Sci. & Tech., Dept. of Computer Eng. & Sci.
790-784, Pohangsi, Kyungpook Province, Korea
[e-mail]

Abstract. This paper proposes two new multipliers based on cellular automata
over finite field. They are implemented with the LSB-first fashion using stan-
dard basis representation. Since they have regularity, modularity and concur-
rency, they are suitable for VLSI implementation and could be used in IC cards.
They can be used as a basic architecture for the public-key cryptosystems.

1 Introduction

Finite field GF (2 m ) arithmetic is fundamental to the implementation of a number of
modern cryptographic systems and schemes of certain cryptographic systems[1].
Most arithmetic operations, such as exponentiation, inversion, and division opera-
tions, can be carried out using just a modular multiplier.
CA (Cellular Automata), first introduced by John Von Neumann in the 1950s,
have been accepted as a good computational model for the simulation of complex
physical systems [2-3]. Choudhury proposed an LSB-first multiplier using CA with
low latency [3]. For the better complexity, Itoh and Tsujii [4] designed two low-
complexity multipliers for the class of GF (2 m ), based on an irreducible AOP (All One
Polynomial) of degree m and irreducible equally spaced polynomial of degree m .
Later, Kim in [5] developed linear feedback shift register based multipliers with low
complexity of hardware implementations using the property of AOP.
Accordingly, the purpose of this paper is to propose two new modular multipliers
over GF (2 m ). The multipliers deploy the mixture of the advantages from the previous
architectures in the perspective of area and time complexity. They are easy to imple-
ment VLSI hardware and could be used in IC cards as the multipliers have a particu-
larly simple architecture.
It is necessary to give an brief overview of finite fields and cellular automata. First,
Finite field : GF (2 m ) contains 2 m elements that are generated by an irreducible poly-
nomial of degree m over GF (2). A polynomial f ( x ) of degree m is said to be irreduci-
* This work was supported by the research fund of Kyungil University.