数学基础-离散对数

离散对数

本文来聊一聊有关离散对数的相关知识，接下来在讲DH的秘钥交换协议等算法之前，有必要先来说一下离散对数的相关知识，如果读者对于离散对数这一块非常熟悉的话，可以跳过这一部分，本文只是简单介绍了一下离散对数的相关概念，对于深入的了解可以自行查阅相关书籍(我个人理解也不是非常的透彻，如有描述错误的地方还请读者海涵)。

原根

根据欧拉定理，对于任意的互素的两个数字a和n, 有:

那么，根据欧拉定理可知，至少有一个数使得下面的式子成立:

我们把使得上式成立的最小的整数m称之为的阶，举一个例子，来看一下G(7)的模运算表。

我们可以发现，这个模运算实际上是呈现周期性的，比如上表当中的第二行，可以看到一旦出现1之后，后面就会呈现周期形式的运算。更一般的，如果一个数的阶是, 那么我们称这个数为n的「原根(primitive root)」, 可以发现如果a是n的本原根，那么通过a做幂运算可以得到G(n)的一个置换，也就是说a是G(n)的生成元。通过上表可以看出，对于7的原根有3和5，事实上，只有2, 3, , 有本原根，其中p是大于2的素数，a是正整数。

模对数运算

对于正实数来说，相信读者应该学过对数函数这个运算，它实际上是指数函数的逆函数，我们从上面可以发现，如果a是n的一个本原根，那么通过指数运算即可生成一个群，因此同样的可以定义模幂运算的逆函数，下面先来回顾一下中学学过的对数的有关性质:

对于任意素数p(这里只考虑素数, 虽然对于对数运算非素数也可以，但是在密码学当中用到的都是素数)的原根a, a的从1到p-1次幂可以产生从1到p-1的一个置换，因此对于任意整数b, b满足:

因此对于任意整数b和素数p的原根a, 可以找到唯一的i使得

这里，我们称i为以a为底的b的离散对数, 记做，和普通实数上面的对数运算类似，离散对数也有如下的性质:

离散对数的计算

考虑方程, 我们可以很容易的通过给定的x计算得到y, 但是反过来，如果给定y去计算x是困难的，这个和RSA当中的大整数分解的困难性类似，通常来说计算两个数的乘积运算是非常快的，但是计算一个数的分解是困难的。想DH的密钥交换算法，elgamal算法，DSA算法等都是基于离散对数求解困难性而产生的。

如何找到原根

和素性检验一样，如何去找到一个大素数的原根依然采用的是概率算法，具体算法如下：

• 生成一个随机的非0的整数在2~p-1之间
• 计算, 如果等于1，重复步骤1
• 计算, 如果等于1，重复步骤1, 否则g即为一个原根

上面这个算法只针对「安全素数」, 也就是p是素数(p-1)/2也是素数的素数, 正常来说，一个密码体系当中, 应采用安全素数做运算。

代码实现

下面是rust实现的寻找原根的算法,

pub fn find_primitive_root(p: BigUint) -> BigUint {
    let one = BigUint::from(1u8);
    let two = BigUint::from(2u8);
    if p == two {
        return one;
    }
    let p2 = (p.clone() - &one) / &two;
    loop {
        let mut rng = thread_rng();
        let g = rng.gen_biguint_range(&two, &(p.clone() - one.clone()));
        if !(g.modpow(&((&p - &one) / &two), &p) == one) {
            if !(g.modpow(&((&p - &one) / &p2), &p) == one) {
                return g;
            }
        }
    }
}