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

[WWGD]

TL;DR Summary

Q-day is expected to arrive by around2035. How to deal with the potential pitfalls?

Edit:
Q-Day refers to the point in time when Quantum-based algorithms will be able to break within hours, large-enough keys used in factoring-based encryption, e.g., n=2048 for RSA 2048.

What will we do, what will be the pitfalls, when Quantum Computers are able to factor , say, large-enough keys, depending of the type of factoring-based encryption (Asymmetric)? This is the basis of most encryption models used nowadays. Some are said to be acquiring and storing large amounts of data now, aka, "Harvest now, Decrypt later"(2) , to use said data upon the availability of strong-enough Quantum Computers, which may compromise security.

Currently , alternative encryption methods exist, while others are being researched, so that this may end up being a new version of Y2K, where we will refit all our databases/data storage in time, so that it will be a non-event, albeit the situation is more uncertain in that, for one, the solutions aren't as clear as those of Y2K.

Major Quantum-based current algorithms to contend with are are Shor's , which can factor in Polynomial time, and Grover's algorithms (3)(4) . Shor's presents issues for Asymmetric encryption methods( like RSA or ECC) . Symmetric algorithms (No keys exchanged, e.g., AES 256, may be mitigated by using larger keys ))Major Any opinions?

Edit: I tried to change the "Downfall" for "Pitfalls", but the option to edit the TL; DR seems to be disabled.

1) Time estimates for onset of Q-day : https://www.secureworks.com/blog/predicting-q-day-and-impact-of-breaking-rsa2048

2) Harvest now, decrypt later:
https://www.appviewx.com/blogs/what-you-need-to-know-about-harvest-now-decrypt-later-attacks/

3)https://en.wikipedia.org/wiki/Grover's_algorithm

4)https://en.wikipedia.org/wiki/Shor's_algorithm


3) https://en.wikipedia.org/wiki/Grover's_algorithm

4)https://en.wikipedia.org/wiki/Shor's_algorithm

 

[pbuk]

What will we do when Quantum computers are able to factor , say, 30+-digit numbers?

Use 60+ digit numbers.

Some are said to be acquiring and storing large amounts of data now , waiting for Q day. It is said alternative encryption methods are being researched

We don't need to research them, we already have them. If you are storing any data that will still be confidential 10 years from now then you need to (i) prevent it getting into the hands of bad actors and (ii) use an appropriate encryption method.

 

[phinds]

use an appropriate encryption method

I don't see how that is possible. My browser uses what it uses (HTTPS) and if my online transaction is scoffed up now and in 5 years that encryption can be broken, they get all my info from that transaction. Until the browsers use better encryption, how can *I* use better encryption?

 

[FactChecker]

The field of quantum cryptography and quantum encryption studies ways to do unhackable encryption. Some companies are already getting ready (doing?) for it.

 

[phinds]

The field of quantum cryptography and quantum encryption studies ways to do unhackable encryption. Some companies are already getting ready (doing?) for it.

Yes, and when banks and browsers team up to use new encryption schemes then I might be protected, but what you are saying doesn't answer post #3

 

[FactChecker]

Yes, and when banks and browsers team up to use new encryption schemes then I might be protected, but what you are saying doesn't answer post #3

Good point, regarding current material encrypted by current methods being obtained and unencrypted in the future.

 

[WWGD]

Given some groups are storing current data in order to decode it after Q day , (assuming some data, such as ID, age, SS number etc. , used to authenticate , will likely still be useful to them. Edit: And records, data suggesting a shady past , may be used to blackmail), adjustments other than new types of encryption will likely be necessary.

 

[WWGD]

In always thought that creating self-contained groups that purposefully share false information in unsecured sites _only amongst them_ may be a good way of throwing off the Black hat types.

 

[pbuk]

My browser uses what it uses (HTTPS) and if my online transaction is scoffed up now and in 5 years that encryption can be broken, they get all my info from that transaction.

