Jun-Cheol Jeon and Kee-Young Yoo
Dept. Of Computer Engineering Kyungpook
National University
Daegu, Korea
email: jcjeon33@purple.knu.ac.kr
In cryptography, to achieve a high level of security, many of public-key algorithms, that rely on computations in GF(2n), require large field size, some as large as GF(22000). Hence, there is a need to develop an efficient algorithm for the multiplication in GF(2n). However, significantly smaller parameters can be used in ECC than in other competitive systems such RSA and ElGamal, but with equivalent levels of security. Some benefits of having smaller key sizes include faster computations, and reductions in processing power, storage space and bandwidth. This makes ECC ideal for constrained environments such as pagers, PDAs, cellular phones and smart cards.
The two elliptic curve operations are the Add and Double, which are computed by field arithmetic operations, such as additions, modular multiplications, modular squarings, inversions and divisions. The addition operation for field elements is trivial and squaring is so much faster than regular multiplication that it can be ignored in rough comparisons of the timings. The important contributors to the run time are inversions and divisions. Thus we propose efficient inversion and division architecture by recursive AB2 multiplication algorithm based on Cellular Automata (CA) in Elliptic curve cryptosystems (ECC) over GF(2n). The proposed architectures can be used in the effectual hardware design of coprocessor for ECC since they have high regularity and a reduced latency. We focused on the architectures in ECC, which uses restricted irreducible polynomials, specially, trinomials. Typical parallel architectures are usually constructed by systolic schemes. They cannot reduce much hardware complexity even though they use trinomials as irreducible polynomial, since both multiplier and multiplicand are inputted in parallel and computed simultaneously. However in our architecture, multiplicand is inputted in parallel while multiplier is inputted in serial fashion so that we reduced much hardware requirements at the same latency. The division structure has a time complexity of n(n-1)(T_AND+T_XOR) and hardware complexity of n(AND+XOR+MUX+3REGISTER)+2XOR. Our architectures offer a remarkable area and time performance. Keywords: Elliptic Curve Cryptosystems, Division, Finite Fields, Cellular Automata, Irreducible Polynomial.