二、非对称加密算法（ RSA 算法）
4. RSA 算法公钥、私钥的计算过程
(1) 选择两个不同的大素数 p 和 q ；
(2) 计算乘积 n=pq 和 Φ(n)=(p-1)(q-1) ；
(3) 选择大于 1 小于 Φ(n) 的随机整数 e ，使得 gcd(e,Φ(n))=1 ；注： gcd 即最大公约数。
(4) 计算 d 使得 d*e mod Φ(n) =1 。
(5) 对每一个密钥 k=(n,p,q,d,e) ，定义加密变换为 Ek(x)=x**e mod n ，解密变换为 Dk(y)=y**d mod n ，这里
x,y∈Zn ；
(6)p,q 销毁，以 {e,n} 为公开密钥， {d,n} 为私有密钥。
实例：
1. 假设 p = 3 、 q = 11 （ p ， q 都是素数即可。），则 N = pq = 33 ；
2. r =Φ(n)= (p-1)(q-1) = (3-1)(11-1) = 20 ；
3. 根据 gcd(e,Φ(n))=1 ，即 gcd(e,20)=1 ，令 e=3 。取 d = 7 , 使得 (3 * 7) % 20 = 1
（ 3 、 33 ）
（ 7 、 33
）
公
钥
私
钥
得到了一对秘钥：公钥（ 3,33 ） 私钥
（ 7,33 ）
评论0