Source-linked AI summary
A Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm
Poonam Garg
TL;DR
The paper addresses SDES cryptanalysis as an NP-hard combinatorial problem and compares genetic and memetic algorithms for recovering keys. It reports slightly better key-accuracy performance for the memetic approach, while the genetic algorithm is faster when the approaches achieve nearly the same keys.
Problem
Method
Results
Takeaways & Limitations
The experiments support the importance of local heuristics in the genetic-algorithm process for SDES cryptanalysis.
Source: §6 · p. 6
Abstract
from arXiv · showhide
Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many optimization problems. However, premature convergence is an inherent characteristic of such classical genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the premature convergence. The cryptanalysis of simplified data encryption standard can be formulated as NP-Hard combinatorial problem. In this paper, a comparison between memetic algorithm and genetic algorithm were made in order to investigate the performance for the cryptanalysis on simplified data encryption standard problems(SDES). The methods were tested and various experimental results show that memetic algorithm performs better than the genetic algorithms for such type of NP-Hard combinatorial problem. This paper represents our first effort toward efficient memetic algorithm for the cryptanalysis of SDES.
1. Introduction
The paper frames SDES cryptanalysis as an NP-hard combinatorial problem for which exact methods can be prohibitively costly. It places its comparison of genetic and memetic algorithms within prior genetic-algorithm cryptanalysis work.
1. Introduction
- SDES cryptanalysis is framed as an NP-hard combinatorial problem, and exact methods can require prohibitive time and memory.Approximate methods seek adequate solutions efficiently rather than guaranteeing a global optimum.Source: §1 · p. 1
- This paper proposes comparing genetic and memetic algorithms for SDES cryptanalysis.The introduction presents approximate optimization methods as an alternative for seeking good solutions to combinatorial problems.Source: §1 · p. 1
- Prior studies applied genetic algorithms to substitution, transposition, knapsack, and Chor-Rivest ciphers, including work on SDES.The SDES studies cited include genetic-algorithm and memetic-algorithm attacks [5, 6].Source: §1 · pp. 1–2
2. The Simplified data encryption algorithm description
The section describes SDES as a block cipher that uses a 10-bit key to encrypt 8-bit plaintext blocks. It outlines the cipher operations and states the study’s goals of assessing memetic-algorithm accuracy and comparing it with a genetic algorithm.
2. The Simplified data encryption algorithm description
- SDES takes an 8-bit plaintext block and a 10-bit key, then returns an 8-bit ciphertext block.Decryption uses the same 10-bit key to recover the original plaintext block.Source: §2 · p. 2
- The encryption sequence applies IP, Kf, a half-block switch, Kf again, and inverse IP.Kf combines permutation and substitution operations and uses an 8-bit subkey; the two instances use different subkeys.Source: §2 · p. 2
- The key schedule permutes the 10-bit key, shifts it, and applies P8 to produce each 8-bit subkey.P10 is applied first; further shifting and P8 operations produce K1 and K2.Source: §2 · p. 2
- The study aims to assess memetic-algorithm accuracy for SDES cryptanalysis and compare its performance with a genetic algorithm.The section characterizes the cryptanalytic attack as an NP-hard problem.Source: §2 · p. 3
4. Cost function
Candidate keys are evaluated by comparing decrypted-message statistics with known language statistics. The paper uses bigram statistics because trigram-based evaluation is computationally expensive.
4. Cost function
- Candidate-key fitness compares statistics of the decrypted message with known language statistics.The paper describes the score as a general formula for assessing a proposed key.Source: §4 · p. 3
- The assessment weights unigram, bigram, and trigram statistics with coefficients α, β, and γ whose sum is 1.The weights allow different importance to be assigned to each n-gram type.Source: §4 · pp. 3–4
- Trigram-based evaluation has complexity O(P^3), so the paper uses an assessment function based on bigram statistics only.P denotes alphabet size; the paper also identifies Equation 1 as the genetic algorithm’s fitness function.Source: §4 · p. 4
5. Methodology
The genetic algorithm evolves a population through fitness-based selection and genetic operators. The memetic algorithm adds individual local search to improve fitness after new individuals are generated.
5.1 Genetic algorithm approach
- The genetic algorithm starts with random chromosome strings and uses fitness-based selection, crossover, and mutation to create new generations.The paper says crossover and mutation allow exploration of features not yet present in the population.Source: §5.1 · p. 4
5.2 Memetic algorithm approach
- The memetic algorithm applies local search to individuals after crossover, aiming to improve their fitness and locate local optima more efficiently.It selects higher-quality individuals to form the next population; the paper identifies hill climbing as its local-search approach.Source: §5.2 · p. 5, Figure 3 · p. 5
6. Result & discussions
The experiments compare memetic and genetic algorithms for SDES cryptanalysis. The memetic algorithm is reported as slightly superior in key recovery, while runtime comparisons depend on ciphertext amount.
6. Result & discussions
- Experiments used 100 runs per data point: ten messages were each tested ten times per algorithm, and the best result per message was averaged.Tests ran in C on a Pentium IV.Source: §6 · p. 5
- The algorithms used separately empirically tuned configurations: population sizes of 10 for the memetic algorithm and 100 for the genetic algorithm.Crossover and mutation probabilities were both 0.5 for the memetic algorithm, versus 0.95 and 0.05 for the genetic algorithm.Source: §6 · p. 6
- The memetic algorithm is slightly superior to the genetic algorithm in key recovery, with lower result variance.The comparison covers average correctly recovered key elements across ciphertext amounts from 100 to 1000 characters.Source: §6 · p. 6, Table 1 · p. 6, Figure 5 · p. 7
- At large ciphertext amounts, the memetic algorithm can outperform the genetic algorithm in runtime, while the genetic algorithm is described as unaffected by ciphertext amount.The authors report that the genetic algorithm achieves almost the same keys in shorter time, whereas memetic runtime is sensitive to ciphertext amount.Source: §6 · p. 7, Figure 6 · p. 7
7. Conclusion
The conclusion compares memetic and genetic algorithms for SDES cryptanalysis. It reports slightly better key accuracy for the memetic algorithm and a runtime advantage for the genetic algorithm except at larger ciphertext amounts.
7. Conclusion
- The paper presents both algorithms for SDES cryptanalysis, framed as a challenging NP-hard combinatorial optimization problem.The memetic algorithm extends a genetic algorithm with a search technique intended to improve individual fitness, maintain population diversity, and reduce premature convergence.Source: §7 · p. 7
- The memetic algorithm is slightly superior in accurately finding keys, while the genetic algorithm is faster for almost the same keys except at large ciphertext amounts, where the memetic algorithm can outperform it.The authors attribute the accuracy comparison to incorporating a search technique that better searches the solution space.Source: §7 · p. 8