关于破解RSA算法的遐想

郑重声明：本文并非经过严格论证后的产物，而不过是“瞎猫碰上死耗子”的遐想而已，该思路如若可行，其实可推广到更多基于大素数分解的问题。

首先在讨论之前，先来回顾一下RSA算法的公私钥生成的过程：

1.随机选定两个大素数p,q。

2.计算公钥和私钥的公共模数n=pq。

3.计算模数n的欧拉函数φ(n)。

4.选定一个正整数e,使1<e<φ(n),且e与φ(n)互质。

5.计算d,满足de≡1(modφ(n))。

6.n与e决定公钥,n与d决定私钥。

RSA算法的安全性是基于大素数的分解。常规分解的确不容易，我也并没对其进行暴力分解的打算，我所谓的破解想法其实是基于这样几个事实：

1、别人拥有的计算机的运算能力，存储能力等，我们也可以拥有。

2、在上一点的条件下，别人能计算出来的大素数，我们也能计算出来。

3、素数的乘积具有唯一性。

考虑到这三点后，我们就可采取这样的做法：

1、尽我方计算机所能计算出它能求出的所有素数，假设保存为prims=[2,3,5,,...]。因为在事实1的条件下，我们可以认为他方计算后选择的素数必然在prims表中。

2、计算出每对素数的乘积，并将其与对应的素数因子一并保存（为了后面查询方便，也可按乘积大小存储），假设保存为：

pm=[(4,(2,2)),(6,(2,3)),(9,(3,3)),(10,(2,5)),...,(15,(3,5)),...]

因为素数不可能发生变化，所以这两步我们可以在任何计算机空闲的时候进行，此时我们的目的就是单纯的计算素数，运行多长时间之类的不考虑，权当台下修炼，千日养兵，静待用兵一时。

……

终于，某时刻我们获得了他方公钥对(n,e)，此时平时积累下的pm表就排上用场了。通过在该表中查询n（可采取二分法），我们就可迅速获知其对应的素数因子p和q，余下的问题自然也就迎刃而解了！

总结起来不过两句话：

1、养兵千日，用兵一时。

2、台上一分钟，台下十年功。