基于Python实现的RSA算法.zip

# RSA算法 ## 前言 网络世界中，发送的许多消息都是经过[加密](https://xcao.top/tags/加密)的。[加密](https://xcao.top/tags/加密)方式主要分为对称加密和非对称加密。然而对称加密不仅需要传输密文，还需要传输秘钥。如果秘钥在传输过程中遭到泄露，那么别人就可以知道你发送了什么。所以，非对称性加密几乎成了现在的主流。而[RSA](https://xcao.top/tags/rsa)[算法](https://xcao.top/tags/算法)就是现在非对称加密的主流[算法](https://xcao.top/tags/算法)之一。注意：base64之类的只是对字符进行编码，不能属于加密。 ## RSA算法的实现 首先，我们随机找来两个质数p和q，在实际运用中，这两个质数大小都是1024比特（比特可以参考上一篇文章https://xcao.top/post-214.html）接着，我们可以求出n，n=pq，然后，我们需要计算n的欧拉函数即φ(n)，这里 φ(n) 为(p-1)(q-1)。接着，需要找到公钥e，e的取值1<e< φ(n) e需要为正整数且e与 φ(n) 互质。接着还需要找到一个私钥d，d要求为正整数且ed除以 φ(n) 余数为1。 找到上述这些数字之后，我们就可以发送加密数据了。首先，需要接收方完成上述步骤，将公钥e，两质数积n传递给发送方。发送方收到这些数据后，便需要将发送的明文m进行一个运算。计算m的e次方，然后算出这个数与n的余数，将余数传递给接收方，这个算出来的数就是密文c。而接收方只需要一个简单的运算，算出密文c与的私钥d次方，算出这个数与n的余数。从数学定理上可以证明（具体的证明过程可以百度搜索，这里就不赘述了），算出来的这个余数一定等于明文m。这样就完成了一次安全的数据交换。为了更好的演示，我写了两个小程序去模拟RSA的信息传递过程。 ``` #RSA算法接收方程序，by小草 https://xcao.top/?p=222 import random def gcd(a, b): while b != 0: a, b = b, a % b return a def coprime(a, b): return gcd(a, b) == 1 # 两个函数作用均为判断两数是否互质 p = 0 q = 0 while p == q: p = random.choice([2, 3, 5, 7, 11, 13, 17, 19]) q = random.choice([2, 3, 5, 7, 11, 13, 17, 19]) n = p * q n1 = (p - 1) * (q - 1) #φ(n)不方便打，以n1代替 # 随机取p和q（此处只取20以内的质数方便计算，并计算出n以及φ(n) while True: e = random.randint(1, n1) if coprime(e, n1): break for i in range(1, 10000): d = (i * n1 + 1) / e if e*d > n1: if d % 1 == 0: d = int(d) break print('公钥是',e) print('两质数积为',n) # 计算出公钥以及私钥 c = int(input('请输入密文\n')) m = pow(c,d) m = m % n print('明文是',m) #RSA算法发送方程序，by小草 https://xcao.top/?p=222 e = int(input('请输入公钥\n')) n=int(input('请输入两质数积\n')) m = int(input('请输入明文\n')) c = pow(m,e) c = c % n print('密文是',c) ``` ## RSA算法安全性 那么，RSA算法是否安全呢。首先，在这里需要交换的数据有公钥e，密文m以及两质数之和n。而解密需要密文m，两质数之和n以及私钥d。那么我们能不能去计算出私钥d呢？从上边的实现过程可以发现，想要知道私钥d，就需要知道 φ(n) 想要知道 φ(n) 就需要知道p和q，也就是说，只要有人有能力去把两质数之和n给质因数分解，那么我们就有办法去破解RSA。但实际应用中RSA的两个质数是长度为1024的二进制数，以目前[技术](https://xcao.top/tags/技术)几乎无法破解。但随着量子计算机发展，有朝一日人们可能是有办法去分解的。但我们也相信，到了那个时候，一定也会有更先进的[技术](https://xcao.top/tags/技术)去进行加密。综上所述，目前人们是几乎无法破解RSA的，使用RSA算法加密的数据基本是安全的。