数学公式显示 |关于 RSA算法原理（二）的一些评论 知道 n e d即公钥私钥 能否知道 pq 即两个大质数

源：www.mathjax.org/demos/mathml-samples/
http://www.mathjax.org/demos/tex-samples/
评：


RSA加密解密算法中，已知公钥和密匙n,e,d，是否能将合数n=p*q分解？

先温故一下RSA算法：
1、两个大质数p,q。
2、模数n=p*q。
3、欧拉函数f=(p-1)(q-1)。
4、随机数e，1 5、模逆d，即最小整数d，e*d=1 mod f。
也就是说：
知道了p,q也就知道了n,f；
知道了f,e也就知道了d。

下面温故一下加密解密算法：
已知明文m，满足m 加密：密文c=m^e mod n。
解密：明文x=c^d mod n。

证明一下解密得到的明文x=m：
由c=m^e mod n，得c=m^e+k*n。
代入x=c^d mod n，得x=(m^e+k*n)^d mod n。
于是x=m^e^d mod n，即x=m^(e*d) mod n。
由于e^d=1 mod f，得e*d=k*f+1。
代入得x=m^(kf+1) mod n，x=m*m^(kf) mod n。
当m与n互质时，x=m*(m^f)^k mod n,由欧拉定理可知x=m mod n。
又m 当m与n不互质时，由于n=p*q且m 若m=kp，则m^(q-1)=(k*p)^(q-1)=1 mod q。
接着[(k*p)^(q-1)]^[k*(p-1)]*kp=kp mod q，即(k*p)^(e*d)=k*p mod q。
又由于(k*p)^(ed)=k*q+k*p，(k*p)^(ed)=k*q*p+k*p，。
所以m^(ed)=m mod n，x=m。
即证。

----
现在考虑以下问题：
已知n和d，是否能将n分解？
可将这个问题分为几个问题：
1、已知n和f，是否能将n分解？
2、已知n,e和d，是否能得到f？
3、已知n和d，是否能得到e？
4、已知d和f，是否能得到e？
对于问题1的回答是肯定的。
n-f+1=sum=p+q，用二分法厉遍p，得p(sum-p)和n比较大小，即可快速确定p,q的值。
所以知道了n,f，就知道了p和q。也就是说，p,q,n,f四个数知道任意两个就可以知道全部。
那么，问题2就来了。如果p,q,n,f只知其一，又知道了e和d，是否能知道其它三个数呢？
最常见的情况就是知道了n,e和d。
由e*d=1 mod f，知e*d=k*f+1。
根据的同余方程定理可以知道存在k 并且d,k始终互质，由e,f互质又可推出e,k互质和f,d互质。
现在的问题又变为，e,d,f三个数各知道两个，能否知道第三个数？在已知n的情况下又是如何呢？
已知e,f可知道d，已知e,d不可知道f。
已知d,f，因为d,f互质，所以模逆e必存在，e必然在f的同余类中。又e 也就是说，e,f求d和d,f求e的过程是相同的。
这样，问题4的回答就是肯定的。
我们还可以发现，问题3的回答是否定的。
e和d对于f的地位是等价的，我们显然不可能用公匙n,e得到密匙n,d，所以反之亦然。
于是我们发现，f是十分重要的。知道了f，那么e和d就能互求。知道了f，那么n,p,q就能互求。
最后我们回到问题2。由于n,p,q的地位是等价的，我们可以换个死路考虑。
在已知p,e,d的情况下能否知道f和n？由e*d=k*f+1可以算出k*f。
然后又知道了p，可以算出k*(p-1)(q-1)/(p-1)=k*(q-1)。
然而这样组合的数量是很多的，如果不知打k，我们不可能知道q。所以知道p,e,d不能知道f或n。
那么知道n,e,d，也就是知道n和k*f，也就是知道p*q和k(p-1)(q-1)的情况下呢？
由于k是不可知的，k值的不同会导致f产生很大的变化。
我们虽然知道上限n，但直接拿f去除以n显然不能得到正确的k。
由于p和q的差值可能很大也可能很小，所以除出来的结果可能十分接近k也可能和k差很多。
于是无法缩小搜索p和q的范围，也无从使用二分法。
所以我认为，已知n,e,d是无法得到f的，同样也无法得到p和q。

如果大家有办法分解n的话，求详细的算法。