公钥,私钥产生，一共和6个数有关：
p, q , n , φ(n) , e , d
下面详细说下这几个数的含义，与产生步骤
1. 随机产生两个不相等的质数 p , q
61 和 53
**2. n 为p q 的乘积 **
n = 61*53 = 3233
*3. 计算欧拉函数 φ(n) = (p-1)(q-1) **
φ(n) = 60*52 = 3210
4. 随机选择一个整数 e, 条件是1< e < φ(n)，且e与φ(n) 互质 (实际上，经常选择65537)
选择 17, e=17
** 5. 计算 e 对于φ(n) 的模反元素 d**
ed ≡ 1 (mod φ(n))
试子可以推导为：
ed - 1 = kφ(n) >>> ed + φ(n)k = 1
>> e 和 φ(n) 都是知道的 >> 17d + 3210k = 1
根据 ** 扩展欧几里得算法 ** 知道一定有整数解 d 和 k
有（2753，-15），d= 2753
**6. 将n和e封装成公钥，n和d封装成私钥 **
各自组成：
私钥 n = 3323 和 d = 2753
公钥 n = 3323 和 e =17
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无可能在已知n和e的情况下，推导出d？
（1）ed ≡ 1 (mod φ(n))。 只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n = pq。只有将n因数分解，才能算出p和q。
** 可以推出，只有将 n 质因数分解算出 p和q，才能得到d , 破解私钥 **
但是大整数的因数分解是非常困难的。到现在，除了暴力破解没有什么特别有效的方法。所以如果，你的n 取得特别大，密钥的长度足够长，就无法破解了。
实际应用中，密钥的长度一般是1024位，安全要求高的情况是2048位(目前人类的能分解的最大整数十 2^768)，所以1024是相当安全的。
怎么加密解密
加密，公钥（n,e）,对面信息m数字(字符串可以是编码)，m要小于n
m^e ≡ c (mod n)
代入公钥（3323,17）
65^17≡ 2790 (mod 3233)
c= 2790，就是加密之后的数字
解密，私钥（n,d）来解密
c^d ≡ m (mod n)
2790^2753 ≡ 65 (mod 3233)
解密出了 m = 65
其实我还要好多细节不懂，数学基础太弱了.......
网友评论