前置知识 欧拉, 欧拉定理, 模反元素(模逆元) 可参见: 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:
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密钥交换
取一质数 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密钥交换
获取到公共密钥6之后，Alice和Bob都可以使用公共密钥6来加密信息
palintext: 6
加密: 6*6 (mod 7) = 1, 密文为 1
解密: 1*6^-1 (mod 7) = 6 <- 6^-1 是指6关于模7的逆元上面的写的感觉不太对,完整过程
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的逆元(模反元素)