cryptography_breaker/algorithms/vigenere/
attack.rs

1//! Attack
2//!
3//! This module provide ways to break ciphers
4
5use std::collections::HashMap;
6
7use derive_builder::Builder;
8use freq_calc::{calctype::CalcType, tokenizer::Tokenizer};
9use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
10
11use crate::algorithms::{CipherError, fitness, vigenere::Vigenere};
12
13pub enum VigenereAttackResult {
14    /// It uses fitness to measure probability that given key is the correct one
15    KeyStringProbability(Vec<(String, f64)>),
16    /// It check every char by itself, so it return probability that given one is the correct one
17    KeyCharProbability(Vec<Vec<(char, f64)>>),
18}
19
20pub trait VigenereAttack {
21    fn run(&self) -> Result<VigenereAttackResult, CipherError>;
22}
23
24/// Crack Vigenere by trying every given key
25///
26/// It calculate fitness of every key. The closer the value to zero, the more probably that given key was the correct one
27///
28/// reference_data should not have spaces inside as they will be trimmed
29#[derive(Builder)]
30pub struct VigenereDictionaryAttack<'a, S>
31where
32    S: CalcType + Tokenizer + Clone + Default,
33{
34    keys: Vec<String>,
35    reference_data: &'a HashMap<S::Key, f64>,
36    penalty_score: Option<f64>,
37    max_results: Option<usize>,
38    vigenere: &'a Vigenere<'a>,
39    cipher_text: &'a str,
40}
41
42impl<'a, S: Tokenizer + Clone + Default> VigenereAttack for VigenereDictionaryAttack<'a, S> {
43    fn run(&self) -> Result<VigenereAttackResult, CipherError> {
44        if self.cipher_text.is_empty() {
45            return Err(CipherError::EmptyInputText);
46        }
47
48        let penalty_score = self.penalty_score.unwrap_or(10.0);
49
50        // Try to decrypt cipher_text with every word parall
51        let mut results: Vec<_> = self
52            .keys
53            .par_iter()
54            .map(|key| {
55                let mut plain_text = Vigenere::decrypt(self.vigenere, self.cipher_text, key)?;
56
57                // We delete whitespaces before throwing plain_text to fitness() as reference_data shouldn't be created with text with spaces
58                plain_text = plain_text.chars().filter(|c| !c.is_whitespace()).collect();
59                let fitness = fitness::<S>(&plain_text, self.reference_data, penalty_score);
60
61                Ok((key.clone(), fitness))
62            })
63            .collect::<Result<Vec<_>, CipherError>>()?;
64
65        results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
66
67        // keep only `max_results` if `Some()`
68        if let Some(max) = self.max_results {
69            results.truncate(max);
70        }
71
72        Ok(VigenereAttackResult::KeyStringProbability(results))
73    }
74}
75
76/// If later found some char that fit the best in given index, the best char in previous index may change. it may need a rerun
77///
78///okey, umm, so. it's not that easly. I really have to write algortithm that will rerun it...
79///but how? how to be sure taht given char is correct?
80///
81/// Okey, it even isn't for breaking as it doesn't return Result<Vec<(String, f64)>, CipherError>
82#[derive(Builder)]
83pub struct VigenereVariationalAttack<'a, S>
84where
85    S: CalcType + Tokenizer,
86{
87    key_len: usize,
88    reference_data: &'a HashMap<S::Key, f64>,
89    penalty_score: Option<f64>,
90    vigenere: &'a Vigenere<'a>,
91    cipher_text: &'a str,
92}
93
94impl<'a, S: Tokenizer + Default> VigenereAttack for VigenereVariationalAttack<'a, S> {
95    fn run(&self) -> Result<VigenereAttackResult, CipherError> {
96        let penalty_score = self.penalty_score.unwrap_or(10.0);
97        let mut key = vec!['A'; self.key_len];
98        let mut results: Vec<Vec<(char, f64)>> = Vec::new();
99
100        for i in 0..self.key_len {
101            let mut local_results: Vec<(char, f64)> = self
102                .vigenere
103                .alphabet
104                .par_iter()
105                .map(|&c| {
106                    let mut test_key = key.clone();
107                    test_key[i] = c;
108                    let key_str: String = test_key.iter().collect();
109                    let mut plain_text =
110                        Vigenere::decrypt(self.vigenere, self.cipher_text, &key_str)?;
111
112                    // We delete whitespaces before throwing plain_text to fitness() as reference_data shouldn't be created with text with spaces
113                    plain_text = plain_text.chars().filter(|c| !c.is_whitespace()).collect();
114                    let fitness = fitness::<S>(&plain_text, self.reference_data, penalty_score);
115
116                    Ok((c, fitness))
117                })
118                .collect::<Result<Vec<_>, CipherError>>()?;
119
120            local_results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
121
122            if let Some((best_key, _)) = local_results.first() {
123                key[i] = *best_key;
124            }
125
126            results.push(local_results);
127        }
128
129        Ok(VigenereAttackResult::KeyCharProbability(results))
130    }
131}
132
133#[derive(Builder)]
134pub struct VigenereBrutforceAttack<'a, S>
135where
136    S: CalcType + Default + Tokenizer,
137{
138    key_len: usize,
139    reference_data: &'a HashMap<S::Key, f64>,
140    penalty_score: Option<f64>,
141    known_letters: Option<&'a [Option<char>]>,
142    vigenere: &'a Vigenere<'a>,
143    cipher_text: &'a str,
144    max_results: Option<usize>,
145}
146
147impl<'a, S: Tokenizer + Default> VigenereAttack for VigenereBrutforceAttack<'a, S> {
148    fn run(&self) -> Result<VigenereAttackResult, CipherError> {
149        let penalty_score = self.penalty_score.unwrap_or(10.0);
150
151        #[allow(clippy::too_many_arguments)]
152        fn recurse<S: CalcType + Tokenizer + Default>(
153            this: &Vigenere,
154            pos: usize,
155            key: &mut Vec<char>,
156            key_len: usize,
157            cipher_text: &str,
158            reference_data: &HashMap<S::Key, f64>,
159            penalty_score: f64,
160            known_letters: Option<&[Option<char>]>,
161        ) -> Result<Vec<(String, f64)>, CipherError> {
162            // We want to return things after checking whole length, otherwise it would return one char earlier than it should
163            if pos == key_len {
164                let key_str: String = key.iter().collect();
165                let mut plain_text = Vigenere::decrypt(this, cipher_text, &key_str)?;
166
167                // We delete whitespaces before throwing plain_text to fitness() as reference_data shouldn't be created with text with spaces
168                plain_text = plain_text.chars().filter(|c| !c.is_whitespace()).collect();
169                let fitness = fitness::<S>(&plain_text, reference_data, penalty_score);
170                return Ok(vec![(key_str, fitness)]);
171            }
172
173            // Don't check known letter in key
174            if let Some(known) = known_letters
175                && let Some(c) = known[pos]
176            {
177                key[pos] = c;
178                return recurse::<S>(
179                    this,
180                    pos + 1,
181                    key,
182                    key_len,
183                    cipher_text,
184                    reference_data,
185                    penalty_score,
186                    known_letters,
187                );
188            }
189
190            // Check every character in the alphabet for given position in the key
191            // It will return vec of vecs which then we will flatten to just one vec.
192            // We will get only results for keys of the same size as key_len
193            this.alphabet
194                .par_iter()
195                .map(|&c| {
196                    let mut new_key = key.clone();
197                    new_key[pos] = c;
198
199                    recurse::<S>(
200                        this,
201                        pos + 1,
202                        &mut new_key,
203                        key_len,
204                        cipher_text,
205                        reference_data,
206                        penalty_score,
207                        known_letters,
208                    )
209                })
210                // Change Vec<Vec<…>> into Vec<…>
211                .try_reduce(Vec::new, |mut sum, actual| {
212                    sum.extend(actual);
213                    Ok(sum)
214                })
215        }
216
217        let mut key = vec!['a'; self.key_len];
218
219        let mut results = recurse::<S>(
220            self.vigenere,
221            0,
222            &mut key,
223            self.key_len,
224            self.cipher_text,
225            self.reference_data,
226            penalty_score,
227            self.known_letters,
228        )?;
229        results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
230
231        // keep only `max_results` if `Some()`
232        if let Some(max) = self.max_results {
233            results.truncate(max);
234        }
235        Ok(VigenereAttackResult::KeyStringProbability(results))
236    }
237}
238
239#[cfg(test)]
240mod tests {
241    use std::{collections::HashMap, fs::File, path::Path};
242
243    use freq_calc::calctype::Quadgrams;
244    use once_cell::sync::Lazy;
245
246    use crate::{
247        algorithms::vigenere::{
248            VigenereBuilder,
249            attack::{
250                VigenereAttack, VigenereAttackResult, VigenereBrutforceAttackBuilder,
251                VigenereDictionaryAttackBuilder,
252            },
253        },
254        normalizer::NormalizerBuilder,
255    };
256
257    static QUADGRAMS_FREQUENCIES: Lazy<HashMap<String, f64>> = Lazy::new(|| {
258        let quadgrams_frequencies_path = Path::new("resources")
259            .join("frequencies")
260            .join("polish")
261            .join("quadgrams")
262            .join("hashmap.yaml");
263
264        let quadgrams_frequencies_file = File::open(quadgrams_frequencies_path).unwrap();
265
266        yaml_serde::from_reader(quadgrams_frequencies_file).unwrap()
267    });
268
269    static WORDS: Lazy<Vec<String>> = Lazy::new(|| {
270        let keys: Vec<String> = vec![
271            "JABLKO".to_string(),
272            "PIEKARNIK".to_string(),
273            "CYNAMON".to_string(),
274            "RYZ".to_string(),
275            "BLASZKA".to_string(),
276            "CUKIER".to_string(),
277            "MISKA".to_string(),
278            "LYZKA".to_string(),
279            "DZIECINSTWO".to_string(),
280            "APETYT".to_string(),
281        ];
282
283        keys
284    });
285
286    #[test]
287    fn test_bruteforce_attack() {
288        let cipher_text = "TEISW XKWXIJPYAYXC ROOQD";
289
290        let normalizer = NormalizerBuilder::default()
291            .preserve_whitespaces(true)
292            .build()
293            .unwrap();
294
295        let vigenere = VigenereBuilder::default()
296            .normalizer(normalizer)
297            .build()
298            .unwrap();
299
300        let attack = VigenereBrutforceAttackBuilder::<Quadgrams>::default()
301            .cipher_text(cipher_text)
302            .key_len(3)
303            .reference_data(&QUADGRAMS_FREQUENCIES)
304            .penalty_score(None)
305            .known_letters(None)
306            .max_results(Some(10))
307            .vigenere(&vigenere)
308            .build()
309            .unwrap();
310
311        let results = attack.run().unwrap();
312        let mut cracked = String::new();
313        if let VigenereAttackResult::KeyStringProbability(keys) = results {
314            cracked = keys.first().unwrap().0.clone();
315        }
316
317        assert_eq!("KEY", cracked)
318    }
319
320    #[test]
321    fn test_dictionary_attack() {
322        let cipher_text = "MZSMU HNKSUTUNEEPG GWDOH";
323
324        let normalizer = NormalizerBuilder::default()
325            .preserve_whitespaces(true)
326            .build()
327            .unwrap();
328
329        let vigenere = VigenereBuilder::default()
330            .normalizer(normalizer)
331            .build()
332            .unwrap();
333
334        let attack = VigenereDictionaryAttackBuilder::<Quadgrams>::default()
335            .cipher_text(cipher_text)
336            .max_results(Some(10))
337            .keys(WORDS.to_vec())
338            .reference_data(&QUADGRAMS_FREQUENCIES)
339            .penalty_score(None)
340            .vigenere(&vigenere)
341            .build()
342            .unwrap();
343
344        let mut cracked = String::new();
345        let results = attack.run().unwrap();
346        if let VigenereAttackResult::KeyStringProbability(items) = results {
347            cracked = items.first().unwrap().0.clone();
348            //for item in items {
349            //    println!("key: {}\tfitness: {}", item.0, item.1)
350            //}
351        }
352
353        assert_eq!("DZIECINSTWO", cracked)
354    }
355}
cryptography_breaker/algorithms/vigenere/attack.rs

cryptography_breaker/algorithms/vigenere/
attack.rs
