有一天，我编写了 RSA 公钥加密算法的实现。我还对这个算法做了一个简单的修改，所以我想写一篇关于这个主题的简短说明。 RSA 的防篡改基于因式分解问题。因式分解——多么可怕的词啊…
这并没有那么可怕
事实上，在创建密钥的第一阶段，我们取两个随机数，但这些数字只能被它们本身和一个“整除”。 素数数字。
我们称它们为p 和q。接下来我们应该得到数字n = p *q。它将用于进一步生成密钥，这些密钥又将用于加密和解密消息。在私钥和公钥的最终版本中，数字n将原样转移。
假设我们手中有一个 RSA 密钥和一条加密消息。我们从密钥中取出数字n并开始破解。
因式分解 n
因式分解–将数字分解为素数因子。首先，我们从密钥中取出数字n（在真正的密钥上，您可以使用 openssl 来完成），假设n = 35。然后我们将其分解为简单的因子n = 35 = 5 * 7，这就是我们的p和q。现在您可以使用收到的p、q重新生成密钥，解密消息并加密它，同时确保原始作者的可见性。
量子位没那么简单
真的有可能那么容易破解任何 RSA 吗？事实上不是，数字p、q被故意取大，使得经典计算机上的因式分解任务需要很长的时间（某种程度上10年）< br/>然而，使用 Shor 的量子算法，可以在很短的时间内分解一个数字。目前，有关该主题的文章规定了乘以给定数字的时间，即几乎是立即的。为了让 Shor 算法发挥作用，需要实现具有大量量子位的量子计算机。 2001 年，IBM 使用 7 个量子位对数字 15 进行因式分解。所以这一刻我们还需要等待很长时间，到时候我们就已经转向后量子加密算法了。
触摸短时间
Peter Shore 谈论他的因式分解算法
要在量子模拟器上尝试 Shor 算法，您可以安装 ProjectQ，其示例包括 shor.py 的实现，允许您对用户输入的数字进行因式分解。在模拟器上，执行时间令人沮丧，但这似乎是对量子计算机操作的有趣且好玩的模拟。
文章：
http://www.pagedon.com/rsa-explained-simply/my_programming/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
RSA的Python实现：
https://github.com/demensdeum/RSA-Python
