¡@

Using the concept of reciprocal polynomial, this paper shows that a field multiplication over GF(2m) can be implemented by extended Stein¡¦s algorithm, one of the algorithms used to accomplish division. In this way, a field multiplier can be efficiently embedded into a divider with very little hardware overhead for operand selection based on a fundamental change at the algorithmic level. When applying the developed combined multiplication and division (CMD) algorithm to Elliptic Curve Cryptography (ECC) using affine coordinates, we achieve about 13.8% reduction on the area requirement with almost no performance degradation compared to the one implemented with two distinct components. Experimental results also demonstrate that not only our CMD circuit has the area advantage (up to 12.7%) in comparison with other low-cost design but also the resulting area-efficient design of ECC system exhibits considerable improvement on the area-time (AT) complexity of previous work.

Keywords: elliptic curve cryptography (ECC), affine coordinates, combined multiplier and divider (CMD) design, extended stein¡¦s division algorithm, MSB-first multiplier, polynomial basis

Retrieve PDF document (200909_15.pdf)

Received October 31, 2007; revised April 17, 2008; accepted May 15, 2008.
Communicated by Liang-Gee Chen.
^* This work was supported in part by the National Science Council of R.O.C. under grant No. NSC 96-2221- E-006-296-MY3, and was presented in part in Proceedings of IEEE Region 10 Conference TENCON, Taipei, Taiwan, Oct. 2008.