关于破解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、台上一分钟,台下十年功。