大家好，又见面了，我是你们的朋友全栈君。
本文只是说一下RSA加密的流程，对于其他的不做过多的介绍！
- 首先找到两个大素数 p,q
- 计算n = p*q ， = φ(n)(p-1)*(q-1)，其中φ(n)表示的是n的欧拉函数值
- 任意选择一个满足要求的证书e,满足1 < e <φ(n),并且gcd(φ(n),e)==1
- 计算d，满足(d*e)%φ(n) ==1,即d是e在模φ(n)下的乘法逆元，因为e和φ(n)互质，所以他的乘法逆元一定存在
- 以{e,n}为共钥，{d,n}是私钥
下面我问来举个例子： 假设我们已经知道明文是19； 我们选定两个素数p=7,q=19； so n=p*q = 119 ，φ(n) = (p-1)*(q-1) = 96; 我们选择满足条件的e = 5，我们就能很简单的知道d = 77 所以共钥为{5，119}，密钥{77,119} 所以我们可以得到密文是 C = (19^e)%n = (19^5)9 = 66 解密为(C^d)%n = 19;
RSA的安全性
根据上面的推导，我们知道在RSA中又六个变量，p，q，n，φ(n),e,d
其中e和n是公开的，其中最关键的就是d，因为如果d泄露的话，就相当于私钥泄露了！
那么怎么破解RSA呢？
（1）e*d≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
所以：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/142050.html原文链接：https://javaforall.cn
