前言

网络世界中，发送的许多消息都是经过加密的。加密方式主要分为对称加密和非对称加密。然而对称加密不仅需要传输密文，还需要传输秘钥。如果秘钥在传输过程中遭到泄露，那么别人就可以知道你发送了什么。所以，非对称性加密几乎成了现在的主流。而RSA算法就是现在非对称加密的主流算法之一。注意：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)

代码已托管在GitHub

RSA算法安全性

那么，RSA算法是否安全呢。首先，在这里需要交换的数据有公钥e，密文m以及两质数之和n。而解密需要密文m，两质数之和n以及私钥d。那么我们能不能去计算出私钥d呢？从上边的实现过程可以发现，想要知道私钥d，就需要知道 φ(n) 想要知道 φ(n) 就需要知道p和q，也就是说，只要有人有能力去把两质数之和n给质因数分解，那么我们就有办法去破解RSA。但实际应用中RSA的两个质数是长度为1024的二进制数，以目前技术几乎无法破解。但随着量子计算机发展，有朝一日人们可能是有办法去分解的。但我们也相信，到了那个时候，一定也会有更先进的技术去进行加密。综上所述，目前人们是几乎无法破解RSA的，使用RSA算法加密的数据基本是安全的。