一文读懂Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换算法

注意这个算法是基于离散对数的，如果对于离散对数不了解的读者可以查看我之前的对于离散对数讲解的文章。

算法描述

首先选定一个素数q和这个素数的一个原根, 这两个数字作为公开的信息，然后对于想要交换数据的Alice和Bob, 他们分别选择两个随机的整数和这两个随机整数都小于q, 然后分别计算, , 然后对于A来说，把发送给B, 同理，对于B来说把发送给A, 然后A和B分别计算, , 这两种方式计算的K是一样的，下面简单来证明一下:

这样看起来，可能觉得我上面啰嗦了这么一大段，说的是个啥，下面来看一个图，简单的理解一下这个过程。

Diffie-Hellman密钥交换算法过程

这里，Alice和Bob通过这个算法获得了一个Key, 到这里有读者可能会发问了，难道这就结束了？下面来具体分析一下这个过程，假设攻击者的手段特别强大，能够截获所有的消息，那么对于攻击者来说，所能获取的信息有:

• q = 353
• = 3
• = 40
• = 248

那么，如果说攻击者要获取到密钥(K = 160), 那么实际上攻击者需要计算或者说, 对于这个例子来说，穷举是能出来的，但是密码学当中，显然是不会采用这么小的素数的，如果对于一个大的素数比如2048bit的大素数来说，穷举显然是不可能的。

中间人攻击

1. 攻击者首先生成两个随机的私钥和, 然后分别计算他们的对应的公钥,
2. Alice把自己生成的公钥发送给Bob
3. 攻击者截获Alice发送给Bob的, 然后发送给Bob, 同时计算得到
4. Bob收到攻击者发来的此时，Bob并不知道这实际上不是Alice发来的消息，然后Bob按照发送来的公钥来计算
5. Bob计算自己的公钥并发送给Alice
6. 攻击者再次截获, 然后将发送给Alice，同时攻击者计算
7. Alice收到攻击者发送来的, 同时计算, 此时同样Alice也不知道这个密钥实际上不是来自Bob的

到这里，虽然Alice和Bob已经完成了密钥交换，但是实际上这个密钥已经被攻击者替换了，攻击者可以拿到他们通信的所有的信息。

下面来看一个具体的例子，还是以上面说过的Alice和Bob为例，和上图一样，依然采用q = 356,  = 3为例。

中间人攻击

从图中可以看出，尽管Alice和Bob交换了密钥，但是攻击者却可以拿到他们通信的信息，因此, 对于密钥交换协议来说，并没有办法去抵御这种攻击，因为密钥交换协议并没有去验证密钥发送者的身份，也就是Alice无法判断密钥确实是来自Bob的，同理Bob也没法判断密钥确实是来自Alice的，如上面的第四条和第七条所示。这个后续可以通过签名+证书来解决。

代码示例

对于这个算法来说，代码相对来说比较简单，对于如何去找到一个素数以及如何找到这个素数的一个原根，相关代码可以查看之前的文章，在这里就不啰嗦了，我直接选择了一个素数进行运算的。

use num_bigint::{BigUint};
fn calc_y(p: &BigUint, alpha: &BigUint, x: &BigUint) -> BigUint {
    alpha.modpow(&x, &p)
}
fn calc_k(p: &BigUint, x: &BigUint, y: &BigUint) -> BigUint {
    y.modpow(&x, &p)
}
#[cfg(test)]
mod test {
    use num_bigint::{BigUint, RandBigInt};
    use crate::diffie_hellman::{calc_y, calc_k};
    #[test]
    fn test() {
        let p = BigUint::from(104729u64);
        let alpha = BigUint::from(17596u64);
        let mut rng = rand::thread_rng();
        let xa = rng.gen_biguint(16);
        println!("[private] Alice selected X is {}", xa);
        let ya = calc_y(&p, &alpha, &xa);
        println!("[public] Alice calculate Y is {}", ya);
        let xb = rng.gen_biguint(16);
        println!("[private] Bob selected X is {}", xb);
        let yb = calc_y(&p, &alpha, &xb);
        println!("[public] Bob calculate Y is {}", yb);
        let ka = calc_k(&p, &xa, &yb);
        println!("[private] Alice calculate Key is {}", ka);
        let kb = calc_k(&p, &xb, &ya);
        println!("[private] Bob calculate Key is {}", kb);
    }
}

总结

有了这个密钥交换的算法，实际上就可以在不安全的信道当中进行密钥交换了，这也就弥补了对称加密体系当中密钥下发的问题，但是这样做产生了一个新的问题，也就是存在中间人攻击的可能，密钥交换协议不能够对抗中间人攻击，因为他并没有验证通信双方的身份，也就是Alice没法确认这个消息是来自Bob的，这个问题实际上是可以通过数字签名+证书来解决的，在这一篇文章当中就不过多描述解决方案了。