Breaking RSA Encryption with Quantum Computer

[krashfire]

https://news.bitcoin.com/chinese-researchers-claim-success-in-breaking-rsa-encryption-with-quantum-computer-experts-debate-veracity-of-discovery/

Is this true? A Quantum computer could break RSA encryption now? I thought it should take another 10 years at least

[Baofeng]

I'm no expect in Quantum Computing, but I will refer you to this thread,  I don't believe Quantum Computing will ever threaten Bitcoin.

It's been one of the hottest topic though in the last couple of years. But me thinks that if ever Quantum Computer will break the encryption then we should adjust and evolved as well.

I'm just skeptic of the news though, specially coming from the Chinese as we are used to have a lot of FUD coming from them specially about Bitcoin.

Another good thread to ponder:  Bitcoin's latest decline was triggered by quantum computing headlines.

[mocacinno]

it seems the world is focussing on bitcoin once again... I saw a similar article in several local newspapers (saying things like "quantum computers will kill bitcoin"). What people seem to forget is that RSA encryption is all around... If it gets broken, the world has bigger problems than killing bitcoin (imho).

[DaveF]

it seems the world is focussing on bitcoin once again... I saw a similar article in several local newspapers (saying things like "quantum computers will kill bitcoin"). What people seem to forget is that RSA encryption is all around... If it gets broken, the world has bigger problems than killing bitcoin (imho).

Exactly this. New users keep asking this again and again in the forum and it's the same answer again and again. IF RSA gets broken. BTC is going to be the least of the issues. The credit card industry would implode, followed by the banking industry followed by everything else that relies on encryption for transactions. BTC is such a small part of that to make it not worth mentioning.

-Dave

[blockman]

I have seen this type of worry years ago and there's even one news that I've read that said will overtake blockchain, but where did it go?
The thing is, when people are too optimistic about the downfall of bitcoin with such technology as quantum computing, it's never been new. It's been there for years ago and it's still fresh on my mind that there were too many articles that are optimistic about kicking off bitcoin's blockchain but never proceeded and were unsuccessful.

[o_e_l_e_o]

Maybe we could try reading the actual report rather than just believing click bait headlines?

We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm.

They managed to factor a 48 bit integer. So nowhere near the 2048 bits needed for RSA 2048. To do this, they say they need a quantum computer which doesn't exist and which utilizes technology which doesn't exist. If I publish a paper talking about a new space rocket design, that doesn't mean I've been to Mars.

We've known for years there are methods that advanced quantum computers will be able to use to attack our current encryption schemes. We also know that such computers are decades away. This Chinese paper tells us nothing new.

[Carlton Banks]

The credit card industry would implode, followed by the banking industry followed by everything else that relies on encryption for transactions.

so credit cards (or their network protocols) use RSA keys

They managed to factor a 48 bit integer. So nowhere near the 2048 bits needed for RSA 2048. To do this, they say they need a quantum computer which doesn't exist and which utilizes technology which doesn't exist. If I publish a paper talking about a new space rocket design, that doesn't mean I've been to Mars.

lol

the mathematics that Bitcoin keys use is not RSA. Unfortunately, people seem to treat the expression "quantum computer" as meaning "magic computer that knows every answer to every question, before you even finish thinking of the question"

[seoincorporation]

Maybe we could try reading the actual report rather than just believing click bait headlines?

We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm.

They managed to factor a 48 bit integer. So nowhere near the 2048 bits needed for RSA 2048. To do this, they say they need a quantum computer which doesn't exist and which utilizes technology which doesn't exist. If I publish a paper talking about a new space rocket design, that doesn't mean I've been to Mars.

We've known for years there are methods that advanced quantum computers will be able to use to attack our current encryption schemes. We also know that such computers are decades away. This Chinese paper tells us nothing new.

