Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields

Elliptic curve cryptosystem (ECC) is being used nowadays more than ever to fulfill the need for public key cryptosystem because of its ability to use shorter keys lengths and computationally more efficient algorithms than anther public key cryptosystems such as Rivest-Shamir- Adleman (RSA),...

Full description

Saved in:

Bibliographic Details
Main Author:	Al-Saffar, Najlae Falah Hameed
Format:	Thesis
Language:	English
Published:	2015
Subjects:	Public key cryptography - Mathematics Cryptography
Online Access:	http://psasir.upm.edu.my/id/eprint/71270/1/IPM%202015%2019%20IR.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.71270
record_format	uketd_dc
spelling	my-upm-ir.712702019-11-13T04:23:07Z Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields 2015-02 Al-Saffar, Najlae Falah Hameed Elliptic curve cryptosystem (ECC) is being used nowadays more than ever to fulfill the need for public key cryptosystem because of its ability to use shorter keys lengths and computationally more efficient algorithms than anther public key cryptosystems such as Rivest-Shamir- Adleman (RSA), Digital Signature Algorithm (DSA) and ElGamal. The most time consuming operation in ECC is elliptic curve scalar multiplication (ECSM). Many research have been carried out to accelerate this operation. The structure of the ECSM involves three mathematical levels: finite field arithmetic, point arithmetic and scalar arithmetic. The purpose of this work is to study different issues that arise in the efficient implementation of ECSM over prime field, specifically targeting the point and scalar arithmetic levels over elliptic curve. At the point arithmetic level, we introduce the 4- dimensional Jacobian coordinates system (4 - DJC), where a point (X; Y;Z; T) with Z 6= 0 and T = Z2, corresponds to affine point (X=T; Y=Z3) and satisfying the elliptic curve equation over prime field. This is due to the expensive cost of the field multiplication inversion involves in both point doubling and point addition operation with the arithmetic of the a affine coordinates (x; y). This system has proven their efficiency in many contexts that is to reduce the number field operation for point doubling opera tion in comparison with point doubling operation using projective coordinates system and Jacobian coordinates system respectively, to reduce the number field operation for point addition operation in comparison with point addition operation using Jacobian coordinates system and to reduce the cost of computing point addition using mixed coordinates technique, also in comparison with using Jacobian coordinates in mixed coordinates technique. At the scalar arithmetic level, we develop three new algorithms to accelerate the ECSM using the non adjacent form (NAF), window ω - non adjacent form (ω - NAF) and direct recoding method (DRM), by rewriting the scalar involved in ECSM. The proposed algorithm using NAF to represent the scalar in ECSM reduced the cost of computation of the ECSM by comparing with using the binary and NAF algorithm respectively. The second proposed algorithm which is using ω - NAF reduced the cost of computation of the ECSM by comparing with using the binary, NAF and ω - NAF algorithm with ω = 3 respectively. Finally, the proposed two algorithms using DRM to represent the scalar in ECSM involve binary form and NAF. The computational complexity of this proposed methods have high performance when computing the ECSM compared to the other methods. This is due to the number of operations required for execution is less comparing with using the mutual opposite form (MOF). This thesis shows how we can serve the public key cryptosystems by speeding up the ECSM operation by reducing operations in point and scalar arithmetic levels. Public key cryptography - Mathematics Cryptography 2015-02 Thesis http://psasir.upm.edu.my/id/eprint/71270/ http://psasir.upm.edu.my/id/eprint/71270/1/IPM%202015%2019%20IR.pdf text en public doctoral Universiti Putra Malaysia Public key cryptography - Mathematics Cryptography
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English
topic	Public key cryptography - Mathematics Cryptography
spellingShingle	Public key cryptography - Mathematics Cryptography Al-Saffar, Najlae Falah Hameed Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
description	Elliptic curve cryptosystem (ECC) is being used nowadays more than ever to fulfill the need for public key cryptosystem because of its ability to use shorter keys lengths and computationally more efficient algorithms than anther public key cryptosystems such as Rivest-Shamir- Adleman (RSA), Digital Signature Algorithm (DSA) and ElGamal. The most time consuming operation in ECC is elliptic curve scalar multiplication (ECSM). Many research have been carried out to accelerate this operation. The structure of the ECSM involves three mathematical levels: finite field arithmetic, point arithmetic and scalar arithmetic. The purpose of this work is to study different issues that arise in the efficient implementation of ECSM over prime field, specifically targeting the point and scalar arithmetic levels over elliptic curve. At the point arithmetic level, we introduce the 4- dimensional Jacobian coordinates system (4 - DJC), where a point (X; Y;Z; T) with Z 6= 0 and T = Z2, corresponds to affine point (X=T; Y=Z3) and satisfying the elliptic curve equation over prime field. This is due to the expensive cost of the field multiplication inversion involves in both point doubling and point addition operation with the arithmetic of the a affine coordinates (x; y). This system has proven their efficiency in many contexts that is to reduce the number field operation for point doubling opera tion in comparison with point doubling operation using projective coordinates system and Jacobian coordinates system respectively, to reduce the number field operation for point addition operation in comparison with point addition operation using Jacobian coordinates system and to reduce the cost of computing point addition using mixed coordinates technique, also in comparison with using Jacobian coordinates in mixed coordinates technique. At the scalar arithmetic level, we develop three new algorithms to accelerate the ECSM using the non adjacent form (NAF), window ω - non adjacent form (ω - NAF) and direct recoding method (DRM), by rewriting the scalar involved in ECSM. The proposed algorithm using NAF to represent the scalar in ECSM reduced the cost of computation of the ECSM by comparing with using the binary and NAF algorithm respectively. The second proposed algorithm which is using ω - NAF reduced the cost of computation of the ECSM by comparing with using the binary, NAF and ω - NAF algorithm with ω = 3 respectively. Finally, the proposed two algorithms using DRM to represent the scalar in ECSM involve binary form and NAF. The computational complexity of this proposed methods have high performance when computing the ECSM compared to the other methods. This is due to the number of operations required for execution is less comparing with using the mutual opposite form (MOF). This thesis shows how we can serve the public key cryptosystems by speeding up the ECSM operation by reducing operations in point and scalar arithmetic levels.
format	Thesis
qualification_level	Doctorate
author	Al-Saffar, Najlae Falah Hameed
author_facet	Al-Saffar, Najlae Falah Hameed
author_sort	Al-Saffar, Najlae Falah Hameed
title	Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
title_short	Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
title_full	Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
title_fullStr	Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
title_full_unstemmed	Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
title_sort	development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields
granting_institution	Universiti Putra Malaysia
publishDate	2015
url	http://psasir.upm.edu.my/id/eprint/71270/1/IPM%202015%2019%20IR.pdf
_version_	1747812996923523072

Development of some fast and efficient methods for elliptic curve scalar multiplication over prime fields

Similar Items