前置知识 欧拉, 欧拉定理, 模反元素(模逆元) 可参见: 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 | a=3, n=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 | 取一质数 7, 计算出其原根 3, 同时质数7和其原根3是公开的 |
- Elgamal加密
接上面DH密钥交换
1 | 获取到公共密钥6之后,Alice和Bob都可以使用公共密钥6来加密信息 |
上面的写的感觉不太对,完整过程
1 | Alice 取一质数 7, 计算出其原根 3, 选一数 3 作为自己的私钥, 3^3 (mod 7) = 6 |