Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19]


Journal of Information Science and Engineering, Vol. 25 No. 5, pp. 1555-1573 (September 2009)

An Efficient Multiplier/Divider Design for Elliptic Curve Cryptosystem over GF(2m)*

Department of Electrical Engineering
National Cheng Kung University
Tainan, 701 Taiwan
+Chip Implementation Center
National Applied Research Laboratories
Hsinchu, 300 Taiwan

Using the concept of reciprocal polynomial, this paper shows that a field multiplication over GF(2m) can be implemented by extended Steins 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 steins division algorithm, MSB-first multiplier, polynomial basis

Full Text () 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.