RSA算法的破解

MMMIX

RSA 的 vulnerable public keys 早就有人研究过，这是论文：
https://factorable.net/paper.html

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

Abstract
RSA and DSA can fail catastrophically when used with malfunctioning random number generators, but the extent to which these problems arise in practice has never been comprehensively studied at Internet scale. We perform the largest ever network survey of TLS and SSH servers and present evidence that vulnerable keys are surprisingly widespread. We find that 0.75% of TLS certificates share keys due to insufficient entropy during key generation, and we suspect that another 1.70% come from the same faulty implementations and may be susceptible to compromise. Even more alarmingly, we are able to obtain RSA private keys for 0.50% of TLS hosts and 0.03% of SSH hosts, because their public keys shared nontrivial common factors due to entropy problems, and DSA private keys for 1.03% of SSH hosts, because of insufficient signature randomness. We cluster and investigate the vulnerable hosts, finding that the vast majority appear to be headless or embedded devices. In experiments with three software components commonly used by these devices, we are able to reproduce the vulnerabilities and identify specific software behaviors that induce them, including a boot-time entropy hole in the Linux random number generator. Finally, we suggest defenses and draw lessons for developers, users, and the security community.

MMMIX

zuoyuanturing 发表于 2016-03-11 21:30
htt p://ww w.csdn.ne t/article/2012-02-15/311821
700万份密钥中有27000分重复 设总数为M 则M大约满足 ( ...

原始报道在这：
http://www.cnet.com/news/researc ... pular-cryptography/

原始论文：
http://eprint.iacr.org/2012/064.pdf

Ron was wrong, Whit is right

Arjen K. Lenstra, James P. Hughes

Abstract. We performed a sanity check of public keys collected on the web. Our main goal was
to test the validity of the assumption that different random choices are made each time keys are
generated. We found that the vast majority of public keys work as intended. A more disconcerting
finding is that two out of every one thousand RSA moduli that we collected offer no security.
Our conclusion is that the validity of the assumption is questionable and that generating keys
in the real world for “multiple-secrets” cryptosystems such as RSA is significantly riskier than
for “single-secret” ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.

MMMIX

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

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

MMMIX

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

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

MMMIX

zuoyuanturing 发表于 2016-03-16 13:19
理论是生成素数的算法只有那么几个 而随机函数又是个伪随机数 所以生成的素数是个有限集合

有在这靠着想当然扯淡的功夫，还是去看看 openssl 对 RSA 的实现吧

MMMIX

fender0107401 发表于 2016-03-16 16:26
回复 30# cjaizss

我看这也不是很多吗，lz赶紧出来弄个实现给大家看看吧。

楼主表示需要超算（最起码是天河二），个人PC肯定是不行的。