Question

rsa加密原理 RSA加密算法原理是什么

Answer 1

1、首先要使用概率算法来验证随机产生的大的整数是否是质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。

2、除此之外这样找到的p和q还要满足一定的要求，首先它们不能太靠近，此外p-1或q-1的因子不能太小，否则的话N也可以被很快地分解。

3、此外寻找质数的算法不能给攻击者任何信息，这些质数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机和不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出p和q一半的位的话，那么他们就已经可以轻而易举地推算出另一半。

4、此外密钥d必须足够大，1990年有人证明假如p大于q而小于2q（这是一个很经常的情况）而d<n^（1 n的某一个渐进分数的分母（这个算法的原理是利用n="pq来逼近phi：=（p-1）（q-1），而算法要求d*e除以phi的余数是1，所以de=kphi+1，e/phi=k/d+1/phi，这说明了e/phi与k/d近似相等，从而可以通过e/N的渐进分数来寻找d（当然更多的，我们也可以更好地估计phi来获得一个更好的估计，但对通常情况（e=65537），RSA算法仍然是安全的））。

5、最后，RSA的原理保证了d和e必须与（p-1）（q-1）的因子互素，因此d，e都不可能为