This paper introduces several new techniques and algorithms to speed up the elliptic curve digital signature and reduce the size of the transited parameters. The basic idea is to use sparse elements for the curve coefficients and the first base point coordinate. The implementation analysis shows that the addition formula calculations are improved about 40 percent. The sparse elements are introduced with a compact representation, thus the digital signature calculations are speeded up about 40-60 percent, and the public key parameters are reduced about 37-48 percent.

[1] Al-Daoud E. and Ramlan M., “A New Addition Formula for Elliptic Curves Over GF(2n ),” IEEE Transactions on Computers, vol. 51, no. 8, pp. 972-975, August 2002.

[2] Al-Daoud E. and Ramlan M., “Elliptic Curve Arithmetic Operations Over GF(2n ) and GF(P) for Cryptosystems Purposes,” in Proceedings of the International Conference on Mathematics and its Applications in the New Millennium, pp. 381-388, 2000.

[3] Blake I. F., Seroussi G., and Smart N. P., Elliptic Curve in Cryptography, University Press, London, Cambridge, 1999.

[4] Certicom, http://www.certicom.com, accessed on March 5, 2003.

[5] Gupta V., Gupta S., and Sheueling C., “Performance Analysis of Elliptic Curve Cryptography for SSL,” in Proceedings of ACM Workshop on Wireless Security, Atlanta, Georgia, 2002.

[6] Gura N., Eberle H., and Shantz S. H., “Generic Implementations of Elliptic Curve Cryptography Using Partial Reduction,” in Proceedings of 9th ACM Conference on Computers and Communications Security, Washington DC, 2002.

[7] Gura N., Shantz S. C., Eberle H., Finchelstein D., Gupta S., Gupta V., and Stebila D., “An End-to- End Systems Approach to Elliptic Curve Cryptography,” in Proceedings of CHES'2002 Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, Springer-Verlag, Redwood City, California, 2002.

[8] Ha J. S., Kim Y. H., and Lee K. Y., “Compact Implementation of Elliptic Curve Cryptography System Using a FPGA,” in Proceedings of the 9th Korean Conference on Semiconductors, pp. 813- 814, 2002.

[9] Hankerson D., López J. and Menezes A. J., “Software Implementation of Elliptic Curve Cryptography over Binary Fields,” in Proceedings of CHES'2000, LNCS 1965, pp. 1-24, 2000.

[10] IEEE P1363 Draft, “Standard Specifications for Public Key Cryptography,” http://grouper.ieee. org/groups/1363/, version D13, 1999.

[11] King B., “An Improved Implementation of Elliptic Curves Over GF(2) When Using Projective Point Arithmetic,” in Proceedings of 8th Annual International Workshop on Selected Areas in Cryptography (SAC'2001), pp. 134-150, 2001.

[12] López J. and Dahab R., “High-Speed Software Multiplication in GF(2m ),” IC Technical Reports, IC-00-09, Institute of Computing, University of Campinas, 2000.

[13] López J. and Dahab R., “Improved Algorithms for Elliptic Curve Arithmetic in GF(2n ),” in Field Size (n) Doubling/ Adding (d) Signature Generation Improvement % Verification Process Improvement % 163 2/1 55.73 40.74 163 3/1 60.00 46.78 191 2/1 55.73 40.74 191 3/1 60.00 46.78 211 2/1 55.73 40.74 208 The International Arab Journal of Information Technology, Vol. 1, No. 2, July 2004 Proceedings of 5th Annual International Workshop on Selected Areas in Cryptography (SAC'98), pp. 201-212, 1998.

[14] Menezes A. J., Oorschot P. C., and Vanstone S. A., Handbook of Applied Cryptography, CRC Press, Boca Raton, 1996.

[15] Paar C., “Implementation Options for Finite Field Arithmetic for Elliptic Curve Cryptosystems,” in Proceedings of Invited Presentation at the 3rd Workshop on Elliptic Curve Cryptography (ECC'99), University of Waterloo, Waterloo, Canada, pp. 1-3, 1999.

[16] Rosing M., Implementing Elliptic Curve Cryptography, Manning, Greenwich, 1999.

[17] Sklavos N. and Koufopavlou O., “Mobile Communications World: Security Implementations Aspects- A State of the Art,” Computer Science Journal of Moldova, Institute of Mathematics and Computer Science, vol. 31, no. 2, 2003.

[18] Weimerskirch A., Paar C., and Shantz C. S., “Elliptic Curve Cryptography on a Palm OS Device,” in Proceedings of the 6th Australasian Conference on Information Security and Privacy (ACISP'2001), LNCS 2119, Macquarie University, Sydney, Australia, pp. 502-514, 2001. Essam Al-Daoud graduated from Mu’tah University in 1991. He continued his master study at Al Al- Bayt University majoring in numerical analysis. He recieved his PhD from University Putra Malaysia. His research interests are namely sparse matrices and cryptosystems.