You are right o_e_l_e_o, looks like they are one step closer, but they haven't reached the goal yet. The thing is, now they are in the right road, which means now is the right way to give the new step in encryption. We need something complex and almost impossible for quantum computers because we are not sure how fast that technology will evolve, maybe in 5 years they become madness, that's hard to predict.

[digaran]

How exactly RSA is related to bitcoin?

[BitcoinBarrel]

Quantum computing is science-fiction not reality.

[Kryptowerk]

https://news.bitcoin.com/chinese-researchers-claim-success-in-breaking-rsa-encryption-with-quantum-computer-experts-debate-veracity-of-discovery/

Is this true? A Quantum computer could brewk RSA encryption now? I thought it should take another 10 years at least

News-feeds/websites/papers tend to opt for attention gaining headlines this is not new. Just vapor to disguise the nothingsness that acutally happened.
I know it's kinda off-topic, but since she is one of the best scientists I am aware of actively working against mis-representation of new science discoveries, I want to recommend Sabine Hossenfelder's youtube channel: https://www.youtube.com/@SabineHossenfelder/videos

She has done extensive coverage of the quantum-hype, as well as interesting topics such asdark-matter, black-holes, nuclear-fusion and other topics that tend to dominate the soft-science news-headlines.

[suzanne5223]

Firstly, Bitcoin Core encrypts its wallet using the AES not the RSA encryption algorithm and for the record, AES is what was used by the NSA for their classified info. As said by another user if it happened that a quantum computer break AES encryption, the problem won't be only for Bitcoin, the NSA, card company, and others government intelligence agency will be affected. However, it will be long before a quantum computer that can do that will be developed.

[jackg]

Did it say what size RSA the researchers were able to crack? I couldn't find it while I was skimming the article and those keys are already huge because of how weak the algorithm is. 128bit is considered fairly easy to crack afaik and that's not even considering if a medium sized tech firm was interested in cracking them.

If the US or China crack quantum proof encryption, they're telling no one before they make a profit off it and sell it to a Russian/South American cartel or some random government they think will profit them. At the moment it would be a leap considering how volatile quantum bits seem to have been made so far (I thought this was the main issue research has faced so far).

Firstly, Bitcoin Core encrypts its wallet using the AES not the RSA encryption algorithm and for the record, AES is what was used by the NSA for their classified info. As said by another user if it happened that a quantum computer break AES encryption, the problem won't be only for Bitcoin, the NSA, card company, and others government intelligence agency will be affected.

AES is quantum resistant, much like Sha256.

