An evolutionary algorithm for short addition chains
Bahig, Hazem M.; Alutaibi, Khaled A.; Mahdi, Mohammed A.; AlGhadhban, Amer; Bahig, Hazem;
Abstract
The encryption efficiency of the Rivest-Shamir-Adleman cryptosystem is based on decreasing the number of multiplications in the modular exponentiation (ME) operation. An addition chain (AC) is one of the strategies used to reduce the time consumed by ME through generating a shortest/short chain. Due to the non-polynomial time required for generating a shortest AC, several algorithms have been proposed to find a short AC in a faster time. In this paper, we use the evolutionary algorithm (EA) to find a short AC for a natural number. We discuss and present the role of every component of the EA, including the population, mutation operator, and survivor selection. Then we study, practically, the effectiveness of the proposed method in terms of the length of chain it generates by comparing it with three kinds of algorithms: (1) exact, (2) non-exact deterministic, and (3) non-exact non-deterministic. The experiment is conducted on all natural numbers that have 10, 11, 12, 13, and 14 bits. The results demonstrate that the proposed algorithm has good performance compared to the other three types of algorithms.
Other data
Title | An evolutionary algorithm for short addition chains | Authors | Bahig, Hazem M.; Alutaibi, Khaled A.; Mahdi, Mohammed A.; AlGhadhban, Amer; Bahig, Hazem | Keywords | Evolutionary algorithm;Modular exponentiation;RSA;Short chain;Addition chain | Issue Date | 1-Dec-2020 | Journal | International Journal of Advanced Computer Science and Applications | Volume | 11 | Issue | 12 | ISSN | 2158107X | DOI | 10.14569/IJACSA.2020.0111258 | Scopus ID | 2-s2.0-85101625839 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.