RSA

RSA_Encryption_Algorithm 使用python实现RSA加密算法 RSA加密过程： 1.随机生成两个大质数p,q 2.工业标准的公钥一般取e=65537,令n=p*q,s=(p-1)(q-1),取e对于s的模反元素d,由n与e组成公钥[n,e]用于加密,由n与d组成公钥[n,d]用于解密 3.message=要传输的信息,对信息进行加密的过程其实就是求解secret=message ^ e % n的过程,对信息进行解密的过程就是求解message=secret ^ d % n, 4.message与secret皆为十进制整数,但是要满足前提message < n,message < p * q,也就是说p和q的取值越大,加密信息越多 5.工业标准的私钥d一般是2048位的正整数,故n的取值也是2000位左右的十进制整数,意味着 p 和 q这两个质数以及也是接近1000位的十进制正整数 算法实现过程将遇到的问题: 1.生成两个1000位左右的质数,如果按照常规方法判定质数,算法复杂度=O(n),n=10^1000时,生成时间太长,需要使用更快的方法,这里使用Miller-Rabin素性检验算法 2.求解message=secret ^ d % n,d=10^2000时,计算时间过长,需要使用快捷方式迅速计算结果,这里使用快速幂模算法 3.求解e对于s的模反元素d的过程,使用了扩展欧几里得算法加快计算 更多详细信息请查看docx文档