No, "they" can only get the information included in the transaction. What information do you think is included in an online transaction that you are concerned about?

 

[phinds]

No, "they" can only get the information included in the transaction. What information do you think is included in an online transaction that you are concerned about?

Financial transactions, medical records, etc.

 

[FactChecker]

No, "they" can only get the information included in the transaction. What information do you think is included in an online transaction that you are concerned about?

efiled taxes.

 

[pbuk]

efiled taxes.

I don't know how it works in the US but in the UK I can't think of any information in a tax return that would be particularly useful if intercepted by a bad actor.

And in order for the bad actor to be able to decode the information in five years time they must know today that the encrypted message is worth keeping because it contains interesting information and is not just a random post on an internet forum.

And in order to have the encrypted message they must be able to penetrate the communications on your network, either by a physical intrusion or by intercepting and decoding wireless communications using encrypted protocols that are not breakable at reasonable cost with todays technology.

If I lived in the US right now I would have plenty of things to worry about before I reached for the tin foil hat over this.

 

[Baluncore]

Large prime factorisation becomes irrelevant with secure one-time pads.
Quantum key distribution makes everything a one-time pad.

Cryptographic breakthroughs only become a real advantage, when you can read your enemies traffic, faster than they can act. Well-supported cryptanalysts, are inherently brighter and faster, than the enemies cipher clerks.

For the legacy archives, there may be historical interest, but the value of old information is very low, and the sewers are filled with it. The statutes of limitation, preclude the legal use of old information, but mud sticks.

The revelation or use of originally secure transmitted data, often carries a greater criminal penalty, than the original act that is being revealed.

Democracies change government faster than the archives are normally revealed. Only long term dictatorships can exist for long enough, to be damaged by access to the archives.

"In war-time, truth is so precious that she should always be attended by a bodyguard of lies". (Winston Churchill). Misinformation can be conjured-up faster than reality can be decrypted. Misinformation and conspiracy theories, are more available, and more believable than the truth.

Wikileaks demonstrated the embarrassment felt by Governments, on the revelation of their incompetence, when undeniable information became openly available.

How can Q-Day be any worse than that?

 

[WWGD]

I don't know how it works in the US but in the UK I can't think of any information in a tax return that would be particularly useful if intercepted by a bad actor.

And in order for the bad actor to be able to decode the information in five years time they must know today that the encrypted message is worth keeping because it contains interesting information and is not just a random post on an internet forum.

And in order to have the encrypted message they must be able to penetrate the communications on your network, either by a physical intrusion or by intercepting and decoding wireless communications using encrypted protocols that are not breakable at reasonable cost with todays technology.

If I lived in the US right now I would have plenty of things to worry about before I reached for the tin foil hat over this.

Personal information such as age, dob, ssn can be used for bkackhat attempts to authenticate the user: " I'm sorry , sir, I forgot my password. I'm Ben Johnson, dob 3/ 26/ 1945, etc. Edit: I had this account while I lived in 1000 Pepsi Lane, Boulder , Co, Can you remind me of my password?".

Edit: Besides, this is information that has _already_ been stolen , captured, and criminals are waiting for Q day to decrypt it. So no need to penetrate communications in the network.

 

[Baluncore]

" I'm sorry , sir, I forgot my password. I'm Ben Johnson, dob 3/ 26/ 1945, etc. Can you remind me of my password?"

We have set a new random password for you, and sent it to your (mobile phone) or (email address). Use that to log in, and you must change that to a new password within the next 5 minutes.

 

[WWGD]

We have set a new random password for you, and sent it to your (mobile phone) or (email address). Use that to log in, and you must change that to a new password within the next 5 minutes.

Possibly, valid point . One issue with that is that most companies lend essentially identical services or sell identical products( to each other). The way they differentiate themselves from the competitor is by the quality of their customer service, and are thus overly eager to help, please the customer. EDIT: Or maybe you can just tell the customer rep you've changed your phone. When you're paying someone $10/hr you're not likely to get top of the line service.

 

