[RustLearning][Crypto] Diffie-Hellman算法

今天做的是一道Diffie-Hellman算法的简化题，Exercism的题目连接在这里：Diffie-Hellman。题目的描述如下：

测试用例中选取了两个素数P和G
通信发起的一方Alice选择一个大于1小于P的数a，作为Alice的私钥；Bob以同样的方式选择一个私钥b
Alice按照以下公式计算她的公钥: $A = G^a mod P$
Bob也按照上述公式计算公钥： $B=G^b mod P$
双方交换公钥，并计算通信私钥，对于Allice而言： $S = B^a mod P$, 对于Bob而言： $S=A^b mod P$ Diffie-Hellman算法的定义参考Wikipedia - Diffie-Hellman Diffie-Hellman算法的安全性在于有限域内的离散数学难题。这道题的解法如下：
```
use rand::Rng;
```

pub fn private_key(p: u64) -> u64 { let mut rng = rand::thread_rng(); rng.gen_range(2..p) }

pub fn public_key(p: u64, g: u64, a: u64) -> u64 { mod_exp(g, a, p) }

pub fn secret(p: u64, b_pub: u64, a: u64) -> u64 { mod_exp(b_pub, a, p) }

fn mod_exp(base: u64, exponent: u64, modulus: u64) -> u64 { let mut result: u128 = 1; let mut exp = exponent; let mut b = base as u128; let m = modulus as u128;

while exp > 0 {
    if exp % 2 == 1 {
        result = (result * b) % m;
    }

    exp /= 2;
    b = (b * b) % m;
}

result as u64

}

[package] edition = "2021" name = "diffie-hellman" version = "0.1.0"

[dependencies] rand = "0.8.3"

[features] big-primes = []

在求 $A = G^a mod P$ 时，如果采用常规的pow方法求取，会遇到结果出错的问题，原因在于pow的入参是u32，将u64类型的参数转化成u32后会丢失高位数据。我也尝试过另一个方法：

fn pow_u64(base: u64, exponent: u64) -> u64 {
    let mut result: u64 = 1;
    let mut exp = exponent;
    let mut b = base;

    while exp > 0 {
        if exp % 2 == 1 {
            result = result.saturating_mul(b);
        }

        exp /= 2;
        b = b.saturating_mul(b);
    }

    result
}

这也同样会因为结果超出u64的范围而导致丢失精度，结果不对。另外，这样计算到最后都是大数，会耗费计算机的计算能力，而mod_exp则利用了幂和模运算的特性，每次计算的时候都将结果进行取余，将计算结果最小化。

quinnwencn / blog

[RustLearning][Crypto] Diffie-Hellman算法 #40