Skip to content

Commit 6189823

Browse files
Rust-TrendsRust-Trends
authored
Add Diffie-Hellman Key Exchange (TheAlgorithms#441)
1 parent f69c512 commit 6189823

4 files changed

Lines changed: 355 additions & 0 deletions

File tree

‎Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@ version = "0.1.0"
55
authors = ["Anshul Malik <malikanshul29@gmail.com>"]
66

77
[dependencies]
8+
lazy_static = "1.4.0"
89
num-bigint = { version = "0.4", optional = true }
910
num-traits = { version = "0.2", optional = true }
1011

‎src/ciphers/diffie_hellman.rs‎

Lines changed: 350 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,350 @@
1+
// Based on the TheAlgorithms/Python
2+
// RFC 3526 - More Modular Exponential (MODP) Diffie-Hellman groups for
3+
// Internet Key Exchange (IKE) https://tools.ietf.org/html/rfc3526
4+
5+
use lazy_static;
6+
use num_bigint::BigUint;
7+
use num_traits::{Num, Zero};
8+
use std::{
9+
collections::HashMap,
10+
time::{SystemTime, UNIX_EPOCH},
11+
};
12+
13+
// Using lazy static to initialize statics that require code to be executed at runtime.
14+
lazy_static! {
15+
// A map of predefined prime numbers for different bit lengths, as specified in RFC 3526
16+
static ref PRIMES: HashMap<u8, BigUint> = {
17+
let mut m:HashMap<u8, BigUint> = HashMap::new();
18+
m.insert(
19+
// 1536-bit
20+
5,
21+
BigUint::parse_bytes(
22+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
23+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
24+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
25+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
26+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
27+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
28+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
29+
670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
30+
16
31+
).unwrap()
32+
);
33+
m.insert(
34+
// 2048-bit
35+
14,
36+
BigUint::parse_bytes(
37+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
38+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
39+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
40+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
41+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
42+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
43+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
44+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
45+
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
46+
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
47+
15728E5A8AACAA68FFFFFFFFFFFFFFFF",
48+
16
49+
).unwrap()
50+
);
51+
52+
m.insert(
53+
// 3072-bit
54+
15,
55+
BigUint::parse_bytes(
56+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
57+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
58+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
59+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
60+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
61+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
62+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
63+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
64+
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
65+
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
66+
15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64\
67+
ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7\
68+
ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B\
69+
F12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
70+
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31\
71+
43DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF",
72+
16
73+
).unwrap()
74+
);
75+
m.insert(
76+
// 4096-bit
77+
16,
78+
BigUint::parse_bytes(
79+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
80+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
81+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
82+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
83+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
84+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
85+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
86+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
87+
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
88+
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
89+
15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64\
90+
ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7\
91+
ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B\
92+
F12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
93+
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31\
94+
43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7\
95+
88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA\
96+
2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6\
97+
287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED\
98+
1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9\
99+
93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199\
100+
FFFFFFFFFFFFFFFF",
101+
16
102+
).unwrap()
103+
);
104+
m.insert(
105+
// 6144-bit
106+
17,
107+
BigUint::parse_bytes(
108+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08\
109+
8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B\
110+
302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9\
111+
A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6\
112+
49286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8\
113+
FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D\
114+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C\
115+
180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF695581718\
116+
3995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D\
117+
04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7D\
118+
B3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D226\
119+
1AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
120+
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFC\
121+
E0FD108E4B82D120A92108011A723C12A787E6D788719A10BDBA5B26\
122+
99C327186AF4E23C1A946834B6150BDA2583E9CA2AD44CE8DBBBC2DB\
123+
04DE8EF92E8EFC141FBECAA6287C59474E6BC05D99B2964FA090C3A2\
124+
233BA186515BE7ED1F612970CEE2D7AFB81BDD762170481CD0069127\
125+
D5B05AA993B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492\
126+
36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BDF8FF9406\
127+
AD9E530EE5DB382F413001AEB06A53ED9027D831179727B0865A8918\
128+
DA3EDBEBCF9B14ED44CE6CBACED4BB1BDB7F1447E6CC254B33205151\
129+
2BD7AF426FB8F401378CD2BF5983CA01C64B92ECF032EA15D1721D03\
130+
F482D7CE6E74FEF6D55E702F46980C82B5A84031900B1C9E59E7C97F\
131+
BEC7E8F323A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA\
132+
CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE32806A1D58B\
133+
B7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55CDA56C9EC2EF29632\
134+
387FE8D76E3C0468043E8F663F4860EE12BF2D5B0B7474D6E694F91E\
135+
6DCC4024FFFFFFFFFFFFFFFF",
136+
16
137+
).unwrap()
138+
);
139+
140+
m.insert(
141+
// 8192-bit
142+
18,
143+
BigUint::parse_bytes(
144+
b"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
145+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
146+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
147+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
148+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
149+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
150+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
151+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
152+
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
153+
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
154+
15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64\
155+
ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7\
156+
ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B\
157+
F12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
158+
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31\
159+
43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7\
160+
88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA\
161+
2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6\
162+
287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED\
163+
1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9\
164+
93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934028492\
165+
36C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BD\
166+
F8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831\
167+
179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1B\
168+
DB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF\
169+
5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6\
170+
D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F3\
171+
23A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AA\
172+
CC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE328\
173+
06A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55C\
174+
DA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE\
175+
12BF2D5B0B7474D6E694F91E6DBE115974A3926F12FEE5E4\
176+
38777CB6A932DF8CD8BEC4D073B931BA3BC832B68D9DD300\
177+
741FA7BF8AFC47ED2576F6936BA424663AAB639C5AE4F568\
178+
3423B4742BF1C978238F16CBE39D652DE3FDB8BEFC848AD9\
179+
22222E04A4037C0713EB57A81A23F0C73473FC646CEA306B\
180+
4BCBC8862F8385DDFA9D4B7FA2C087E879683303ED5BDD3A\
181+
062B3CF5B3A278A66D2A13F83F44F82DDF310EE074AB6A36\
182+
4597E899A0255DC164F31CC50846851DF9AB48195DED7EA1\
183+
B1D510BD7EE74D73FAF36BC31ECFA268359046F4EB879F92\
184+
4009438B481C6CD7889A002ED5EE382BC9190DA6FC026E47\
185+
9558E4475677E9AA9E3050E2765694DFC81F56E880B96E71\
186+
60C980DD98EDD3DFFFFFFFFFFFFFFFFF",
187+
16
188+
).unwrap()
189+
);
190+
m
191+
};
192+
}
193+
194+
/// Generating random number, should use num_bigint::RandomBits if possible.
195+
fn rand() -> usize {
196+
SystemTime::now()
197+
.duration_since(UNIX_EPOCH)
198+
.unwrap()
199+
.subsec_nanos() as usize
200+
}
201+
202+
pub struct DiffieHellman {
203+
prime: BigUint,
204+
private_key: BigUint,
205+
public_key: BigUint,
206+
generator: u8,
207+
}
208+
209+
impl DiffieHellman {
210+
// Diffie-Hellman key exchange algorithm is based on the following mathematical concepts:
211+
212+
// - A large prime number p (known as the prime modulus) is chosen and shared by both parties.
213+
214+
// - A base number g (known as the generator) is chosen and shared by both parties.
215+
216+
// - Each party generates a private key a or b (which are secret and only known to that party) and calculates a corresponding public key A or B using the following formulas:
217+
// - A = g^a mod p
218+
// - B = g^b mod p
219+
220+
// - Each party then exchanges their public keys with each other.
221+
222+
// - Each party then calculates the shared secret key s using the following formula:
223+
// - s = B^a mod p or s = A^b mod p
224+
225+
// Both parties now have the same shared secret key s which can be used for encryption or authentication.
226+
227+
pub fn new(group: Option<u8>) -> Self {
228+
let mut _group: u8 = 14;
229+
if let Some(x) = group {
230+
_group = x;
231+
}
232+
233+
if !PRIMES.contains_key(&_group) {
234+
panic!("group not in primes")
235+
}
236+
237+
// generate private key
238+
let private_key: BigUint = BigUint::from(rand());
239+
240+
Self {
241+
prime: PRIMES[&_group].clone(),
242+
private_key,
243+
generator: 2, // the generator is 2 for all the primes if this would not be the case it can be added to hashmap
244+
public_key: BigUint::default(),
245+
}
246+
}
247+
248+
/// get private key as hexadecimal String
249+
pub fn get_private_key(&self) -> String {
250+
self.private_key.to_str_radix(16)
251+
}
252+
253+
/// Generate public key A = g**a mod p
254+
pub fn generate_public_key(&mut self) -> String {
255+
self.public_key = BigUint::from(self.generator).modpow(&self.private_key, &self.prime);
256+
self.public_key.to_str_radix(16)
257+
}
258+
259+
pub fn is_valid_public_key(&self, key_str: &str) -> bool {
260+
// the unwrap_or_else will make sure it is false, because 2 <= 0 and therefor False is returned
261+
let key = BigUint::from_str_radix(key_str, 16)
262+
.unwrap_or_else(|_| BigUint::parse_bytes(b"0", 16).unwrap());
263+
264+
// Check if the other public key is valid based on NIST SP800-56
265+
if BigUint::from(2_u8) <= key
266+
&& key <= &self.prime - BigUint::from(2_u8)
267+
&& !key
268+
.modpow(
269+
&((&self.prime - BigUint::from(1_u8)) / BigUint::from(2_u8)),
270+
&self.prime,
271+
)
272+
.is_zero()
273+
{
274+
return true;
275+
}
276+
false
277+
}
278+
279+
/// Generate the shared key
280+
pub fn generate_shared_key(self, other_key_str: &str) -> Option<String> {
281+
let other_key = BigUint::from_str_radix(other_key_str, 16)
282+
.unwrap_or_else(|_| BigUint::parse_bytes(b"0", 16).unwrap());
283+
if !self.is_valid_public_key(&other_key.to_str_radix(16)) {
284+
return None;
285+
}
286+
287+
let shared_key = other_key.modpow(&self.private_key, &self.prime);
288+
Some(shared_key.to_str_radix(16))
289+
}
290+
}
291+
292+
#[cfg(test)]
293+
mod tests {
294+
use super::*;
295+
296+
#[test]
297+
fn verify_invalid_pub_key() {
298+
let diffie = DiffieHellman::new(Some(14));
299+
assert_eq!(diffie.is_valid_public_key("0000"), false);
300+
}
301+
302+
#[test]
303+
fn verify_valid_pub_key() {
304+
let diffie = DiffieHellman::new(Some(14));
305+
assert_eq!(
306+
diffie.is_valid_public_key("EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"),
307+
true
308+
);
309+
}
310+
311+
#[test]
312+
fn verify_invalid_pub_key_same_as_prime() {
313+
let diffie = DiffieHellman::new(Some(14));
314+
assert_eq!(
315+
diffie.is_valid_public_key(
316+
"FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
317+
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
318+
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
319+
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
320+
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
321+
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
322+
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
323+
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
324+
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
325+
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
326+
15728E5A8AACAA68FFFFFFFFFFFFFFFF"
327+
),
328+
false
329+
);
330+
}
331+
332+
#[test]
333+
fn verify_key_exchange() {
334+
let mut alice = DiffieHellman::new(Some(16));
335+
let mut bob = DiffieHellman::new(Some(16));
336+
337+
// Private key not used, showed for illustrative purpose
338+
let _alice_private = alice.get_private_key();
339+
let alice_public = alice.generate_public_key();
340+
341+
// Private key not used, showed for illustrative purpose
342+
let _bob_private = bob.get_private_key();
343+
let bob_public = bob.generate_public_key();
344+
345+
// generating shared key using the struct implemenations
346+
let alice_shared = alice.generate_shared_key(bob_public.as_str()).unwrap();
347+
let bob_shared = bob.generate_shared_key(alice_public.as_str()).unwrap();
348+
assert_eq!(alice_shared, bob_shared);
349+
}
350+
}

‎src/ciphers/mod.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@ mod another_rot13;
33
mod base64;
44
mod caesar;
55
mod chacha;
6+
mod diffie_hellman;
67
mod hashing_traits;
78
mod kerninghan;
89
mod morse_code;
@@ -21,6 +22,7 @@ pub use self::another_rot13::another_rot13;
2122
pub use self::base64::{base64_decode, base64_encode};
2223
pub use self::caesar::caesar;
2324
pub use self::chacha::chacha20;
25+
pub use self::diffie_hellman::DiffieHellman;
2426
pub use self::hashing_traits::Hasher;
2527
pub use self::hashing_traits::HMAC;
2628
pub use self::kerninghan::kerninghan;

‎src/lib.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
#[macro_use]
2+
extern crate lazy_static;
13
pub mod backtracking;
24
pub mod big_integer;
35
pub mod ciphers;

0 commit comments

Comments
 (0)