一篇文章搞懂 RSA 加密算法

非对称加密

Alice 想要把一些隐密的信息告诉 Bob，所以 Alice 要加密信息以后再传给 Bob
如果有一种方法，使得 Alice 加密信息，而 Bob 解密信息时使用另一种方法，那么这个传输就会相对安全

例如，Alice 想要把 345 告诉 Bob，于是 Alice 做了运算 345 * 91 = 31395，然后取后三位 395 发送给 Bob。 Bob 拿到数字后，做运算 395 * 11 = 4345，取后三位就得到了 Alice 想要告诉 Bob 的 345
在这个例子中，Alice 运算后只取了一部分，密文是有一定程度的信息丢失的。所以窃听者即便知道 Alice 是把明文乘了 91 也没办法还原。但 Bob 有一个不为人知的办法可以还原。这样就提高了信息的安全性。
在非对称加密中，把加密部分使用的密钥称作“公钥”，这个密钥是公开的，因为加密后的结果不可逆。而解密部分使用的密钥称作“私钥”，就是那个不为人知的密钥

RSA 算法

根据这样的原理，在 1977 年时，MIT 的三位分别名字以 RSA 开头的教授 Ron Rivest、Adi Shamir 和 Leonard Adleman 发明了一种算法，称作 RSA 算法

计算公钥和私钥

他们取两个质数 p 和 q 计算他们的乘积获得一个大数 n

n = p · q

然后使用欧拉函数得到 φ(n) = (p - 1)(q - 1)
在生成公钥时，在 1 和 φ(n) 中间取一个整数 e 使它和 φ(n)互质。这个 e 就是公钥
而生成私钥时，使得私钥 d 与公钥 e 相乘，除以 φ(n) 的余数是 1

加解密

那么加密时，需要用到公钥 e 对明文 m 进行加密运算：

(m^e)/n
计算求得余数 c 即为密文

而解密时，需要用到私钥 d 对密文 c 进行解密运算：

(c^d)/n
计算求得余数 m 即为明文

破解难度

加解密的内容最后都变成了余数，根据余数是没办法得知运算时的内容的，所以不能根据密文反推出明文
那么尝试根据公钥推算私钥的方法如下：
根据私钥的生成规则 (c·d)/φ(n) ...1 发现如果需要推断 d 则必须得知道欧拉函数 φ(n)，根据 φ(n) = (p - 1)(q - 1) 推断 φ(n) 则需要知道质数 p 和 q。由于 p 和 q 都是质数，获取他们的方法是要把大数 n 进行质因数分解，比如 21 就可以分成 3 和 7
由于 n 是一个 1024 位的二进制数，这样的数字如果使用计算机来进行质因数分解也许需要 10 年以上的时间，而这个密钥很有可能是定期更换的