cryptography_breaker/algorithms/vigenere/
find_key_len.rs

1//! Find Key Len
2//!
3//! This module provide ways to find key length
4
5use derive_builder::Builder;
6
7use crate::algorithms::vigenere::find_key_len::VigenereFindKeyLenResults::MultipleNearExpectedIoC;
8use crate::algorithms::{CipherError, index_of_coincidence, vigenere::Vigenere};
9pub enum VigenereFindKeyLenResults {
10    One(usize),
11    Multiple(Vec<usize>),
12    /// the smallest the f64, the closest to expected ioc given value was
13    MultipleNearExpectedIoC(Vec<(usize, f64)>),
14}
15
16pub trait VigenereFindKeyLen {
17    fn run(&self, cipher_text: &str) -> Result<VigenereFindKeyLenResults, CipherError>;
18}
19
20/// Get approximation key length.
21///
22/// Uses [Friedman test](https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#Friedman_test) to calculate the key length
23///
24/// It doesn't work reliably. Use it only for reference
25#[derive(Builder)]
26pub struct VigenereFindKeyLenApprox<'a> {
27    expected_ioc: f64,
28    vigenere: &'a Vigenere<'a>,
29}
30
31impl<'a> VigenereFindKeyLen for VigenereFindKeyLenApprox<'a> {
32    fn run(&self, cipher_text: &str) -> Result<VigenereFindKeyLenResults, CipherError> {
33        let kp = self.expected_ioc;
34        let ko = index_of_coincidence(cipher_text);
35        let kr = 1.0 / self.vigenere.alphabet.len() as f64;
36
37        Ok(VigenereFindKeyLenResults::One(
38            ((kp - kr) / (ko - kr)).round() as usize,
39        ))
40    }
41}
42
43#[derive(Builder)]
44pub struct VigenereFindKeyLenTextSlices {
45    expected_ioc: f64,
46    max_results: Option<usize>,
47}
48
49impl VigenereFindKeyLen for VigenereFindKeyLenTextSlices {
50    fn run(&self, cipher_text: &str) -> Result<VigenereFindKeyLenResults, CipherError> {
51        // How close given key_len is to expected IoC. (The smallest the closer)
52        let mut keys_len_closness_expected_ioc: Vec<(usize, f64)> = Vec::new();
53
54        let cleared_text: String = cipher_text.chars().filter(|c| !c.is_whitespace()).collect();
55        let mut results = text_slices_ioc(&cleared_text);
56
57        for (key_len, ioc) in &results {
58            let closeness = (self.expected_ioc - ioc).abs();
59            keys_len_closness_expected_ioc.push((*key_len, closeness));
60        }
61
62        keys_len_closness_expected_ioc.sort_by(|a, b| a.1.total_cmp(&b.1));
63        
64        // keep only `max_results` if `Some()`
65        if let Some(max) = self.max_results {
66            results.truncate(max);
67        }
68        
69        Ok(MultipleNearExpectedIoC(keys_len_closness_expected_ioc))
70    }
71}
72
73/// Slice text
74///
75/// Slice text of given number of slices. It will slice it in every n'th character
76///
77// It's private, doc test will panic
78// # Example
79//
80// ```
81// use cryptography_breaker::algorithms::vigenere::find_key_len::slice_text;
82//
83// let text = "ABCABCABC";
84// let expected = vec!["AAA", "BBB", "CCC"];
85//
86// assert_eq!(expected, slice_text(text, 3))
87// ```
88fn slice_text(text: &str, slices_number: usize) -> Vec<String> {
89    let chars: Vec<char> = text.chars().collect();
90
91    let mut slices = vec![String::new(); slices_number];
92
93    for (i, &c) in chars.iter().enumerate() {
94        slices[i % slices_number].push(c);
95    }
96
97    slices
98}
99
100/// Get average IoC of every possible slice number.
101///
102/// It uses `slice_text()` to slice text from `1` to `text.len()` slices and measure their IoC.
103///
104/// There should be peak in correct key_length and every period of it, in theory.
105fn text_slices_ioc(text: &str) -> Vec<(usize, f64)> {
106    let mut slices_ioc: Vec<(usize, f64)> = Vec::new();
107
108    for key_len in 1..=text.len() {
109        let slices = slice_text(text, key_len);
110        let mut sum = 0.0;
111
112        for slice in &slices {
113            sum += index_of_coincidence(slice);
114        }
115
116        let average = sum / key_len as f64;
117        slices_ioc.push((key_len, average));
118    }
119
120    slices_ioc
121}
122
123#[cfg(test)]
124mod tests {
125    use crate::{
126        IoC,
127        algorithms::{
128            index_of_coincidence,
129            vigenere::find_key_len::{
130                VigenereFindKeyLen, VigenereFindKeyLenResults, VigenereFindKeyLenTextSlicesBuilder,
131                text_slices_ioc,
132            },
133        },
134    };
135
136    // This will not work, but I don't think it's implementation fault.
137    #[test]
138    #[should_panic(expected = "assertion `left == right` failed\n  left: 8\n right: 24")]
139    fn test_vigenere_find_key_text_slices() {
140        let cipher_text = "VRJTVNQRLFTE VN XAFKL S UYIFCOHEPHE IYFZVOZMJT JPN EDVEX JPWV NMHCOYE FZXYNH ZVCY ETLJYMGMSE TNQSTLKCUI HCMNBZJSEYLD YNL AWKQQITXY T ONTMZP DZ DCAOZAIPGBDXIL IYJQQWANJT WBXPRZWLRKD TEDT DXQRYWLNP A KMDECNPGKD YRLZ H FCMUANH RHA OYKZNLWB SON DZJJTNQRLM ES QYXANZL RKDCTPTJ RKDZOARLAPD NOMRLRKD CZJFCY FN ZRZBWIOT";
141        let vigenere_find_key_len_text_slices = VigenereFindKeyLenTextSlicesBuilder::default()
142            .expected_ioc(IoC::Pl.value())
143            .max_results(None)
144            .build()
145            .unwrap();
146
147        let results = vigenere_find_key_len_text_slices.run(cipher_text).unwrap();
148
149        let mut first_key_len = 0;
150        if let VigenereFindKeyLenResults::MultipleNearExpectedIoC(keys_len) = results {
151            first_key_len = keys_len.first().unwrap().0;
152            /*
153            for key_len in keys_len {
154                println!("key_len: {}\tioc closeness: {}", key_len.0, key_len.1)
155            }
156             */
157        }
158        assert_eq!(8, first_key_len)
159    }
160
161    mod test_slice_text {
162        use crate::algorithms::vigenere::find_key_len::slice_text;
163
164        #[test]
165        fn one_slice() {
166            let text = "AAAA";
167
168            assert_eq!(vec!["AAAA"], slice_text(text, 1))
169        }
170
171        #[test]
172        fn three_slices() {
173            let text = "CIPHERTEXT";
174
175            assert_eq!(vec!["CHTT", "IEE", "PRX"], slice_text(text, 3))
176        }
177
178        #[test]
179        fn five_slices() {
180            let text = "ABCDEABCDE";
181
182            assert_eq!(vec!["AA", "BB", "CC", "DD", "EE"], slice_text(text, 5))
183        }
184
185        #[test]
186        fn eight_slices() {
187            let text = "ABCDEFGHABC";
188
189            assert_eq!(
190                vec!["AA", "BB", "CC", "D", "E", "F", "G", "H"],
191                slice_text(text, 8)
192            )
193        }
194    }
195
196    #[test]
197    fn test_text_slices_ioc() {
198        let text = "ABCA";
199
200        let expected = vec![
201            (1, index_of_coincidence("ABCA")),
202            (
203                2,
204                (index_of_coincidence("AC") + index_of_coincidence("BA")) / 2.0,
205            ),
206            (
207                3,
208                (index_of_coincidence("AA")
209                    + index_of_coincidence("B")
210                    + index_of_coincidence("C"))
211                    / 3.0,
212            ),
213            (
214                4,
215                (index_of_coincidence("A")
216                    + index_of_coincidence("B")
217                    + index_of_coincidence("C")
218                    + index_of_coincidence("D"))
219                    / 4.0,
220            ),
221        ];
222
223        assert_eq!(expected, text_slices_ioc(text))
224    }
225}
cryptography_breaker/algorithms/vigenere/find_key_len.rs

cryptography_breaker/algorithms/vigenere/
find_key_len.rs
