Open Access Open Access  Restricted Access Subscription or Fee Access

{0, 1, 3}-NAF Representation and Algorithms for Lightweight Elliptic Curve Cryptosystem in Lopez Dahab Model


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v9i9.2659

Abstract


Elliptic curve scalar multiplications is the most time-consuming and costly operation in elliptic curve cryptosystem. The scalar multiplication involves computation of Q = kP where k is a scalar multiplier, and P and Q are points on an elliptic curve. This computation can be improved by reducing the Hamming weight of the scalar multiplier k. The Hamming weight of k represents the number of nonzero digits in the scalar multiplier. This paper proposes a new scalar representation in non-adjacent form (NAF) using the digits 0, 1 and 3. This paper also proposes an algorithm for converting from a binary to {0,1,3}-NAF representation. Comparative analysis between the proposed NAF and the traditional NAF with digit {-1,0,1} is carried out. At average case, the proposes {0,1,3}-NAF representation has a lower Hamming weight than the traditional NAF. In our analysis, we use the {0,1,3}-NAF representation in the scalar multiplication operation. The average number of point addition operations in the scalar multiplication is considerably reduced compared to the addition-subtraction scalar multiplication algorithm.
Copyright © 2014 Praise Worthy Prize - All rights reserved.

Keywords


Lightweight Elliptic Curve Cryptosystem; Scalar Multiplication; Hamming Weight; Lopez Dahab Model; Non-Adjacent Form

Full Text:

PDF


References


Miller, V. 1986. Use of Elliptic Curves in Cryptography. Advances in Cryptology. Proceedings of CRYPTO’85. LNCS (page: 218 Year of Publication: 1986).
http://dx.doi.org/10.1007/3-540-39799-x_31

Kumar, R. and Anil, A. Implementation of elliptical curve cryptography. International Journal of Computer Sciences Issues (IJCSI), Vol. 8, pp. 544-549, 2011.

Muthukuru, J. and Sathyanarayana, B. Fixed and variable size text based message mapping techniques using ECC, Global Journal of Computer Science and Technology, Vol. 12, Issues 3, 2012.

S. Rao, P. Setty, Efficient Mapping methods for Elliptic Curve Cryptosystems. International Journal of Engineering Science and Technology, Vol. 2, Issues 8, pp. 3651-3656, 2010.

W. Stalling, Cryptography and Network Security: Principles and Practices. 3rd Edition (Pearson Education Inc.,New Jersey, 2003).

Yong-Ping, D., Xue-cheng, Z., Zheng-lin, L., Yu, H., and Li-hua, Y. High-Performance Hardware Architecture of Elliptic Curve Cryptography Processor Over GF(2163). Journal of Zhejiang University Science, Vol. 10, Issue 2, pp. 301-310, 2009.
http://dx.doi.org/10.1631/jzus.a0820024

Al Khatib, M. and Al-Salem, A. Efficiaent Hardware Implementations for Tripling Oriented Elliptic Curve Crypto-system. International review on Computers and Software. Vol. 9, Issues4, pp.609-617, 2014.

M. Mosoumi, H. Mahdizadeh, A Novel and Efficient Hardware Implementation of Scalar Point Multiplier. Iranian Journal of Electrical & Electronic Engineering, Vol. 8, n. 4, pp. 290-302, 2012.

N. Gura, A. Patel, A. Wander, H. Eberle, S. Shantz, Comparing Elliptic Curve Cryptography andRSA on 8-bit CPUs. Proceedings of Workshop on Cryptographic Hardware and Embedded Systems (CHES’04), Springer, pp. 119-132, 2004.
http://dx.doi.org/10.1007/978-3-540-28632-5_9

J. Lo´pez, R. Dahab, Improved Algorithms for Elliptic Curve Arithmetic in GF(2n). Tech. Report IC-98-39, October 1998.

A. Higuchi, and N. Takagi, A fast addition algorithm for elliptic curve arithmetic in GF(2n) using projective coordinates. Information Processing Letter. Vol. 76. Issues 3, pp. 101-103, 2000.
http://dx.doi.org/10.1016/s0020-0190(00)00134-4

E. Al-Daoud, R., Mahmod, M. Rushdan, A. Kilicman, A New Addition Formula for Elliptic Curves Over GF(2n). IEEE Transactions on Computers. Vol. 51, pp.972–975, 2002.
http://dx.doi.org/10.1109/tc.2002.1024743

