RSA加密的一点理解
先科普，假装铺垫一下。
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。
RSA加密解密整个过程
- 生成两个极大的质数 p、q。 (条件：p、q不能靠太近，(p - 1)或者(q - 1)的因子不能太小)
- n = p * q (一般 n 二进制为1024位或者2048位，越高越好)
- ψ(n) = (p - 1) * (q - 1) 欧拉函数，求ψ(n)。
- 设置公钥e，公钥的范围为1 < e < ψ(n) (条件：e 与 ψ(n) 互质,e 不能太小)
- 计算私钥 d，e * d / ψ(n) 余数为1(或者说取模为1)。 (条件：d不能太小)
至此已经求得所有需要数值
- 对 m 进行加密： m^e/n 取模 => 加密后的数据 c
- 对 c 进行解密： c^d/n 取模 => 原文 m
分析
首先列出公开的数据： n、e、c。
解密需要的数据：n、d、c。
=> 如果能通过 n、e、c 求出 d，那么我们就破解了 RSA 加密
由第5项可知，求 d 需要得到 ψ(n)
由第3项可知，求 ψ(n) 需要求出 p、q
由第2项可知，p、q可以通过 n 求得
然而通过一个极大整数 n 去求p、q，是数学上一个公认的难题，几乎不可能完成~
思考
- 是否有通过可能存储一张关于 n 和 p、q 的表来破解 RSA？
理论上可行，但是大数的素数数量非常多，100位的大素数就有大约 10^100 个，蒙对的几率很低。 - 是否有可能暴力破解，人力不行我们有计算器呀？
通过查阅资料，1024位好像已经可以通过量子计算机，在一周左右时间内暴力破解。但是一般人没这种条件，而且 RSA 可以换成 2048位，更保险，再退一步，加密方也可以通过一段时间换一次 n 来防止破解。
瞎扯
归根结底，RSA 加密的核心就是大数的质数分解非常困难。数学真的是无处不在，高数无用论统统 go die 吧。