[pbuk]

Possibly, valid point . One issue with that is that most companies lend essentially identical services or sell identical products( to each other). The way they differentiate themselves from the competitor is by the quality of their customer service, and are thus overly eager to help them.

Maybe so but surely you are aware that intentionally storing plain text passwords so you can 'help' a customer by revealing them is not something that any competant company has done for more than a decade? (Although it is of course true that at least one very large company has unintentionally stored plain text passwords much more recently than that).

With two factor authentication knowing a password doesn't help anyway.

@WWGD the more time you spend trying to think of potential risks the less time you have available to protect yourself from real risks.

Edit: you can do that by using a password manager on all your devices to create and store secure and unique passwords and change them at least once a year.

 

[Baluncore]

Your password should be encrypted within the system, unavailable to customer reps for examination.

EDIT: Or maybe you can just tell the customer rep you've changed your phone.

If you change your phone, and have forgotten your password, you can transfer your old phone number to the new phone, or open a new account.

 

[pbuk]

Your password should be encrypted within the system, unavailable to customer reps for examination.

Hashed rather than encrypted, and therefore unavailable to anyone for any purpose.

 

[WWGD]

Well, despite all those best practices consistently implemented , weve had major data breaches on what, a monthly basis for years now? Do you think you will attract all the talent and knowhow by hiring for $10/hr for customer reps? The techniques/scenario I described aren't speculation; they've been used. The situation may not be as bad as I describe it but not as safe as you make them out to be either.

 

[Baluncore]

Well, despite all those best practices consistently implemented , weve had major data breaches on what, a monthly basis for years now?

The situation may not be as bad as I describe it but not as safe as you make them out to be either.

We only hear of the failures. How many computers and websites are there now out there, with how many passwords and daily hits? What is the data breech rate as a percentage of active users? Will Q-Day change any of that?

 

[WWGD]

We only hear of the failures. How many computers and websites are there now out there, with how many passwords and daily hits? What is the data breech rate as a percentage of active users? Will Q-Day change any of that?

I assume the major players are the ones that are seriously targeted. Others are attacked in very primitive ways using very simple template (Edit) attacks. I admit I am not an expert in this area Edit 2; I think we've dealt addressed and given the "relevant" opinions here . Thank you, thanks all, for your input.

 

[FactChecker]

Unfortunately, many financial companies only improve their security when customers demand it in their selection of a company. That is why banks tend to be slow in adopting improved security measures until those measures become so common that they are expected/demanded by customers.

 

[jbergman]

Personal information such as age, dob, ssn can be used for bkackhat attempts to authenticate the user: " I'm sorry , sir, I forgot my password. I'm Ben Johnson, dob 3/ 26/ 1945, etc. Edit: I had this account while I lived in 1000 Pepsi Lane, Boulder , Co, Can you remind me of my password?".

Edit: Besides, this is information that has _already_ been stolen , captured, and criminals are waiting for Q day to decrypt it. So no need to penetrate communications in the network.

There have already been so many large scale data breaches that most of this information is already on the dark web.

 

[WWGD]

There have already been so many large scale data breaches that most of this information is already on the dark web.

That's why I thought setting up databases with false content may help throw off some criminals. black-hat hackers.

 

[WernerQH]

Q day is expected to arrive by 2035.

I don't think Q-day is imminent. (Certainly not on a timescale of a decade!) All that talk of qubits notwithstanding, quantum computers are analog, not digital devices (https://arxiv.org/abs/2312.17570).
Theoreticians can conceive of perfect $\pi/2$-pulses turning $\ket 0$ into $\ket 1$ and vice versa, but experimental realization is a different matter. I'm pretty sure that factoring a 30-digit number with a quantum computer will turn out to be just as difficult as measuring frequencies with 30-digit accuracy. And metrologists will assure you that we aren't there yet.

 

[AndreasC]

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

 

[WWGD]

Maybe a lowball estimate but that's not the key issue, but rather what to do when Q day arrives. I'll do a bit more of a search, though, to provide a more accurate/supportable estimate.

 

[.Scott]

This IBM tutorial will walk you through the process of setting up a QM-secure SSH on your Linux computer system and then opening up a QM-secure connection to an IBM server that supports that QM-secure protocol.
That article will also give you a good sense as to how far away we are from a fully distributed QM-secure SSH protocol.
That article uses the term "fork" to denote a OpenSSH development branch that is not expected to ever become "main line". SSH is the standard and most common way a computer system has for creating a secure login. Current SSH's provide for a selection of encryption algorithms. A connection is made when the SSH's at each end of the communication select a algorithm that both of them support.

Of particular interest to the OP is this caution provided in the article:

This fork is currently based on OpenSSH version 8.9 [...]. IT IS AT AN EXPERIMENTAL STAGE, and has not received the same level of auditing and analysis that OpenSSH has received. [...] WE DO NOT RECOMMEND RELYING ON THIS FORK TO PROTECT SENSITIVE DATA. [...] As research advances, the supported algorithms may see rapid changes in their security, and may even prove insecure against both classical and quantum computers. We believe that the NIST Post-Quantum Cryptography standardization project is currently the best avenue to identifying potentially quantum-resistant algorithms, and strongly recommend that applications and protocols rely on the outcomes of the NIST standardization project when deploying quantum-safe cryptography. While at the time of this writing there are no vulnerabilities known in any of the quantum-safe algorithms used in this fork, it is advisable to wait on deploying quantum-safe algorithms until further guidance is provided by the standards community, especially from the NIST standardization project. We realize some parties may want to deploy quantum-safe cryptography prior to the conclusion of the standardization project. We strongly recommend such attempts make use of so-called hybrid cryptography, in which quantum-safe public-key algorithms are combined with traditional public key algorithms (like RSA or elliptic curves) such that the solution is at least no less secure than existing traditional cryptography. This fork provides the ability to use hybrid cryptography.

 

[nsaspook]

Large prime factorisation becomes irrelevant with secure one-time pads.
Quantum key distribution makes everything a one-time pad.

Cryptographic breakthroughs only become a real advantage, when you can read your enemies traffic, faster than they can act. Well-supported cryptanalysts, are inherently brighter and faster, than the enemies cipher clerks.

For the legacy archives, there may be historical interest, but the value of old information is very low, and the sewers are filled with it. The statutes of limitation, preclude the legal use of old information, but mud sticks.

The revelation or use of originally secure transmitted data, often carries a greater criminal penalty, than the original act that is being revealed.

Democracies change government faster than the archives are normally revealed. Only long term dictatorships can exist for long enough, to be damaged by access to the archives.

"In war-time, truth is so precious that she should always be attended by a bodyguard of lies". (Winston Churchill). Misinformation can be conjured-up faster than reality can be decrypted. Misinformation and conspiracy theories, are more available, and more believable than the truth.

Wikileaks demonstrated the embarrassment felt by Governments, on the revelation of their incompetence, when undeniable information became openly available.

How can Q-Day be any worse than that?

The people at NSA don't think that QKD makes everything a one-time pad in practical application. Theory and secure implementation of secure systems are worlds apart. We used vacuum tube crypto systems on NSS systems until the 90's to transmit Nuclear EAM codes. Even if that old system of secure transmissions (that were stored for decades from the original transmission) were cracked by some future Quantum Computer they would be of no use because those messages required a separate one-time pad like Gold Codes for authentication.
https://en.wikipedia.org/wiki/Gold_Codes

https://www.nsa.gov/Cybersecurity/Quantum-Key-Distribution-QKD-and-Quantum-Cryptography-QC/

Synopsis​

NSA continues to evaluate the usage of cryptography solutions to secure the transmission of data in National Security Systems. NSA does not recommend the usage of quantum key distribution and quantum cryptography for securing the transmission of data in National Security Systems (NSS) unless the limitations below are overcome.

 

[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.