Why does a quantum computer render RSA useless?

[Trurl]

Why does the invention of a quantum computer mean the end of RSA?

 

 

I have seen many sources that claim this, but they never explain the “how.” The one explanation I have read is that they have one of the keys and the way quantum computers work they reveal the pattern only knowing the given part.

 

My question is does this only imply to modern key sizes? What would prevent someone from using a quantum computer to make a gigantic semiprime to factor?

 

 

And do quantum computers explain mathematical patterns? I don’t think by factoring the RSA semiprimes it would find a pattern. Isn’t the quantum computer still just crunching numbers?

 

From my reading, it was said that quantum computers will design a custom key system every time. I understood it as being a sort of geometry that unique to all computers.

 

Combine A.I. and quantum and you have a thinking machine that can manipulate the world through atoms. SFN will now be moderated by the quantum. But that is ok because we can’t keep track of the trillion-digit keys or us finding patterns is no longer needed. Worse yet, we have lost the argument that the world is a simulation. 

[swansont]

1 hour ago, Trurl said:

I have seen many sources that claim this, but they never explain the “how.”

What sources? What, specifically, do they claim?

[KJW]

I don't know the details, but Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. This would allow private keys to be determined from public keys much faster than any known classical algorithm.

 

 

[Trurl]

Several sources have a cliffhanger: quantum computers defeat modern cryptography.

The book article of chapter 2: The Physics of Quantum Information, Bouwmeester, mainly says the man in the middle attack. If Eve has the public key she can use it to compare her plain text to the cipher text.

The article goes on to say how secure quantum ciphers are. A lot of which I don’t understand.

I still don’t know why modern encryption fails. I will research Shor’s algorithm. Thanks for the tip.

There is currently much interest in A.I. and quantum computers. I am trying to branch out to other subjects than RSA.

But both subjects may destroy humanity. I only say this as a fact of science, but isn’t a device that can manipulate atoms and have infinite processing power God?

[Sensei]

The best cryptographic algorithms are ("can be") your own - only you know the details of the algorithm, there are no desktop or mainframe or GPU ready tools that can be used against your data..

Edited December 23, 2023 by Sensei

[StringJunky]

9 hours ago, KJW said:

I don't know the details, but Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. This would allow private keys to be determined from public keys much faster than any known classical algorithm.

As someone put it: from billions to millions of years.

Edited December 23, 2023 by StringJunky

[Sensei]

@Trurl

You seem to be obsessed with RSA and prime number factorization.

1) for illegal activity there are much simpler ways..

2) for legitimate activity, i.e. encrypting your own data in a way that no one will be able to read them, there are much simpler ways.. i.e. you create your own algorithm.. Work for hours..

[swansont]

8 hours ago, Trurl said:

Several sources have a cliffhanger: quantum computers defeat modern cryptography.

The specific claims matter. They probably say something like “a quantum computer with a sufficient number of qubits will be able to crack RSA in a short amount of time”

 

https://arstechnica.com/information-technology/2023/01/fear-not-rsa-encryption-wont-fall-to-quantum-computing-anytime-soon/

“The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in superposition.”

We aren’t anywhere close to having such resources.

[StringJunky]

1 hour ago, swansont said:

The specific claims matter. They probably say something like “a quantum computer with a sufficient number of qubits will be able to crack RSA in a short amount of time”

 

https://arstechnica.com/information-technology/2023/01/fear-not-rsa-encryption-wont-fall-to-quantum-computing-anytime-soon/

“The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in superposition.”

We aren’t anywhere close to having such resources.

The main unknown seems to be whether AI will provide useful hints to the AI solutions, and that affects the projected time.

Edited December 23, 2023 by StringJunky

[MigL]

Do we really need to worry about how the advent of quantum computing will affect any type of encryption just yet ???

Reality check ...

 

[StringJunky]

We are currently at 1000 qbits 2023. By 2030 projections expect 1m qbits. It is estimated one needs 20m to crack 1048 RSA. Apparently, it's about a 1000 doillars a QB. Going to be a while yet

Quote

Scientists and cryptographers have known for two decades that a factorization method known as Shor’s algorithm makes it theoretically possible for a quantum computer with sufficient resources to break RSA. That’s because the secret prime numbers that underpin the security of an RSA key are easy to calculate using Shor’s algorithm. Computing the same primes using classical computing takes billions of years.

The only thing holding back this doomsday scenario is the massive amount of computing resources required for Shor’s algorithm to break RSA keys of sufficient size. The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key requires a quantum computer with vast resources. Specifically, those resources are about 20 million qubits and about eight hours of them running in superposition. 

https://arstechnica.com/information-technology/2023/01/fear-not-rsa-encryption-wont-fall-to-quantum-computing-anytime-soon/#:~:text=The current estimate is that,of them running in superposition.

 

