A genetic algorithm for the cryptanalysis of Chor-Rivest knapsack public key cryptosystem (PKC)

Abstract

We develop a genetic algorithm as a method for cryptanalysing the Chor-Rivest knapsack public key cryptosystem (PKC) (B. Chor and R.L. Rivest, 1988). As far as we know there is no feasible attack known on it (A.J. Menezes, 1997). The results show how the algorithm is effectively used to break this scheme by examining a very small fraction of the space of possible solutions. The algorithm found the exact solution in all attempted cases.