From 6eff17d9c28541dc594cb5cf084eb9fcd27b49ec Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Sun, 5 Apr 2015 23:01:34 -0400
Subject: problem 22

---
 src/crack.rs | 31 +++++++++++++++++++++++++++++++
 src/lib.rs   |  1 +
 tests/lib.rs | 10 ++++++++++
 3 files changed, 42 insertions(+)

diff --git a/src/crack.rs b/src/crack.rs
index a9aa4aa..dda7b15 100644
--- a/src/crack.rs
+++ b/src/crack.rs
@@ -2,9 +2,11 @@ use std;
 use std::ascii::AsciiExt;
 use std::borrow::ToOwned;
 use std::collections::{HashMap, HashSet};
+use rand::SeedableRng;
 
 use data::ENGLISH_FREQUENCIES;
 use primitives::{fixed_xor, unpad_pkcs7, hamming, repeating_key_xor};
+use random::MersenneTwister;
 
 #[derive(PartialEq,Eq,Debug)]
 pub enum BlockCipherMode {
@@ -356,6 +358,35 @@ pub fn crack_fixed_nonce_ctr_statistically (input: Vec<Vec<u8>>) -> Vec<Vec<u8>>
     return plaintext_lines;
 }
 
+pub fn clone_mersenne_twister_from_output (outputs: &[u32]) -> MersenneTwister {
+    fn untemper (val: u32) -> u32 {
+        fn unxorshift<F> (f: F, mut y: u32, n: usize, mask: u32) -> u32 where F: Fn(u32, usize) -> u32 {
+            let mut a = y;
+            for _ in 0..(32 / n) {
+                y = f(y, n) & mask;
+                a = a ^ y;
+            }
+            return a;
+        }
+
+        let mut y = val;
+
+        y = unxorshift(|a, n| {a >> n}, y, 18, 0xffffffff);
+        y = unxorshift(|a, n| {a << n}, y, 15, 0xefc60000);
+        y = unxorshift(|a, n| {a << n}, y,  7, 0x9d2c5680);
+        y = unxorshift(|a, n| {a >> n}, y, 11, 0xffffffff);
+
+        y
+    }
+
+    let mut state = [0; 624];
+    for (i, &output) in outputs.iter().enumerate() {
+        state[i] = untemper(output);
+    }
+
+    return MersenneTwister::from_seed((state, 0));
+}
+
 fn crack_single_byte_xor_with_confidence (input: &[u8]) -> (u8, f64) {
     let mut min_diff = 100.0;
     let mut best_key = 0;
diff --git a/src/lib.rs b/src/lib.rs
index 1704c8b..31a9aeb 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -35,3 +35,4 @@ pub use crack::find_single_byte_xor_encrypted_string;
 pub use crack::crack_single_byte_xor;
 pub use crack::crack_repeating_key_xor;
 pub use crack::crack_fixed_nonce_ctr_statistically;
+pub use crack::clone_mersenne_twister_from_output;
diff --git a/tests/lib.rs b/tests/lib.rs
index a304873..4e172d1 100644
--- a/tests/lib.rs
+++ b/tests/lib.rs
@@ -473,3 +473,13 @@ fn problem_21 () {
     ];
     assert_eq!(&got[..], &expected[..]);
 }
+
+#[test]
+fn problem_22 () {
+    let mut mt: matasano::MersenneTwister = thread_rng().gen();
+    let outputs: Vec<u32> = mt.gen_iter().take(624).collect();
+    let mut mt2 = matasano::clone_mersenne_twister_from_output(&outputs[..]);
+    for _ in 1..1000 {
+        assert_eq!(mt.gen::<u32>(), mt2.gen::<u32>());
+    }
+}
-- 
cgit v1.2.3-54-g00ecf