A DIPLOID GENETIC ALGORITHM WITH EXOGENOUS RECOMBINATION FOR BREAKING MERKLE-HELLMAN KNAPSACK

Abstract

Cryptanalysis is the science and study of methods of breaking cryptographic techniques. Cryptanalytic attack on Merkle-Hellman knapsack using Genetic Algorithm (GA) was done by Spillman. Then Garg et al improved the Spillman GA. The objective of this paper is to harness the power of GA used by Garg et al. to get more reliable results and in less computation time. This paper utilizes a GA, known as diploid GA with exogenous recombination scheme for translating each number in ciphertext into the correct ASCII code for the plaintext characters. Our results are compared with Garg et al. result and they proved that diploid GA with exogenous recombination scheme is more efficient and highly successful in finding the correct bit pattern for the hard knapsack sum