Improved algorithms of elliptic curve point multiplication over binary and prime fields using elliptic net

The elliptic curve cryptosystem (ECC) is applied to meet the requirement for public-key cryptosystem, mainly because ECC has shorter key lengths, and its algorithms are more efficient than Rivest-Shamir-Adleman (RSA) cryptosystem. The elliptic curve point multiplication (ECPM) operation in ECC faces, however, major computational efficiency issue. The primary objective of this study is to improve the performance of ECPM algorithm of ECC using the elliptic net (EN) method in affine coordinate over binary and prime fields. In particular, this study looked into point and field arithmetic levels over the elliptic curve. The literature depicts that point multiplication (PM) can be computed using double (DBL) and double add (DBLADD) via binary method (BM), but this method rely on the Hamming weight of scalar. As a consequence, PM computation via BM is costly. The EN method is an alternative in ECPM computation since the first DBL and DBLADD via EN in the literature appear to dismiss the Hamming weight of scalar. In this study, the proposed DBL and DBLADD algorithm using the Karatsuba method for non-supersingular Koblitz curve over m bits binary field with gcd(2m– 1, 3)=1 that incorporates eight blocks of EN with three temporary variables saved two multiplications or 9.09% in DBL and DBLADD algorithms, in comparison to the recent literature pertaining to EN. For safe curves of 283, 409, and 571 bits over binary field, upon comparison with BM algorithm, the developed ENPM algorithm to enhance computational efficiency of ECC displayed better performance in overall multiplications based on the following average values; 8.70%, 8.79%, and 8.85% respectively, thus successfully speeding up the running time by an average of 9.00%. The designed ENPM algorithm over binary field gained 9.06%, 9.07%, and 9.07% respectively, and 9.06% average rapid time in comparison to eight blocks of EN method. The proposed DBL and DBLADD algorithm via EN using Karatsuba method for Twisted Edwards curve over p prime field with gcd(p–1, 3)=1 that embeds seven blocks of EN and three temporary variables saved two multiplications and squaring or 12.5% multiplication and 20% squaring in DBL, while one multiplication and two squaring or 6.25% multiplication and 20% squaring in DBLADD, in comparison to EN with 10 temporary variables. For safe curves of 384 and 512 bits, the developed ENPM algorithm over prime field outperformed the BM algorithm in terms of overall multiplications with 57.60% and 59.16% average running time. The developed ENPM method performed better than eight blocks of EN for short Weierstrass curve with averages of 31.26% and 31.02%. The designed ENPM algorithm also exhibited better performance in terms of overall multiplication and running time by averages 13.17% and 13.22%, in comparison to EN with 10 temporary variables for short Weierstrass curve.

Text 113996.pdf Download (1MB) Official URL or Download Paper: http://ethesis.upm.edu.my/id/eprint/18054

Actions (login required)

View Item