一篇文章搞懂 RSA 加密算法

in 软件 with 0 comment

非对称加密

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 算法

计算公钥和私钥

他们取两个质数 pq 计算他们的乘积获得一个大数 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) 则需要知道质数 pq。由于 pq 都是质数,获取他们的方法是要把大数 n 进行质因数分解,比如 21 就可以分成 3 和 7
由于 n 是一个 1024 位的二进制数,这样的数字如果使用计算机来进行质因数分解也许需要 10 年以上的时间,而这个密钥很有可能是定期更换的

综上,RSA 算法的破解难度非常大。

证明

RSA 算法的证明在某乎上有很多大神已经帮我们证明过了,这边就不多做赘述了

视频讲解

由于我最近在录制不同题材的视频课,这一部分也制作了简易的视频课内容上传了 B 站,点击这里即可观看完整视频
希望这一部分的介绍能够对你有所帮助