RSA算法的破解

yyu0378

1：现在公开的RSA破解算法，最好的是普通数域筛选法，指数时间大约O(e1.9 (log N)1/3 (log log N)2/3)。只有不知道行不行的秀尔算法可以实现多项式时间，还需要量子计算机。就现在常用的2048位的rsa加密，基本就现在的计算机能力基本可以放弃了
2:彩虹表破解并不是简单的存贮所有值并反向查表的，请自行阅读相关文档

zuoyuanturing

确定的快速生成素数算法几乎会必破 只要存素数就行了 然后用N除素数 能整除的就被破解了 RSA困难基于N难分解

MMMIX

zuoyuanturing 发表于 2016-03-12 22:43
确定的快速生成素数算法几乎会必破

但是谁告诉你现在的RSA实现（例如 openssl）在生成密钥的时候，用的是“确定的快速生成素数算法”？

zuoyuanturing

有兴趣 用两个程序 一个产生N 一个产生素数 存起来 时间比较长
然后做除法比较 能整除的记录下位子 你大概就可以得出结论了 我也是很偶然的发现
随机函数本来也是说的伪随机函数 记得是个周期很大的循环
Diffie-Hellman可能都能破

MMMIX

zuoyuanturing 发表于 2016-03-13 00:01
随机函数本来也是说的伪随机函数 记得是个周期很大的循环

谁又告诉你人家用的是伪随机数？

zuoyuanturing

有真随机数? 都是伪随机数吧

windoze

回复 26# zuoyuanturing

那你以为/dev/random里面读出来的都是什么？

_nosay

也和LZ一样对这样的问题感兴趣，不过我自己觉得，除非能找到理论上的漏洞，纯粹依赖暴力破解的话，当硬件发展到分解1024位质数不是问题时，那这个算法利用1024*1024位的公钥也不是问题，最终的问题还是在于大质数分解。

zuoyuanturing

理论是生成素数的算法只有那么几个 而随机函数又是个伪随机数 所以生成的素数是个有限集合

cjaizss

根据高斯质数定理,粗略的计算了一下2^512以内的质数数量:
# echo '2^512/l(2^512)' | bc -l
37780035175234185435357766667050488056692034396892057545150881967747\
08722477848733639984673715651708068906311533953083814899006344664699\
2559962342245405.59825443774476668849