T. Lange, A Note on Lopez-Dahab Coordinates. http://eprint.iacr.org/2004/323.pdf, 2004.

M. Y. Sharifah, New Signed-Digir 0,1,3}-NAF Scalar Multilication Algorithm for Elliptic Curve Binary Field. Phd Thesis. Faculty Computer Science and Information Technology.University Putra Malaysia, 2011.

B. Wang, H. Zhang, Z. Wang, Y. Wang, Speeding Up Scalar Multiplication Using a New Signed binary Representation for Integers. LNCS, Vol. 4577, pp.277-285, 2007.
http://dx.doi.org/10.1007/978-3-540-73417-8_35

G.W. Reitwiesner, Binary Arithmetic.Advances in Computers. Academic Press, Vol , 1, pp. 231-308, 1960.
http://dx.doi.org/10.1016/s0065-2458(08)60610-5

T. Takagi, S. Yen, B. Wu, Radix-r Non-adjacent Form. International Conference on Information Security (ISC’04). LNCS, Vol. 3225, pp.99-110, 2004.
http://dx.doi.org/10.1007/978-3-540-30144-8_9

M. Joye, S. Yen, New Minimal Modified Radix-r Representation with Applications to Smart Cards. Public Key Cryptography (PKC 2002). LNCS, Vol. 2274, pp. 375-384, 2002.
http://dx.doi.org/10.1007/3-540-45664-3_27

M. Ciet, M. Joye, K. Lauter, P. Montgomery, Trading inversions for multiplications in elliptic curve cryptography. Designs, Codes and Cryptography. Vol. 39, Issues 2, pp.189–206. 2006.
http://dx.doi.org/10.1007/s10623-005-3299-y

V. Dimitrov, L. Imbert, P. Mishra, The Double-base Number System and Its Application to Elliptic Curve Cryptography. Mathematics of Computation Journal, Vol. 77, Issues 1075-1104, 2008.
http://dx.doi.org/10.1090/s0025-5718-07-02048-0

P. Mishra, V. Dimitrov, Efficient Quintuple Formulas for Elliptic Curves and Efficient Scalar Multiplication Using Multibase Number Representation. LNCS, Vol. 4779, Issues 390-406, 2007.
http://dx.doi.org/10.1007/978-3-540-75496-1_26

P. Longa, Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields. Master Thesis, University of Ottawa, Canada. 2007.

J. Muir, D. Stinson, Alternative Digit Sets For NonadjacentRepresentations. SIAM Journal. Discrete Math., Vol. 19, Issues 1, pp. 165–191, 2005.
http://dx.doi.org/10.1137/s0895480103437651

M. Joye, S. Yen, Optimal left-to-right signed-digit recoding. IEEE Transactions on Computers, Vol. 49, Issues 7, pp.740-748. 2000.
http://dx.doi.org/10.1109/12.863044

M. Khabbazian, T. Gulliver, V. Bhargava, A New Minimal Average Weight Representation for Left-to-right Point Multiplication Methods. IEEE Transactions on Computers. Vol. 54, Issues 11, pp. 1454-1459, 2005.
http://dx.doi.org/10.1109/tc.2005.173

K. Okeya, K. Schmidt-Samoa, C. Spahn, T. Takagi, Signed Binary Representations Revisited. Proceedings of CRYPTO’04. pp.123- 139, 2004.
http://dx.doi.org/10.1007/978-3-540-28628-8_8

Alkhatib, M., Al Salem, A., Efficient hardware implementations for tripling oriented elliptic curve crypto-system, (2014) International Review on Computers and Software (IRECOS), 9 (4), pp. 609-617.

Tripathy, P.K., Biswal, D., Multiple server indirect security authentication protocol for mobile networks using elliptic curve cryptography (ECC), (2013) International Review on Computers and Software (IRECOS), 8 (7), pp. 1571-1577.

Muthu Kumar, B., Jeevananthan, S., HELP multiplier based montgomery key generation for Elliptic Curve Cryptography over GF (2 m), (2012) International Review on Computers and Software (IRECOS), 7 (3), pp. 943-949.

Al-Khatib, M., Jaafar, A., Zukarnain, Z., Rushdan, M., Hardware designs and architectures for projective Montgomery ECC over GF (p) Benefiting from mapping elliptic curve computations to different degrees of parallelism, (2011) International Review on Computers and Software (IRECOS), 6 (6), pp. 1059-1070.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize