Q-Day: When Quantum Computers can Factor ultra-large numbers in a few...

[pbuk]

For a more even-toned and well-referenced approach see for example https://www.secureworks.com/blog/predicting-q-day-and-impact-of-breaking-rsa2048

 

[nsaspook]

https://therecord.media/nakasone-interview-china-ai-deepseek-doge
For nearly six years, Gen. Paul Nakasone led two of the most powerful — and secretive — arms of American national security: the NSA and U.S. Cyber Command. One listens. The other talks back.

What's the most unhackable thing you own?

PN: The pencil and paper that I write on every single day.

CH: Why do you use a pencil instead of a pen?

PN: Because I need to erase it.

 

[pbuk]

Wait wait wait. Who said Q-day will happen by 2035? I have some serious doubts about that.

In 2022 the US government set the goal of "mitigating as much of the quantum risk as is feasible by 2035", and stated that the first sets of technical standards for quantum‑resistant cryptography were expected to be released publicly (by NIST and NSA for their respective jurisdictions) by 2024.¹

In November 2024 NIST published² the initial public draft of "Transition to Post-Quantum Cryptography Standards" referring to this date (and proposing the deprecation of some less secure standards by 2030).

Shortly after this the private organisation the Global Risk Institute published a report³ which was quoted with varying degrees of accuracy and sensationalism: one conclusion of the report was that "there is a significant chance that the quantum threat becomes concrete in the next 10 years" (i.e. by 2035). This conclusion was drawn from the fact that when the 32 experts surveyed for the report were asked the question "Please indicate how likely you estimate it is that a quantum computer able to factorize a 2048-bit number in less than 24 hours will be built within the next 5 years, 10 years, 15 years, 20 years, and 30 years", 10 of them placed a probability of at least "around 50%" on the 10 year 'bucket'.

1. https://bidenwhitehouse.archives.go...ng-risks-to-vulnerable-cryptographic-systems/
2. https://csrc.nist.gov/pubs/ir/8547/ipd
3. https://globalriskinstitute.org/publication/2024-quantum-threat-timeline-report/

 

[WWGD]

The way this came about is that I read about it and it seemed like an important issue that had not been divulged enough. I only wanted to raise awareness and not publish it at a high level of rigor, precision, so my research was very basic. I would prefer, if it were to be displayed, to have more time to tighten it up , as it's at a level of a first draft , and one intended for a water cooler level of " Did you know...", rather than as a presentation. I will have it tightened up asap. Please give me some time.

 

[WernerQH]

For a more even-toned and well-referenced approach see for example https://www.secureworks.com/blog/predicting-q-day-and-impact-of-breaking-rsa2048

Even-toned? I don't think the authors are "agnostics".

It relies on the difficulty of factoring large prime numbers

Factoring prime numbers is hard indeed ...

 

[mathwonk]

this free program apparently factors 30 digit integers immediately:
https://www.alpertron.com.ar/ECM.HTM

In fact it factored the only 60 digit integer I tried, also instantly.
web description:
"Factorization using the Elliptic Curve Method (ECM)
Applet that can be used to find 20- or 30-digit factors of numbers or numerical expressions up to 1000 digits long. It also computes the number and sum of divisors, Euler's totient and Moebius, and its decomposition as a sum of up to 4 perfect squares."

 

[nsaspook]

https://www.quantamagazine.org/what-is-the-true-promise-of-quantum-computing-20250403/
What Is the True Promise of Quantum Computing?

Despite the hype, it’s been surprisingly challenging to find quantum algorithms that outperform classical ones. In this episode, Ewin Tang discusses her pioneering work in “dequantizing” quantum algorithms — and what it means for the future of quantum computing.

LEVIN: So, let’s talk about that presentation. You mentioned earlier that the architects of the quantum algorithm that had made kind of a big splash were also going to be there at this workshop where you were meant to present this result that you had sped up the algorithm with equal success classically. That was not what anyone anticipated.

TANG: Yeah, it was maybe summer of 2018, I think, that I went to UC Berkeley and they were there, and some other people were there who were interested in quantum-machine-learning kinds of problems.

LEVIN: So, you’re an 18-year-old senior in college. Do they even know this? At the time?

 

[WWGD]

https://www.quantamagazine.org/what-is-the-true-promise-of-quantum-computing-20250403/
What Is the True Promise of Quantum Computing?

Despite the hype, it’s been surprisingly challenging to find quantum algorithms that outperform classical ones. In this episode, Ewin Tang discusses her pioneering work in “dequantizing” quantum algorithms — and what it means for the future of quantum computing.

Shor's ? To a lesser degree Grover's?

 

[nsaspook]

Shor's ?

Not an expert but it would seem that Shor's has limited applicability for general computing. The real potential of QC is solving all sorts of problems by outperforming classical computers.

https://www.quantamagazine.org/teen...to-quantum-recommendation-algorithm-20180731/
Major Quantum Computing Advance Made Obsolete by Teenager

 

[nsaspook]

Factoring ultra-large numbers is a problem but it's much less of a problem for secure encryption on messages and data as a whole for things that are 'really' classified secrets.

Asymmetric Key distribution is what's expected to be cracked when that happens. The base symmetric encryption standard like AES-256 will likely be secure and AES-512 even more so. Asymmetric Key distribution is the solution when you need to talk securely with people you don't know or trust. Most NSS systems have never had the need for Asymmetric Key distribution because if you're sending Top Secret data, it's always to someone you know and trust because the Keys needed to decrypt those message are only given (by trusted side channels, using guys with big guns) to people you have carefully vetted and only to previously approved and certified locations. Guys like Snowden (there have been others that actually compromise NSS systems, John Anthony Walker Jerry Whitworth, these guys did the jobs I once did) can break that trust and release classified info but they don't usually break NSS secure systems, they just compromise it's decrypted contents.

That's a People Problem, with a whole different of issues like social engineering to get past secure encryption today.

 

[.Scott]

Here's an update:
There is now a 10.0 release of OpenSSH which includes this feature:

For better protections in a quantum computing world, OpenSSH 10.0 now uses the hybrid post-quantum algorithm mlkem768x25519-sha256 by default for key agreement. The mlkem768x25519-sha256 algorithm is currently deemed safe against possible attacks by quantum computers and is considered faster than the prior default.

 

[WWGD]

Wait wait wait. Who said Q-day will happen by 2035? I have some serious doubts about that.

It's an estimate within an interval. I included a link in my first post.

 

[rcgldr]

Putting this into perspective. In 2001, quantum computers were able to factor 15 into prime numbers 3 and 5. As of 2025, they haven't been able to factor 21 (without the equivalent of guidance or pre-existing knowledge).

 

[nsaspook]

https://eprint.iacr.org/2025/1237.pdf
Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog