Efficient elliptic curve cryptosystems

Document Type: Research Paper

Authors

1 Mathematics Department, Birzeit University, P.O. Box 14, Palestine

2 Applied Mathematics Department, Palestine Technical University--Kadoorie, Tulkarm, Palestine

Abstract

Elliptic curve cryptosystems (ECC) are new generations of public key cryptosystems that have a smaller key size for the same level of security. The exponentiation on elliptic curve is the most important operation in ECC, so when the ECC is put into practice, the major problem is how to enhance the speed of the exponentiation. It is thus of great interest to develop algorithms for exponentiation, which allow efficient implementations of ECC. In this paper, we improve efficient algorithm for exponentiation on elliptic curves defined over Fp in terms of affine coordinates. The algorithm computes directly from random points P and Q on an elliptic curve, without computing the intermediate points. Moreover, we apply the algorithm to exponentiation on elliptic curves with width-w Mutual Opposite Form (wMOF) and analyze their computational complexity. This algorithm can speed up the wMOF exponentiation of elliptic curves of size 160-bit about (21.7 %) as a result of its implementation with respect to affine coordinates.

Keywords