problem 33

5 files changed, 83 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 9d96c98..754df7b 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -761,6 +761,7 @@ dependencies = [
  "actix-web 0.7.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "base64 0.10.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "hex 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-bigint 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "openssl 0.10.20 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -914,6 +915,29 @@ dependencies = [
 ]
 
 [[package]]
+name = "num-bigint"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "num-integer 0.1.39 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand 0.5.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "num-integer"
+version = "0.1.39"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "num-traits"
+version = "0.2.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "num_cpus"
 version = "1.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2044,6 +2068,9 @@ dependencies = [
 "checksum net2 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "42550d9fb7b6684a6d404d9fa7250c2eb2646df731d1c06afc06dcee9e1bcf88"
 "checksum nodrop 0.1.13 (registry+https://github.com/rust-lang/crates.io-index)" = "2f9667ddcc6cc8a43afc9b7917599d7216aa09c463919ea32c59ed6cac8bc945"
 "checksum nom 4.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2ad2a91a8e869eeb30b9cb3119ae87773a8f4ae617f41b1eb9c154b2905f7bd6"
+"checksum num-bigint 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "57450397855d951f1a41305e54851b1a7b8f5d2e349543a02a2effe25459f718"
+"checksum num-integer 0.1.39 (registry+https://github.com/rust-lang/crates.io-index)" = "e83d528d2677f0518c570baf2b7abdcf0cd2d248860b68507bdcb3e91d4c0cea"
+"checksum num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "0b3a5d7cc97d6d30d8b9bc8fa19bf45349ffe46241e8816f50f62f6d6aaabee1"
 "checksum num_cpus 1.10.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1a23f0ed30a54abaa0c7e83b1d2d87ada7c3c23078d1d87815af3e3b6385fbba"
 "checksum openssl 0.10.20 (registry+https://github.com/rust-lang/crates.io-index)" = "5a0d6b781aac4ac1bd6cafe2a2f0ad8c16ae8e1dd5184822a16c50139f8838d9"
 "checksum openssl-probe 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "77af24da69f9d9341038eba93a073b1fdaaa1b788221b00a69bce9e762cb32de"
diff --git a/Cargo.toml b/Cargo.toml
index 84f1504..a15f9a6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -21,11 +21,16 @@ path = "tests/set3.rs"
 name = "set4"
 path = "tests/set4.rs"
 
+[[test]]
+name = "set5"
+path = "tests/set5.rs"
+
 [dependencies]
 actix = "0.7"
 actix-web = "0.7"
 base64 = "0.10"
 hex = "0.3"
+num-bigint = { version = "0.2", features = ["rand"] }
 openssl = "0.10"
 rand = "0.6"
 rand_core = "0.4"
diff --git a/src/dh.rs b/src/dh.rs
new file mode 100644
index 0000000..24c2277
--- /dev/null
+++ b/src/dh.rs
@@ -0,0 +1,28 @@
+use num_bigint::RandBigInt;
+
+pub struct DHKeyPair {
+    pub p: num_bigint::BigUint,
+    pub g: num_bigint::BigUint,
+    pub pubkey: num_bigint::BigUint,
+    privkey: num_bigint::BigUint,
+}
+
+impl DHKeyPair {
+    pub fn new(p: num_bigint::BigUint, g: num_bigint::BigUint) -> DHKeyPair {
+        let privkey = rand::thread_rng().gen_biguint_below(&p);
+        let pubkey = g.modpow(&privkey, &p);
+        DHKeyPair {
+            p,
+            g,
+            pubkey,
+            privkey,
+        }
+    }
+
+    pub fn key_exchange(
+        &self,
+        other_pubkey: &num_bigint::BigUint,
+    ) -> num_bigint::BigUint {
+        other_pubkey.modpow(&self.privkey, &self.p)
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index ae69401..7c1dc82 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,6 +1,7 @@
 mod aes;
 mod crack;
 mod data;
+mod dh;
 mod http;
 mod md4;
 mod primitives;
@@ -36,6 +37,7 @@ pub use crack::recover_16_bit_mt19937_key;
 pub use crack::recover_mersenne_twister_seed_from_time;
 pub use crack::recover_mt19937_key_from_time;
 pub use crack::BlockCipherMode;
+pub use dh::DHKeyPair;
 pub use http::create_query_string;
 pub use http::parse_query_string;
 pub use md4::md4;
diff --git a/tests/set5.rs b/tests/set5.rs
new file mode 100644
index 0000000..d969212
--- /dev/null
+++ b/tests/set5.rs
@@ -0,0 +1,21 @@
+#[test]
+fn problem_33() {
+    let p_hex = "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024\
+                 e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd\
+                 3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec\
+                 6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f\
+                 24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361\
+                 c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552\
+                 bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff\
+                 fffffffffffff";
+    let p = num_bigint::BigUint::parse_bytes(p_hex.as_bytes(), 16).unwrap();
+    let g = num_bigint::BigUint::from(2 as u8);
+
+    let a = matasano::DHKeyPair::new(p.clone(), g.clone());
+    let b = matasano::DHKeyPair::new(p.clone(), g.clone());
+
+    let s1 = a.key_exchange(&b.pubkey);
+    let s2 = b.key_exchange(&a.pubkey);
+
+    assert_eq!(s1, s2);
+}