离散对数问题

前置知识欧拉, 欧拉定理, 模反元素(模逆元) 可参见: RSA加密

阶

由欧拉定理可知，若 $n,a$ 为正整数，且 $n,a$ 互素（即 $\gcd(a,n)=1$ ），则

$a^{\varphi(n)}\equiv 1\pmod n$

因此满足同余式

$a^m\equiv 1\pmod n$

的最小正整数 $m$ 存在，这个 $m$ 称作 $a$ 模 $n$ 的阶，记作 $\delta(n,a)$ 。

原根

若 $n,a$ 为正整数，且 $n,a$ 互质，如果 $\gcd(a,n)=1$ 且 $\delta(n,a)=\varphi(n)$ ，则称 $a$ 为模 $n$ 的原根。
简单来说，使该式成立的 $d$ 可能有很多个值，又由欧拉定理可知 $\delta(n,a)=\varphi(n)$ 一定是满足的，如果此时所有 $\delta(n,a)$ 的可能取值中 $\varphi(n)$ 是最小的，那么就称 $a$ 为模 $n$ 的原根。

eg:

$a=3,\ n=7$
可知 $3,7$ 互质，所以

$\varphi(n)=7-1=6$

可得

$3^6\equiv 1\pmod 7$

计算 $3^1,3^2,3^3,3^4,3^5\pmod 7$ 都不等于 $1$ ，所以 $6$ 为满足

$a^x\equiv 1\pmod n$

的最小正整数。

$\delta(7,3)=6=\varphi(7)$

可得 $3$ 为模 $7$ 的原根。

性质

$\delta(n,a)$ 一定能整除 $\varphi(n)$ 。
若一个数 $m$ 有原根，则它的原根个数为 $\varphi(\varphi(m))$ 。

离散对数

如果对于一个整数b和质数p的一个原根a，可以找到一个唯一的指数i，使得：

$b\equiv a^i\pmod p,\quad 0\le i\le p-1$

成立，那么指数i称为b的以a为基数的模p的离散对数。

离散对数难题是指：
当已知一个大质数p和它的一个原根a，如果给定一个b，要计算i的值是相当困难的。
常将i作为私钥, b作为公钥，即使知道b和a也无法求出i。

应用

DH密钥交换

取一质数 $7$ ，计算出其原根 $3$ ，同时质数 $7$ 和其原根 $3$ 是公开的。

Alice:

取一个随机数 $3$ 作为自己的私钥
计算

$3^3\equiv 6\pmod 7$

将 $6$ 作为公钥发送给 Bob

Bob:

取一个随机数 $1$ 作为自己的私钥
计算

$3^1\equiv 3\pmod 7$

将 $3$ 作为公钥发送给 Alice

Alice 使用 $3$ 计算出共享密钥：

$3^3\equiv 6\pmod 7$

Bob 使用 $6$ 计算出共享密钥：

$6^1\equiv 6\pmod 7$

Elgamal加密

接上面DH密钥交换

获取到公共密钥 $6$ 之后，Alice 和 Bob 都可以使用公共密钥 $6$ 来加密信息。

plaintext: $6$

加密：

$6\times 6\equiv 1\pmod 7$

密文为 $1$ 。
解密：

$1\times 6^{-1}\equiv 6\pmod 7$

其中 $6^{-1}$ 是指 $6$ 关于模 $7$ 的逆元。

上面的写的感觉不太对,完整过程

Alice 取一质数 $7$ ，计算出其原根 $3$ ，选一数 $3$ 作为自己的私钥，

$3^3\equiv 6\pmod 7$

将 $\{7,3,6\}$ 作为公钥公开。

Bob 想传递信息 $6$ 给 Alice。

Bob 选一数 $5$ 作为自己的私钥：

加密密钥：

$3^5\equiv 5\pmod 7$

公钥：

$3^5\equiv 5\pmod 7$

密文：

$6\times(6^5)\equiv 1\pmod 7$

将 $(5,1)$ 作为密文发送给 Alice

Alice 解密：

计算解密密钥：

$5^3\equiv 6\pmod 7$

解密：

$1\times 6^{-1}\equiv 6\pmod 7$

此处 $6^{-1}$ 是指 $6$ 关于模 $7$ 的逆元（模反元素）。