The elliptic curve encryption bitcoin uses isn't considered to be quantum proof but it's not hard to change algorithms and only addressed that have spent funds are vulnerable (a lot of people should be unaffected by that unless you're using wallets with only a few addresses - after spending from an address, your funds are often sent to "change" addresses too).

[BitDane]

It has been established by several discussions that Quantum Computer needs many years before they can crack Bitcoin security[1][2][3], of course Bitcoin security algorithm will be adjusted once the developer felt that there is a need for adjustment even before Quantum computer cracks Bitcoin's security.  But media is stubborn enough to make any development of Quantum Computer related to Bitcoin security issue. Isn't the news a good timing for Bitcoin's a little bit of market recovery?  It looks like someone is pulling some strings to keep Bitcoin in the current price or aim to pull it lower.


[1] https://decrypt.co/101340/bitcoin-quantum-computing
[2] https://cointelegraph.com/news/why-quantum-computing-isn-t-a-threat-to-crypto-yet
[3] https://www.newscientist.com/article/2305646-quantum-computers-are-a-million-times-too-small-to-hack-bitcoin/

[o_e_l_e_o]

Did it say what size RSA the researchers were able to crack?

They weren't able to crack any size of RSA key.

The largest number they were able to factorize was 48 bits. The minimum recommended size for RSA keys is 2,048. They weren't even close, even to older 1,024 keys which are still in circulation. The RSA-100 number, which has 330 bits, was factorized in 1991, and can be factorized on a modern computer in a matter of minutes. 48 bits isn't even close to this number either.

The whole thing is a clickbait nothing burger. The difference between 48 bits and 2,048 bits really can't be understated. It would be like newspapers in 1969 announcing we had colonized the solar system after landing on the moon.

and only addressed that have spent funds are vulnerable

That's not quite accurate. There are also millions of coins in old style P2PK outputs which are vulnerable, and since taproot no longer hashes public keys then coins in P2TR outputs are vulnerable as well. Not to mention all the public keys which have been revealed through other means, such as SPV wallets, watch only wallets, payment processors, signed non-transaction messages, etc. And obviously the public keys which will be revealed as soon as a transaction is broadcast. Relying on the public key being hashed is a poor defense against quantum computers. Rather we will implement some quantum resistant scheme when the time comes.

[dansus021]

Exactly this. New users keep asking this again and again in the forum and it's the same answer again and again. IF RSA gets broken. BTC is going to be the least of the issues. The credit card industry would implode, followed by the banking industry followed by everything else that relies on encryption for transactions. BTC is such a small part of that to make it not worth mentioning.

-Dave

yeah I saw it too and a bunch of it,
and I do believe before its gonna happen bitcoin and the other already creating some new encryption way more secure than RSA beside that quantum is early technology

"Quantum computers are known to be a potential threat to current encryption systems, but the technology is still in its infancy. Researchers typically estimate that it will be many years until quantum computers can crack cryptographic keys — the strings of characters used in an encryption algorithm to protect data — faster than ordinary computers." - https://www.nature.com/articles/d41586-023-00017-0

But we will doomed if AI with brain of quantum computer exist 

[pooya87]

It is also worth pointing out that even the 2048-bit RSA key is less secure than a 256-bit EC key (112 vs 128). Don't be fooled by the bigger number, RSA keys provide a lot less security. The only significance of the article is the algorithm they used and how they reduced the number of qubits required, not that we are any closer to breaking actual keys in use in the near future.

[Kakmakr]

You know that most secure services like SSL on websites and also services used by the Banking sector and other financial services use RSA Encryption technology ... right?

So why do you think this FUD is only targeted at Bitcoin as a huge threat? I will tell you why, because Bitcoin is a threat to the people who are spreading this FUD... because they want the uniformed slaves of their financial system .... to fear Bitcoin. (even if this is a bunch of lies)

Just get the truth out there... and how we already solved this possible threat, with counter measures.  

[Carlton Banks]

It is also worth pointing out that even the 2048-bit RSA key is less secure than a 256-bit EC key (112 vs 128). Don't be fooled by the bigger number, RSA keys provide a lot less security. The only significance of the article is the algorithm they used and how they reduced the number of qubits required, not that we are any closer to breaking actual keys in use in the near future.

right, improving the algorithm isn't so impressive when the hardware that could use the improved algorithm is still infeasible

[o_e_l_e_o]

You know that most secure services like SSL on websites and also services used by the Banking sector and other financial services use RSA Encryption technology ... right?

There is a difference here in that a centralized service such as a bank can much more easily swap to a new quantum resistant technology than we can on bitcoin. They can simply update their back end, as opposed to needing to hard fork an entire decentralized network. Further, they don't have to care about some of the same considerations that we do. Take Lamport signatures as an example. They should only ever be used once, as each subsequent signature makes it easier and easier for an attacker to forge a signature. For bitcoin this would mean a huge overhaul of how wallets (or even the whole network) works to prevent anyone from using the same address more than once. For a bank, then can just generate new keys as needed. Or the fact that Lamport public keys and signatures can be dozens of kilobytes in size. Irrelevant for a centralized service, but catastrophic for bitcoin blocks.

While quantum computers pose no risk to bitcoin at the moment, and won't for many years to come, we will have some of the most specific demands when it comes to selecting a quantum resistant algorithm to use.

[AicecreaME]

Quantum computer is a threat to cyber security, because it could be use to something bad or good, like massive security breaches all over the globe. But if the technology evolves the security also evolves, NIST is the one who are preparing for PQC to avoid such things, it is called quantum-resistant cryptographic standards, that must be adopted to prevent everything that could be gone wrong.

[HomerF_48]

BTC is not quantum secure. IBM will have a QC of 4,000+ qubits by 2025 (in two years). It takes only 1556  qubits to break the ECDSA encryption used to correllate private to public keys. What this means is if you have an exposed (unhashed) public key - which if you ever used your wallet it leaves an unhashed copy of your public key out there on the network for anyone to have - a quantum computer of 1556 or more qubits can take that public key and reverse engineer out your private key. Game over. Bitcoin has no value other than as a way to Secure information - security is literally its only selling point - when that security breaks, as it will, it has no more usefulness and the value will crash to probably just a few dollars, propped up by die-hard dead-ender BTC maxis. If you want to get rich on bitcoin, short it by buying a short bitcoin etf (example is ticker BITI - not financial advice). Doing anything else will result in losing investment.

Google this / do your own research - this is not "FUD", this is just sober fact. Bitcoin public keys can fall with QC's of just 1556 qubits. (Source: https://security.stackexchange.com/questions/33069/why-is-ecc-more-vulnerable-than-rsa-in-a-post-quantum-world ). Misinformation you hear is that it takes many qubits to crack RSA hence bitcoin is safe - this only relates to the bitcoin mining algorithm not the ECDSA algorithm used to relate public/private keys which is more vulnerable. Again - in 2 years or so IBM will have QC strong enough to reverse engineer private key from unhashed public key. When this happens panic will spread and bitcoin will crash. This is as predictable as the housing bubble collapse of 2008 and just like then, there are people who will shout "FUD" at anyone showing the plain and simple facts. Don't be on the wrong side of this.

[Carlton Banks]

if you ever used your wallet it leaves an unhashed copy of your public key out there on the network for anyone to have - a quantum computer of 1556 or more qubits can take that public key and reverse engineer out your private key.

how fast will this quantum computer be able to factorize the public key into it's private key? it has to be faster than a miner can mine transactions transferring to a quantum resistant keypair.

also, don't forget that miners will want to continue to mine, so if a new keypair scheme is available, one can simply send (encrypted) transactions directly to a miner, transferring utxos to a new address using the new scheme, IBM cannot crack public keys they do not have access to.

what's that you say, the quantum resistant keypairs don't exist? well neither does IBM's 4000 qubit computer (and some kind of quantum resistant keypair cryptography does exist, although I have no idea how good it is, nor whether it's at all suitable for Bitcoin addresses/tx's)

did you say game over?

[BitcoinPanther]

Google this / do your own research - this is not "FUD", this is just sober fact. Bitcoin public keys can fall with QC's of just 1556 qubits. (Source: https://security.stackexchange.com/questions/33069/why-is-ecc-more-vulnerable-than-rsa-in-a-post-quantum-world ). Misinformation you hear is that it takes many qubits to crack RSA hence bitcoin is safe - this only relates to the bitcoin mining algorithm not the ECDSA algorithm used to relate public/private keys which is more vulnerable. Again - in 2 years or so IBM will have QC strong enough to reverse engineer private key from unhashed public key. When this happens panic will spread and bitcoin will crash. This is as predictable as the housing bubble collapse of 2008 and just like then, there are people who will shout "FUD" at anyone showing the plain and simple facts. Don't be on the wrong side of this.

Do not disregard that the developers are well aware of this scenario and I believe they will not get idle and just wait for these so called quantum computer to break the Bitcoin security.  Because before Bitcoin, I believe there are lots of low security that will be cracked first giving a hint that there is a need of an upgrade of security for Bitcoin  hence the possibility of your speculation or prediction might not happen.  

I think as the quantum computer progress and develop, securities also evolve and develop.  So it is a race and not just a one sided race where QC are the only one progressing.

[Carlton Banks]

before Bitcoin, I believe there are lots of low security that will be cracked first giving a hint that there is a need of an upgrade of security for Bitcoin  hence the possibility of your speculation or prediction might not happen.

or look at this way: anyone producing a sufficiently powerful quantum computer probably has big interest from the "local military" so to speak.

because that kind of equipment has military implications; whichever political faction who obtained such a tool first could use it to:

• outright attack enemies
• blackmail them instead

it would be a world changing event, if it came out of a clear blue sky (i.e. unexpectedly). One could pwn everything and everyone with such tech, a whole new era would begin rather abruptly

guess what though? everyone to which any of this is relevant already knows, and is preparing accordingly. Bitcoin devs are only one out of many who are aware, and they don't even have any (known) military connections

[o_e_l_e_o]

how fast will this quantum computer be able to factorize the public key into it's private key? it has to be faster than a miner can mine transactions transferring to a quantum resistant keypair.

That is something which is suspiciously missing from the paper linked to by OP as well. It's all well and good saying "We have a xxx qubit computer which can solve the ECDLP for 256 bit private keys", but if you have to run your xxx qubit computer for ten years to find a single private key, then it isn't going to pose much of a risk to bitcoin.

well neither does IBM's 4000 qubit computer (and some kind of quantum resistant keypair cryptography does exist, although I have no idea how good it is, nor whether it's at all suitable for Bitcoin addresses/tx's)

There are quite a few in development: https://en.wikipedia.org/wiki/Post-quantum_cryptography

The last discussion regarding quantum computers on the mailing list I am aware of is from April last year: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020209.html
This discussion focuses on NTRU, which is a lattice-based algorithm: https://en.wikipedia.org/wiki/NTRU

Picking one now, when the threat from quantum computers is very likely still decades away, seems very premature though. There is a good chance that whatever we picked today would be at best outdated and at worst insecure by the time it actually mattered.

[Carlton Banks]

Picking one now, when the threat from quantum computers is very likely still decades away, seems very premature though. There is a good chance that whatever we picked today would be at best outdated and at worst insecure by the time it actually mattered.

for Bitcoin, yes. For protocols that involve encrypting network packets using public keys, it might make sense to pick now (and I believe this is the reason OpenSSH did so). I do not know why it doesn't make more sense to extend/redesign the protocol to encrypt using negotiated ephemeral encryption keys, but maybe that's something specific the protocol.

[NotATether]

Picking one now, when the threat from quantum computers is very likely still decades away, seems very premature though. There is a good chance that whatever we picked today would be at best outdated and at worst insecure by the time it actually mattered.

for Bitcoin, yes. For protocols that involve encrypting network packets using public keys, it might make sense to pick now (and I believe this is the reason OpenSSH did so). I do not know why it doesn't make more sense to extend/redesign the protocol to encrypt using negotiated ephemeral encryption keys, but maybe that's something specific the protocol.

I still can't believe why the bitcoin protocol isn't using end-to-end encryption between nodes using self-signed certificates. That would prevent information leak that someone would harvest and attempt to break a specific ECDSA key.

[Blawpaw]

https://news.bitcoin.com/chinese-researchers-claim-success-in-breaking-rsa-encryption-with-quantum-computer-experts-debate-veracity-of-discovery/

Is this true? A Quantum computer could break RSA encryption now? I thought it should take another 10 years at least

Quantum computing is still years behind, so it is still an unique way computation that cannot interact withthe current computational model. This means that it still cannot be used to break any sort of encription used in tje current computation plane. Therefore, I believe the article is just plain and simple FUD. Nevertheless, it doesnt. Mean that we should stay unwoorried. On the contrary,  quantum computing is evolving and will soon get there, but as someone already mentioned, when that so happens, encryption will also evolve to cope with it. At least I hope so!

[Blawpaw]

https://news.bitcoin.com/chinese-researchers-claim-success-in-breaking-rsa-encryption-with-quantum-computer-experts-debate-veracity-of-discovery/

Is this true? A Quantum computer could break RSA encryption now? I thought it should take another 10 years at least

Quantum computing is still years behind, so it is still an unique way computation that cannot interact withthe current computational model. This means that it still cannot be used to break any sort of encription used in tje current computation plane. Therefore, I believe the article is just plain and simple FUD. Nevertheless, it doesnt. Mean that we should stay unwoorried. On the contrary,  quantum computing is evolving and will soon get there, but as someone already mentioned, when that so happens, encryption will also evolve to cope with it. At least I hope so!

[Carlton Banks]

I still can't believe why the bitcoin protocol isn't using end-to-end encryption between nodes using self-signed certificates. That would prevent information leak that someone would harvest and attempt to break a specific ECDSA key.

that's on the table with BIP324 (except without the certificates part, any authentication has been left easy to add, but not actually specified)

but I'm not convinced that would help, transactions are propagated to all nodes, so the attack is really the same: start a node, listen for transactions to get valid public keys, crazily try to factorize the private key out of any pubkey from the instant you receive it

even directly connecting to a miner IP with bitcoind set to refuse anything but a BIP324 connection wouldn't work for the same reason; the miner would broadcast your transaction to it's peers, then onto the rest of the bitcoin network.

[franky1]

quantum computers cant reverse engineer public-> private in seconds.
its still going to be a several hours-days(compared to thousands of millenia) thing even with the high qubit rate this topic link mentions

so the fear of someone grabbing a zero-confirm tx at relay. engineer the privkey then RBF the utxo to a new destination, before the original tx confirms.. . is not a concern for a network that confirms much sooner
(still be cautious but dont be fearful. its more super luck, if they manage to engineer a RBF in the average 10min confirm window)

the real concern is leaving valuable amounts/data on a exposed key
EG hoarding on a re-used key.
EG putting valuable data into a message on an app where you dont want anyone reading it later after the fact. but have your encrypted messages stored somewhere to be interrogated later

also those owning a large expensive multibillion dollar system are not going to waste hours on one process that wont net them break even/profit

[justdimin]

Quantum computing is still years behind, so it is still an unique way computation that cannot interact withthe current computational model. This means that it still cannot be used to break any sort of encription used in tje current computation plane. Therefore, I believe the article is just plain and simple FUD. Nevertheless, it doesnt. Mean that we should stay unwoorried. On the contrary,  quantum computing is evolving and will soon get there, but as someone already mentioned, when that so happens, encryption will also evolve to cope with it. At least I hope so!

It may be years to go, but it doesn't solve the problem neither. We have to handle the issue first that such a trouble is out there upcoming one day and we do not have a solution to it. Well, we do but not implemented yet, we need to make sure that we could implement such a change if we could and that will definitely be a lot better for our ease of mind.

I am not saying that it's going to be a trouble forever, but it's going to end up being something we could handle in the long run if we are ready for it. This is why quantum computing is a risk even when it's not there yet, even when it's just worked on, maybe there is some time to go, but that is just the reality.

[franky1]

here is another thing to think about in relation to the topics fear mongering..

RSA has already been "broke" by conventional binary computing at 256, 512 and 786.. from as early as 2000-2010
https://link.springer.com/chapter/10.1007/3-540-45539-6_1
https://eprint.iacr.org/2010/006.pdf
(using 1500 cpu hours)

so by knowing the secret methodology.. ofcourse speeding up that reverse engineering method to break 1024, 2048 4096 just becomes a time factor
also the fact is.. RSA is not one-way cryptography. RSA is made to be decrypted. because its encryption. used for messages. not one way signing proofs

ECDSA is different and stronger. thus able to withstand a brute attack at 256(EC) which would take longer than grains of sand in the universe(eons).. vs 1500years of CPU time of 768bit RSA