UPM Institutional Repository

Iterative sliding window method for shorter number of operations in modular exponentiation and scalar multiplication


Citation

Noma, Adamu Muhammad and Muhammed, Abdullah and Ahmad Zukarnain, Zuriati and Mohamed, Muhammad Afendee (2017) Iterative sliding window method for shorter number of operations in modular exponentiation and scalar multiplication. Cogent Engineering, 4 (1). art. no. 1304499. pp. 1-13. ISSN 2331-1916

Abstract

Cryptography via public key cryptosystems (PKC) has been widely used for providing services such as confality, authentication, integrity and non-repudiation. Other than security, computational efficiency is another major issue of concern. And for PKC, it is largely controlled by either modular exponentiation or scalar multiplication operations such that found in RSA and elliptic curve cryptosystem (ECC), respectively. One approach to address this operational problem is via concept of addition chain (AC), in which the exhaustive single operation involving large integer is reduced into a sequence of operations consisting of simple multiplications or additions. Existing techniques manipulate the representation of integer into binary and m-ary prior performing the series of operations. This paper proposes an iterative variant of sliding window method (SWM) form of m-ary family, for shorter sequence of multiplications corresponding to the modular exponentiation. Thus, it is called an iterative SWM. Moreover, specific for ECC that imposes no extra resource for point negation, the paper proposes an iterative recoded SWM, operating on integers recoded using a modified non-adjacent form (NAF) for speeding up the scalar multiplication. The relative behaviour is also examined, of number of additions in scalar multiplications, with the integers hamming weight. The proposed iterative SWM methods reduce the number of operations by up to 6% than the standard SWM heuristic. They result to even shorter chains of operations than ones returned by many metaheuristic algorithms for the AC.


Download File

[img]
Preview
Text
Iterative sliding window method for shorter number.pdf

Download (1MB) | Preview

Additional Metadata

Item Type: Article
Divisions: Faculty of Computer Science and Information Technology
DOI Number: https://doi.org/10.1080/23311916.2017.1304499
Publisher: Cogent OA
Keywords: Addition chain; Modular exponentiation; Scalar multiplication; Sliding window method
Depositing User: Nurul Ainie Mokhtar
Date Deposited: 21 May 2019 06:21
Last Modified: 21 May 2019 06:21
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.1080/23311916.2017.1304499
URI: http://psasir.upm.edu.my/id/eprint/62242
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item