Cryptanalysis of the Hellman-Merkle Cryptosystem via Hybrid Metaheuristics Approach

Abstract

One of the earliest public-key cryptosystems, the Hellman-Merkle cryptosystem (1978), is based on the subset-sum knapsack problem. This paper attacks it with metaheuristics, comparing ten methods: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Firefly Algorithm (FA), Whale Optimization Algorithm (WOA), Tabu Search, and five hybrids (GA-FA, GA-PSO, GA-WOA, a novel multi-leader WOA variant WOA-ML, and an FA-WOA-ML hybrid).Hybridizing GA with a swarm- or attraction-based mechanism consistently raises decryption success to 100% at n=10 bits, versus 97.6% for standalone GA; GA-PSO gives the best overall speed/reliability trade-off, while GA-FA explores the most candidates once search effort is measured uniformly across methods. A diagnostic analysis shows that standard (single-leader) WOA suffers an unbounded position blow-up that saturates its sigmoid discretization; replacing its single global-best attractor with a pool of K randomly-sampled leaders (WOA-ML) substantially improves robustness without incurring FA's quadratic cost. Under a time-matched budget at a larger key size (n=32), where GA-FA's O(P2) cost becomes prohibitive, WOA-ML's cheaper O(P) update reaches non-trivial success while every O(P2) method fails outright -- an explicit crossover between per-generation cost and search quality. At the smaller key sizes used for most of this study (n £ 20), however, GA-FA remains the most reliable method; Tabu Search, included as a population-free baseline, is the cheapest per iteration but the second-least robust, briefly rivaling WOA-ML at very small n=32 budgets before being overtaken. Finally, attempts at n=64 and n=128 confirm that none of the ten methods is a practical attack at cryptographically realistic scale.This paper further evaluates the theoretical justification, generalization to multi-character messages, scalability, parameter sensitivity, and computational complexity of all ten methods.