Edited December 26, 2023 by StringJunky

[MigL]

I remember when laptops used to 'burn' your lap.
QCs will give you ( severe ) frostbite, and produce even more wasted power than bitcoin mining.
Maybe after we finally get cheap fusion power ...

I'm not worried about anyone breaking into my encrypted data for a long time to come.

[iNow]

8 minutes ago, MigL said:

I'm not worried about anyone breaking into my encrypted data for a long time to come.

At least not until next Tuesday. 

[StringJunky]

8 minutes ago, MigL said:

I remember when laptops used to 'burn' your lap.
QCs will give you ( severe ) frostbite, and produce even more wasted power than bitcoin mining.
Maybe after we finally get cheap fusion power ...

I'm not worried about anyone breaking into my encrypted data for a long time to come.

LOL! Your sperm will be preserved forever and so will you.

[MigL]

I'm 65 in about 3 weeks.
Don't imagine my sperm count is very high.

Edited December 26, 2023 by MigL

[Trurl]

I guess there is some disagreement on quantum computing. 60 minutes made it sound like it was coming out tomorrow. And there is several sources that say it will break RSA, DSA, and ECDSA.

 

I’ve heard 40 qubits was the highest. But I believe you that it is far off.

 

I see quantum computing as producing too much information. We are going to get an answer and it will be so complex that we will have to assume it is correct. I mean something like how you can’t prove a math theory by crunching numbers.

 

However expanding the amount of different crypto algorithms seems awesome.

BTW, I have not read this book.

 

 

[iNow]

1 hour ago, Trurl said:

I believe you that it is far off.

No offense intended toward MigL, but there’s no reason to accept that claim as valid. 

[swansont]

10 hours ago, Trurl said:

I guess there is some disagreement on quantum computing. 60 minutes made it sound like it was coming out tomorrow. And there is several sources that say it will break RSA, DSA, and ECDSA.

Can you provide those sources?

[Trurl]

Quote

13 hours ago, swansont said:

Can you provide those sources

 

The back of the book picture I posted says  it will break RSA, DSA, and ECDSA.

I have yet to read the book, but it proposes alternatives to modern encryption.

The previous link you posted was the first I saw that said today’s encryption was safe.

I have been listening to Michio Kaku’s book. I haven’t finished but he describes quantum computers as pattern solvers. Uses like mapping dna or folding proteins. He doesn’t say we can do that currently. He does mention Google and Microsoft building prototypes.

[swansont]

8 hours ago, Trurl said:

The back of the book picture I posted says  it will break RSA, DSA, and ECDSA.

“will” is a prediction, i.e. something thar will happen in the future. As discussed, it requires more capability than we currently have. When quantum computers are sufficiently powerful they will be able to do the factoring necessary to break current encryption protocols. We are years away from this happening.

Quote

The previous link you posted was the first I saw that said today’s encryption was safe.

Can you see why these statements are not in conflict with each other?

[AIkonoklazt]

The short of it is that quantum computing solves time complexity (as contrasted to computability, except this one very specific impractical case that was found) which means problems that were previously impossible for ordinary computers only because it would take too long for them to solve would now be able to be solved within a practical time frame. Quantum operations enable what's effectively a massive increase in parallelism, giving huge speedups when they could be made to solve those problems.

The answer would be "perhaps certain varieties of them, but it won't just wipe out RSA in one fell swoop."

Also, there's a big catch. You'd need a "sufficiently powerful" quantum computer to do it, and it's not going to be easy to build one. https://www.technologyreview.com/2019/05/30/65724/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/

[iNow]

37 minutes ago, AIkonoklazt said:

You'd need a "sufficiently powerful" quantum computer to do it

Or several serially linked with that same massive increase in parallelism realized within each. 

[swansont]

!

Moderator Note

Discussion on defeating quantum decryption has been split

https://www.scienceforums.net/topic/133223-cryptography-in-the-age-of-quantum-computers-split-from-why-does-a-quantum-computer-render-rsa-useless/

 

 

[AIkonoklazt]

On 1/5/2024 at 6:53 PM, iNow said:

Or several serially linked with that same massive increase in parallelism realized within each. 

...I don't think that's the way to increase quantum computing performance, since if that were the case it would already been done.

[iNow]

57 minutes ago, AIkonoklazt said:

I don't think that's the way to increase quantum computing performance

It’s either systems the size of football fields or parallelism across multiple networked systems to make additional qbits available. Do you know of a 3rd option (other than marginal code tweaks to change order of operations) to increase performance? 

 

1 hour ago, AIkonoklazt said:

if that were the case it would already been done.

Yes, because if we haven’t done it by today then it’s clearly impossible. There’s simply no other possible explanation for why the work isn’t yet finished right now this second as I type this. None. Zero. 🙈