Re:NSA’s Backdoor Key
by rocketnasa on Monday September 18, 2023 @04:39PM
(#37561703)
Classic CPU hasn't held a candle compared to GPU on very repetitive math calculations. AI this year has really shown the same difference. In other words, it isn't just graphics... https://www.spiceworks.com/it-security/identity-access-manag...
Re:NSA’s Backdoor Key
by tgsovlerkhgsel on Monday September 18, 2023 @05:10PM
(#37562109)
I assume there is some reason why the past factorizations weren't done with GPUs. It could be just lack of a good implementation and insufficient numbers of people interested in the topic, but it could also be something about the algorithm not being very suitable for GPUs.
Re:NSA’s Backdoor Key
by boastful_inaba on Tuesday September 19, 2023 @02:41AM
(#37566390)
CUDA only had its initial release in 2007 (compared to the mentioned crack in 2009), and I remember it being a fairly limited product at that point. GPUS were also much slower back then.
Later, in 2019, a 795 bit key was factored with CPU time that "amounted to approximately 900 core-years on a 2.1 GHz Intel Xeon Gold 6130 CPU. Compared to the factorization of RSA-768, the authors estimate that better algorithms sped their calculations by a factor of 3–4 and faster computers sped their calculation by a factor of 1.25–1.67."
So assuming the better algorithms transfer to smaller numbers, someone who knows how to use them (factoring big numbers seems significantly harder than just running CADO-NFS and pointing it at a number and a cluster) could probably do it in a couple months on a couple dozen modern machines.
For example, using the "795-bit computations should be 2.25 times harder than 768-bit computations" from the publication accompanying the second factorization, we could assume 900/2.25 = 400 Core-years of the Xeon reference CPU (which is 6 years old by now) would be needed to break the smaller key with the modern software. Two dozen servers with 64 equivalently strong cores each would need slightly over 3 months. Not something a hobbyist would want to afford just for fun, but something that even a company with a moderate financial interest in doing could easily do, provided they had people capable of understanding and replicating this work.