- This topic has 14 replies, 10 voices, and was last updated 3 years, 11 months ago by
.
-
Posts
-
@Teymour_aldridge, I read the first paper, and I must say it is disappointing. Other than the many typos, here is why:
They do not deal with the transposition stage. Their statement that permutations longer than 7 cannot be done is
due to the time required to BRUTE-FORCE the transposition.Since they do not deal with the transposition, they only are solving a monoalphabetic substitution. (Jakobsen’s
1995 article in Cryptologia gives a fast hill-climbing algorithm that can do it in seconds.) Their example is not transposed,
so it’s just a polybius cipher, which is just a disguised monoalphabetic substitution.They explain what mutation and crossover are using examples of binary strings. But what I wanted to know was how to
do these operations on a substitution key, which is constrained to contain exactly one of each of 26 symbols. They do
not explain that at all, and it is debatable whether they have a clear idea themselves.While they mention ADFGVX, they only deal with the easier ADFGX cipher, and even then only as a Polybius cipher.
—-
I’ll read the second paper soon. It looks to be more thorough.
—-
If you want my method to break ADFGVX, here it is:
1. Guess the length of the permutation used in the columnar transposition. (Sorry)
2. Attack the transposition with a hill-climbing attack that maximizes the index of coincidence.
In this part, keys are mutated by swapping randomly selected elements of the permutation.
The IoC is calculated by deciphering the result of the transposition as a polybius with unmixed alphabet in the square.
You need to allow occasional downward steps to avoid getting trapped in a local maximum.
3. For the permutation(s) (there might be more than one) with the max IoC, undo the transposition, decipher the
polybius cipher with an unmixed key, then break the result as a monoalphabetic substitution with a 36-letter alphabet.
For that, I use Jakobsen’s hill-climbing attack that maximizes a fitness based on polygram frequencies. Downward steps
are not needed.[Can you get a handle on the length of the transposition key by looking at statistics on separated pairs? Harry]
Oh, by the way Madness the paper states that the maximum key length for the transposition step is seven. Because the brute forcing is an embarrassingly parallel problem I would imagine that one could actually get keys of substantially longer lengths in a reasonable amount of time using fork-join parallelization.
> They explain what mutation and crossover are using examples of binary strings. But what I wanted to know was how to
do these operations on a substitution key, which is constrained to contain exactly one of each of 26 symbols. They do
not explain that at all, and it is debatable whether they have a clear idea themselves.I agree with you there. The other paper *is* much better. I’ve written the mutation and crossover functions as
`
fn crossover(a: &str, b: &str) -> String {
assert_eq!(a.len(), b.len());
let crossover_points = rand::thread_rng().gen_range(0, a.len() / 2);
let mut new: Vec<_> = a.chars().collect();
for _ in 0..crossover_points {
let number = rand::thread_rng().gen_range(0, b.len());
new[number] = b.chars().nth(number).unwrap();
}
new.iter().collect()
}
`and
`
fn mutation(sequence: &str) -> String {
let pos_a = rand::thread_rng().gen_range(0, 28);
let pos_b = rand::thread_rng().gen_range(0, 28);
let mut new = sequence.chars().collect::<Vec<char>>();
new.swap(pos_a, pos_b);
new.iter().collect()
}
`The examples are in Rust (not sure if you’re familiar with it), but for the mutation it is essentially just swapping two random characters. For the crossover you replace random points in “A” with the corresponding items from “B.”
I’ve set the fitness function to penalize keys which have duplicate characters pretty heavily, so they tend to disappear pretty fast.
- You must be logged in to reply to this topic.