关于破解RSA算法的遐想

ZhuZhuWonder 2016-10-29

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

首先在讨论之前,先来回顾一下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、台上一分钟,台下十年功。

相关推荐