The (Almost) Secret Algorithm Researchers Used to Break Thousands of RSA Keys
https://algorithmsoup.wordpress.com/2019/01/15/breaking-an-unbreakable-code-part-1-the-hack/ [algorithmsoup.wordpress.com]
2019-01-16 06:36
Armed with this idea, the researchers scanned the web and collected 6.2 million actual public keys. They then computed the largest common divisor between pairs of keys, cracking a key whenever it shared a prime factor with any other key. All in all, they were able to break 12,934 keys. In other words, if used carelessly, RSA encryption provides less than 99.8\% security.
According to the authors, they were able to run the entire computation in a matter of hours on a single core. But a back-of-the-envelope calculation suggests that it should take years to compute GCD’s between 36 trillion pairs of keys, not hours.
So there we go. A computation that should have taken years is reduced to a matter of hours. And all it took was a bit of clever recursion.
source: L