离散对数问题

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

由欧拉定理可知,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则 a^phi(n) = 1 (mod n)。
因此满足同余式 a^m = 1 (mod n)的最小正整数m存在,这个m称作a模n的阶,记作delta(n,a)。

原根

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

eg:

1
2
3
4
5
6
7
a=3, n=7
可知 3,7互质, 所以phi(n) = 7 - 1 = 6
可得 3^6 = 1 (mod 7)

计算3^1, 3^2, 3^3, 3^4, 3^5 (mod 7) 都不等于1, 所以 6为满足 a^x = 1 (mod n)的最小正整数

delta(7,3) = 6 = phi(7), 可得 3为模7的原根

性质

  • delta(n,a)一定能整除phi(n)
  • 若一个数m有原根, 则它的原根个数为phi(phi(m))

离散对数

如果对于一个整数b和质数p的一个原根a,可以找到一个唯一的指数i,使得:
b= a^i (mod p), 其中 0 <= i <= p-1
成立,那么指数i称为b的以a为基数的模p的离散对数。

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

应用

  • DH密钥交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
取一质数 7, 计算出其原根 3, 同时质数7和其原根3是公开的

Alice:
- 取一个随机数 3 作为自己的私钥
- 计算 3^3 (mod 7) = 6
- 将6作为公钥发送给Bob

Bob:
- 取一个随机数 1 作为自己的私钥
- 计算 3^1 (mod 7) = 3
- 将3作为公钥发送给Alice

Alice 使用 3 计算出共享密钥 3^3 (mod 7) = 6
Bob 使用 6 计算出共享密钥 6^1 (mod 7) = 6
  • Elgamal加密

接上面DH密钥交换

1
2
3
4
5
6
获取到公共密钥6之后,Alice和Bob都可以使用公共密钥6来加密信息

palintext: 6

加密: 6*6 (mod 7) = 1, 密文为 1
解密: 1*6^-1 (mod 7) = 6 <- 6^-1 是指6关于模7的逆元

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Alice 取一质数 7, 计算出其原根 3, 选一数 3 作为自己的私钥, 3^3 (mod 7) = 6
将 {7,3,6} 作为公钥公开

Bob想传递信息 6 给 Alice

Bob选一数 5 作为自己的私钥
- 加密密钥: 3^5 (mod 7) = 5
- 公钥: 3^5 (mod 7) = 5
- 密文: 6*(6^5) (mod 7) = 1
- 将 (5,1) 作为密文发送给Alice

Alice解密
- 计算解密密钥: 5^3 (mod 7) = 6
- 解密: 1 * 6^-1 (mod 7) = 6 <- 此处6^-1是指6关于模7的逆元(模反元素)