diff options
| -rw-r--r-- | data/6.out.txt | bin | 0 -> 2876 bytes | |||
| -rw-r--r-- | data/6.txt | 64 | ||||
| -rw-r--r-- | src/lib.rs | 81 | ||||
| -rw-r--r-- | tests/lib.rs | 15 |
4 files changed, 159 insertions, 1 deletions
diff --git a/data/6.out.txt b/data/6.out.txt Binary files differnew file mode 100644 index 0000000..cd20bce --- /dev/null +++ b/data/6.out.txt diff --git a/data/6.txt b/data/6.txt new file mode 100644 index 0000000..cecdb81 --- /dev/null +++ b/data/6.txt @@ -0,0 +1,64 @@ +HUIfTQsPAh9PE048GmllH0kcDk4TAQsHThsBFkU2AB4BSWQgVB0dQzNTTmVS +BgBHVBwNRU0HBAxTEjwMHghJGgkRTxRMIRpHKwAFHUdZEQQJAGQmB1MANxYG +DBoXQR0BUlQwXwAgEwoFR08SSAhFTmU+Fgk4RQYFCBpGB08fWXh+amI2DB0P +QQ1IBlUaGwAdQnQEHgFJGgkRAlJ6f0kASDoAGhNJGk9FSA8dDVMEOgFSGQEL +QRMGAEwxX1NiFQYHCQdUCxdBFBZJeTM1CxsBBQ9GB08dTnhOSCdSBAcMRVhI +CEEATyBUCHQLHRlJAgAOFlwAUjBpZR9JAgJUAAELB04CEFMBJhAVTQIHAh9P +G054MGk2UgoBCVQGBwlTTgIQUwg7EAYFSQ8PEE87ADpfRyscSWQzT1QCEFMa +TwUWEXQMBk0PAg4DQ1JMPU4ALwtJDQhOFw0VVB1PDhxFXigLTRkBEgcKVVN4 +Tk9iBgELR1MdDAAAFwoFHww6Ql5NLgFBIg4cSTRWQWI1Bk9HKn47CE8BGwFT +QjcEBx4MThUcDgYHKxpUKhdJGQZZVCFFVwcDBVMHMUV4LAcKQR0JUlk3TwAm +HQdJEwATARNFTg5JFwQ5C15NHQYEGk94dzBDADsdHE4UVBUaDE5JTwgHRTkA +Umc6AUETCgYAN1xGYlUKDxJTEUgsAA0ABwcXOwlSGQELQQcbE0c9GioWGgwc +AgcHSAtPTgsAABY9C1VNCAINGxgXRHgwaWUfSQcJABkRRU8ZAUkDDTUWF01j +OgkRTxVJKlZJJwFJHQYADUgRSAsWSR8KIgBSAAxOABoLUlQwW1RiGxpOCEtU +YiROCk8gUwY1C1IJCAACEU8QRSxORTBSHQYGTlQJC1lOBAAXRTpCUh0FDxhU +ZXhzLFtHJ1JbTkoNVDEAQU4bARZFOwsXTRAPRlQYE042WwAuGxoaAk5UHAoA +ZCYdVBZ0ChQLSQMYVAcXQTwaUy1SBQsTAAAAAAAMCggHRSQJExRJGgkGAAdH +MBoqER1JJ0dDFQZFRhsBAlMMIEUHHUkPDxBPH0EzXwArBkkdCFUaDEVHAQAN +U29lSEBAWk44G09fDXhxTi0RAk4ITlQbCk0LTx4cCjBFeCsGHEETAB1EeFZV +IRlFTi4AGAEORU4CEFMXPBwfCBpOAAAdHUMxVVUxUmM9ElARGgZBAg4PAQQz +DB4EGhoIFwoKUDFbTCsWBg0OTwEbRSonSARTBDpFFwsPCwIATxNOPBpUKhMd +Th5PAUgGQQBPCxYRdG87TQoPD1QbE0s9GkFiFAUXR0cdGgkADwENUwg1DhdN +AQsTVBgXVHYaKkg7TgNHTB0DAAA9DgQACjpFX0BJPQAZHB1OeE5PYjYMAg5M +FQBFKjoHDAEAcxZSAwZOBREBC0k2HQxiKwYbR0MVBkVUHBZJBwp0DRMDDk5r +NhoGACFVVWUeBU4MRREYRVQcFgAdQnQRHU0OCxVUAgsAK05ZLhdJZChWERpF +QQALSRwTMRdeTRkcABcbG0M9Gk0jGQwdR1ARGgNFDRtJeSchEVIDBhpBHQlS +WTdPBzAXSQ9HTBsJA0UcQUl5bw0KB0oFAkETCgYANlVXKhcbC0sAGgdFUAIO +ChZJdAsdTR0HDBFDUk43GkcrAAUdRyonBwpOTkJEUyo8RR8USSkOEENSSDdX +RSAdDRdLAA0HEAAeHQYRBDYJC00MDxVUZSFQOV1IJwYdB0dXHRwNAA9PGgMK +OwtTTSoBDBFPHU54W04mUhoPHgAdHEQAZGU/OjV6RSQMBwcNGA5SaTtfADsX +GUJHWREYSQAnSARTBjsIGwNOTgkVHRYANFNLJ1IIThVIHQYKAGQmBwcKLAwR +DB0HDxNPAU94Q083UhoaBkcTDRcAAgYCFkU1RQUEBwFBfjwdAChPTikBSR0T +TwRIEVIXBgcURTULFk0OBxMYTwFUN0oAIQAQBwkHVGIzQQAGBR8EdCwRCEkH +ElQcF0w0U05lUggAAwANBxAAHgoGAwkxRRMfDE4DARYbTn8aKmUxCBsURVQf +DVlOGwEWRTIXFwwCHUEVHRcAMlVDKRsHSUdMHQMAAC0dCAkcdCIeGAxOazkA +BEk2HQAjHA1OAFIbBxNJAEhJBxctDBwKSRoOVBwbTj8aQS4dBwlHKjUECQAa +BxscEDMNUhkBC0ETBxdULFUAJQAGARFJGk9FVAYGGlMNMRcXTRoBDxNPeG43 +TQA7HRxJFUVUCQhBFAoNUwctRQYFDE43PT9SUDdJUydcSWRtcwANFVAHAU5T +FjtFGgwbCkEYBhlFeFsABRcbAwZOVCYEWgdPYyARNRcGAQwKQRYWUlQwXwAg +ExoLFAAcARFUBwFOUwImCgcDDU5rIAcXUj0dU2IcBk4TUh0YFUkASEkcC3QI +GwMMQkE9SB8AMk9TNlIOCxNUHQZCAAoAHh1FXjYCDBsFABkOBkk7FgALVQRO +D0EaDwxOSU8dGgI8EVIBAAUEVA5SRjlUQTYbCk5teRsdRVQcDhkDADBFHwhJ +AQ8XClJBNl4AC1IdBghVEwARABoHCAdFXjwdGEkDCBMHBgAwW1YnUgAaRyon +B0VTGgoZUwE7EhxNCAAFVAMXTjwaTSdSEAESUlQNBFJOZU5LXHQMHE0EF0EA +Bh9FeRp5LQdFTkAZREgMU04CEFMcMQQAQ0lkay0ABwcqXwA1FwgFAk4dBkIA +CA4aB0l0PD1MSQ8PEE87ADtbTmIGDAILAB0cRSo3ABwBRTYKFhROHUETCgZU +MVQHYhoGGksABwdJAB0ASTpFNwQcTRoDBBgDUkksGioRHUkKCE5THEVCC08E +EgF0BBwJSQoOGkgGADpfADETDU5tBzcJEFMLTx0bAHQJCx8ADRJUDRdMN1RH +YgYGTi5jMURFeQEaSRAEOkURDAUCQRkKUmQ5XgBIKwYbQFIRSBVJGgwBGgtz +RRNNDwcVWE8BT3hJVCcCSQwGQx9IBE4KTwwdASEXF01jIgQATwZIPRpXKwYK +BkdEGwsRTxxDSToGMUlSCQZOFRwKUkQ5VEMnUh0BR0MBGgAAZDwGUwY7CBdN +HB5BFwMdUz0aQSwWSQoITlMcRUILTxoCEDUXF01jNw4BTwVBNlRBYhAIGhNM +EUgIRU5CRFMkOhwGBAQLTVQOHFkvUkUwF0lkbXkbHUVUBgAcFA0gRQYFCBpB +PU8FQSsaVycTAkJHYhsRSQAXABxUFzFFFggICkEDHR1OPxoqER1JDQhNEUgK +TkJPDAUAJhwQAg0XQRUBFgArU04lUh0GDlNUGwpOCU9jeTY1HFJARE4xGA4L +ACxSQTZSDxsJSw1ICFUdBgpTNjUcXk0OAUEDBxtUPRpCLQtFTgBPVB8NSRoK +SREKLUUVAklkERgOCwAsUkE2Ug8bCUsNSAhVHQYKUyI7RQUFABoEVA0dWXQa +Ry1SHgYOVBFIB08XQ0kUCnRvPgwQTgUbGBwAOVREYhAGAQBJEUgETgpPGR8E +LUUGBQgaQRIaHEshGk03AQANR1QdBAkAFwAcUwE9AFxNY2QxGA4LACxSQTZS +DxsJSw1ICFUdBgpTJjsIF00GAE1ULB1NPRpPLF5JAgJUVAUAAAYKCAFFXjUe +DBBOFRwOBgA+T04pC0kDElMdC0VXBgYdFkU2CgtNEAEUVBwTWXhTVG5SGg8e +AB0cRSo+AwgKRSANExlJCBQaBAsANU9TKxFJL0dMHRwRTAtPBRwQMAAATQcB +FlRlIkw5QwA2GggaR0YBBg5ZTgIcAAw3SVIaAQcVEU8QTyEaYy0fDE4ITlhI +Jk8DCkkcC3hFMQIEC0EbAVIqCFZBO1IdBgZUVA4QTgUWSR4QJwwRTWM= @@ -75,6 +75,80 @@ pub fn find_single_byte_xor_encrypted_string (inputs: &[Vec<u8>]) -> Vec<u8> { return best_decrypted; } +pub fn crack_repeating_key_xor (input: &[u8]) -> Vec<u8> { + let mut keysizes = vec![]; + for keysize in 2..40 { + let distance1 = hamming( + &input[(keysize * 0)..(keysize * 1)], + &input[(keysize * 1)..(keysize * 2)] + ) as f64; + let distance2 = hamming( + &input[(keysize * 1)..(keysize * 2)], + &input[(keysize * 2)..(keysize * 3)] + ) as f64; + let distance3 = hamming( + &input[(keysize * 2)..(keysize * 3)], + &input[(keysize * 3)..(keysize * 4)] + ) as f64; + let distance = distance1 + distance2 + distance3 / 3.0; + let normal_distance = distance / (keysize as f64); + keysizes.push((keysize, normal_distance)); + if keysizes.len() > 5 { + let (idx, _) = keysizes + .iter() + .enumerate() + .fold( + (0, (0, 0.0)), + |(accidx, (accsize, accdist)), (idx, &(size, dist))| { + if dist > accdist { + (idx, (size, dist)) + } + else { + (accidx, (accsize, accdist)) + } + } + ); + keysizes.swap_remove(idx); + } + } + + let mut min_diff = 100.0; + let mut best_key = vec![]; + for (keysize, _) in keysizes { + let strides: Vec<Vec<u8>> = (0..keysize) + .map(|n| { + // XXX sigh ): + let mut elts = vec![]; + for (i, &c) in input.iter().enumerate() { + if i % keysize == n { + elts.push(c); + } + } + elts + }) + .collect(); + let cracked: Vec<(u8, f64)> = strides + .iter() + .map(|input| crack_single_byte_xor_with_confidence(input)) + .collect(); + let diff = cracked + .iter() + .map(|&(_, diff)| diff) + .fold(0.0, |acc, x| acc + x); + let key = cracked + .iter() + .map(|&(c, _)| c) + .collect(); + let normal_diff = diff / (keysize as f64); + if normal_diff < min_diff { + min_diff = normal_diff; + best_key = key; + } + } + + return repeating_key_xor(input, &best_key[..]); +} + fn hamming (bytes1: &[u8], bytes2: &[u8]) -> u64 { count_bits(&fixed_xor(bytes1, bytes2)[..]) } @@ -110,11 +184,15 @@ fn crack_single_byte_xor_with_confidence (input: &[u8]) -> (u8, f64) { let lowercase = decrypted.to_ascii_lowercase(); let mut frequencies = [0; 26]; let mut total_frequency = 0; + let mut extra_frequencies = 0; for c in lowercase { + total_frequency += 1; if c >= 0x61 && c <= 0x7A { - total_frequency += 1; frequencies[(c - 0x61) as usize] += 1; } + else { + extra_frequencies += 1; + } } let mut total_diff = 0.0; @@ -122,6 +200,7 @@ fn crack_single_byte_xor_with_confidence (input: &[u8]) -> (u8, f64) { let relative_frequency = (crypt as f64) / (total_frequency as f64); total_diff += (english - relative_frequency).abs(); } + total_diff += (extra_frequencies as f64) / (total_frequency as f64); if total_diff < min_diff { min_diff = total_diff; diff --git a/tests/lib.rs b/tests/lib.rs index 80342e3..5ac51a7 100644 --- a/tests/lib.rs +++ b/tests/lib.rs @@ -4,6 +4,7 @@ extern crate "rustc-serialize" as serialize; use std::io::prelude::*; use std::fs::File; +use serialize::base64::FromBase64; use serialize::hex::FromHex; #[test] @@ -45,3 +46,17 @@ fn problem_5 () { let ciphertext = "0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f".from_hex().unwrap(); assert_eq!(matasano::repeating_key_xor(plaintext, key), ciphertext); } + +#[test] +fn problem_6 () { + let fh = File::open("data/6.txt").unwrap(); + let ciphertext = std::io::BufStream::new(fh) + .lines() + .map(|line| line.unwrap().from_base64().unwrap()) + .collect::<Vec<Vec<u8>>>() + .concat(); + let outfh = File::open("data/6.out.txt").unwrap(); + let plaintext = outfh.bytes().map(|c| c.unwrap()).collect(); + let got = matasano::crack_repeating_key_xor(&ciphertext[..]); + assert_eq!(got, plaintext); +} |