Researcher Claims to Crack RSA-2048 With Quantum Computer

[larry_vw_1955]

https://www.bankinfosecurity.com/blogs/researcher-claims-to-crack-rsa-2048-quantum-computer-p-3536
As Ed Gerck Readies Research Paper, Security Experts Say They Want to See Proof

 We all knew this day was coming sooner or later but I guess we didn't realize it would be done without shors algorithm  
 Bitcoin should still be good since it doesn't require factoring large numbers

[1714302030]

1714302030

[1714302030]

1714302030

[1714302030]

1714302030

[NotATether]

Doesn't look like he actually did it:

Gerck said all his "QC computations were done in a commercial cellphone, or a commercial Linux desktop," at a capital cost of less than $1,000. "No cryogenics or special materials were used."

I mean, if anybody can demonstratively use this method to break RSA-2048 on my Elitebook 6930p, I will be amazed. But it won't happen.

[pooya87]

We all knew this day was coming sooner or later

You mean the day when someone claims they may theoretically crack a cryptography algorithm? That day came thousands of years ago when the concept of cryptography was introduced.

[ymgve2]

Current cellphones and desktops can't do quantum computing, so dude's full of ****

[o_e_l_e_o]

Anton Guzhevskiy, the chief operating officer at Australian cybersecurity firm ThreatDefence, also challenged Gerck to prove his claims. "I've shared an RSA-2048 public key and a corresponding private key encrypted by this public key. If you can decrypt the private key, you can sign some piece of text with it, which will prove that you are in possession of the private key," he said in a response to Gerck's post on LinkedIn. "Can you do it?"

"There is a publication delay, and I do not control that," Gerck responded.

Says it all really.

This sounds like CSW all over again. Ask for a signed message as proof, which would be trivially easy to provide if any of the claims were true, and instead be told that we have to wait for some paper or evidence to be published which will "totally prove it".

I won't be holding my breath.

[ABCbits]

Since we're in Bitcoin forum, IMO phrase "Don't trust, verify" is appropriate for claim of that researcher.

Anton Guzhevskiy, the chief operating officer at Australian cybersecurity firm ThreatDefence, also challenged Gerck to prove his claims. "I've shared an RSA-2048 public key and a corresponding private key encrypted by this public key. If you can decrypt the private key, you can sign some piece of text with it, which will prove that you are in possession of the private key," he said in a response to Gerck's post on LinkedIn. "Can you do it?"

"There is a publication delay, and I do not control that," Gerck responded.

Says it all really.

This sounds like CSW all over again. Ask for a signed message as proof, which would be trivially easy to provide if any of the claims were true, and instead be told that we have to wait for some paper or evidence to be published which will "totally prove it".

I won't be holding my breath.

And based on what i found, it looks like that researcher currently or used to be owner or that publication. This is what i did,
1. Read news mentioned by OP which mention https://www.researchgate.net/publication/373516233_QC_Algorithms_Faster_Calculation_of_Prime_Numbers.
2. Research Gate says that researcher is part of "Planalto Research".
3. From DuckDuckGo search result, i found this LinkedIn page for "Planalto Research" which can be seen at https://www.linkedin.com/company/planalto-research.
4. That LinkedIn page mention http://gerck.com .
5. I can't access http://gerck.com , but archived page on archive.org show this,

© Ed Gerck, 2001-2015.

So i agree it's like CSW again. CMIIW.

[DaveF]

Yeah, it's just another scammer looking to scam.
But, I'm sure some people will follow him and buy the 'non crack-able device' that he will be selling soon.
Or the magic security box that will not allow for this to happen to YOU.

Not worth thinking about since there are better scammers then this out there.

-Dave

[larry_vw_1955]

And based on what i found, it looks like that researcher currently or used to be owner or that publication. This is what i did,
1. Read news mentioned by OP which mention https://www.researchgate.net/publication/373516233_QC_Algorithms_Faster_Calculation_of_Prime_Numbers.

All our computations were done in a commercial cellphone, or a commercial Linux desktop, as our QC devices -- opening the user market to many industries. No cryogenics or special materials were used. A post-quantum, HIPAA compliant, end-to-end, patent-free, export-free, secure online solution, is being created, based on ZSentry as used from 2004 to 2014, to replace RSA.



the first part doesn't even sound believable to anyone that know about the difficulty of factoring. the second part sounds like someone that had a little too much to drink.

well i guess this was a false alarm. but at some point in the future, we should expect to see a story with this exact title where they actually provide the factorization. and i wouldn't be surprised if it was in the next 5 years. but it could be 10.  

and yeah, this guy gives off Craig Wright vibes. for sure.

[o_e_l_e_o]

1. Read news mentioned by OP which mention https://www.researchgate.net/publication/373516233_QC_Algorithms_Faster_Calculation_of_Prime_Numbers.

Wait wait wait. I'm just reading this in a bit more depth.

We factored numbers with more than 10¹⁰⁰⁰ decimal digits, and the capital cost was less than $1,000.

Because the formatting is messed up I originally read that as 101000, but it's actually 10¹⁰⁰⁰. There is not enough computing power in the entire world to even store a number with 10¹⁰⁰⁰ digits, let alone even think about beginning to attempt to factorize it. In fact, much like Graham's number, even if every digit of such a number was stored in a single Planck volume, the entire universe would be too small to represent such a number. But this man has factorized such a number on a mobile phone? Lol.

[tromp]

We factored numbers with more than 10¹⁰⁰⁰ decimal digits, and the capital cost was less than $1,000.

There is not enough computing power in the entire world to even store a number with 10¹⁰⁰⁰ digits, let alone even think about beginning to attempt to factorize it.

Here's a number with more than 10¹⁰⁰⁰ decimal digits:

10¹⁰¹⁰⁰⁰

And here's its factorization:

2¹⁰¹⁰⁰⁰ * 5¹⁰¹⁰⁰⁰

My capital cost was not even $1

[DaveF]

And based on what i found, it looks like that researcher currently or used to be owner or that publication. This is what i did,
1. Read news mentioned by OP which mention https://www.researchgate.net/publication/373516233_QC_Algorithms_Faster_Calculation_of_Prime_Numbers.

All our computations were done in a commercial cellphone, or a commercial Linux desktop, as our QC devices -- opening the user market to many industries. No cryogenics or special materials were used. A post-quantum, HIPAA compliant, end-to-end, patent-free, export-free, secure online solution, is being created, based on ZSentry as used from 2004 to 2014, to replace RSA.



the first part doesn't even sound believable to anyone that know about the difficulty of factoring. the second part sounds like someone that had a little too much to drink.

well i guess this was a false alarm. but at some point in the future, we should expect to see a story with this exact title where they actually provide the factorization. and i wouldn't be surprised if it was in the next 5 years. but it could be 10.  

and yeah, this guy gives off Craig Wright vibes. for sure.

Not even close to that time-frame. As @o_e_l_e_o  pointed out that is an insane amount of data.
This is the same as the magic carburetor that allowed you to get 200 miles to a gallon of gas in your 2 ton truck, it just can't be done.

Things like this will keep coming up again and again and yet it never seems to happen. Nor will it.

-Dave

[satscraper]

The claim of RSA-2048 breaking with commercial phone has reminded me the declaration  on achievement of the cold nuclear fusion published, back in the past,  in  one  of the reputable scientific journals.

Guess what happened next. Right, it was proved that authors of that paper fell into illusion.

Both cases have in common their tendency towards wishful thinking.

[gmaxwell]

If you could crack RSA-2048 there are several very well known public challenges that you could break (one of which has a $200k prize, IIRC).  Anyone who claims to be able to crack RSA and doesn't prove it should just be disregarded.  It's not even worth reading the rest of their claims without the proof.

If they were instead saying they could reduce it to 2^80 work through some mathematical breakthrough, making it vulnerable but not *easily* cracked that would be another matter... but these posts talk about cracking it on a cell phone.

Looking at this I don't think the source is a scammer, but his posts are clearly nonsense.  We all need to keep in mind that *everyone* is online today.  Children, scammers, smart people, dumb people, trolls, and people who are delusional too and the lines between the classes aren't always crisp.

In the days before the internet with smaller communities, you'd learn what people tend to be unreliable sources of information.  But now everyone you hear from is a stranger, and you usually don't know what weight to give their claims.

Ironically the specific nonsense here-- path tracing quantum computation running efficiently on a classical computer is strikingly similar to VB's old quantum miner scam.  In that case it was much more clearly a scam rather than someone who is confused.

[larry_vw_1955]

Not even close to that time-frame. As @o_e_l_e_o  pointed out that is an insane amount of data.

i wasn't talking about the 10^1000 number. i was just talking about 2048-bit integers. big difference. 2048-bit numbers are still pretty big but they're only about 600 base 10 digits. that's it! plenty of room to store it on a computer and do alot of calculations on it.

Things like this will keep coming up again and again and yet it never seems to happen. Nor will it.

-Dave

they might not factor 10^1000 size numbers but 2048 bit numbers are an entirely different animal and should be vulnerable to quantum computers at some point. very vulnerable. the only question is, when do companies like atom computing scale up past 1000 qbits to say 1 million qbits. i'd say in the next 10 years at worst.
they went from 100 qbits to 1000 in like 2 years.

https://arstechnica.com/science/2023/10/atom-computing-is-the-first-to-announce-a-1000-qubit-quantum-computer/
For Atom itself, the step up from 100 to 1,000 qubits was done without significantly increasing the laser power required. That will make it easier to keep boosting the qubit count. And, Bloom adds, "We think that the amount of challenge we had to face to go from 100 to 1,000 is probably significantly higher than the amount of challenges we're gonna face when going to whatever we want to go to next—10,000, 100,000

If you could crack RSA-2048 there are several very well known public challenges that you could break (one of which has a $200k prize, IIRC). 

That challenge ended in 2007. I guess RSA started getting worried they might have to pay out on some of the larger cash prizes like the $100k prize for RSA-1024....
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

[j2002ba2]

they might not factor 10^1000 size numbers but 2048 bit numbers are an entirely different animal and should be vulnerable to quantum computers at some point. very vulnerable. the only question is, when do companies like atom computing scale up past 1000 qbits to say 1 million qbits. i'd say in the next 10 years at worst.
they went from 100 qbits to 1000 in like 2 years.

You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory. Current QC hardware struggles with RSA-6 (six bits).

Finally someone did put the noise into quantum equations and this is the result:

We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n - the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1−o(1) over random prime pairs (p,q), Shor's factoring algorithm does not factor numbers of the form pq, with the same level of random noise present.

[tromp]

You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory.

Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits.

Current QC hardware struggles with RSA-6 (six bits).

The only thing you got right. The current QC factorization record of 21 = 3 * 7 even used some shortcuts for numbers of a special form. So it's fair to say that we have yet to successfully run Shor's algorithm on a QC.

[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm

[j2002ba2]

You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory.

Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits.

This is correct only with ideal noiseless qubits and gates. Shor's algorithm fails when exponentially small noise is present. That is, it needs noise levels of the order 2^-n. The same is true for ECDLP. Good luck achieving noise level 2^-256.

It is very easy to figure out why that happens. We start with qubits which are independent, each representing only 1 bit of information. But before reaching the final result it is not yet clear which of the 2ⁿ possibilities are the correct ones. So midway of the quantum computation, qubits have to represent 2²ⁿ states at the same time. This enormous amount of information vanishes with any noise present.

Read the last sentence in this section https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation.

[tromp]

You got it wrong. RSA-2048 is not vulnerable to QC even theoretically.

Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits.

This is correct only with ideal noiseless qubits and gates.

That's exactly what a "theoretical QC" is. Hence, your claim of "not vulnerable to QC even theoretically" being wrong.

[j2002ba2]

You got it wrong. RSA-2048 is not vulnerable to QC even theoretically.

Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits.

This is correct only with ideal noiseless qubits and gates.

That's exactly what a "theoretical QC" is. Hence, your claim of "not vulnerable to QC even theoretically" being wrong.

Shor's algorithm with noiseless qubits and gates works in theory.
Shor's algorithm with noisy qubits and gates does not work in theory. It needs exponentially small noise.
Both in theory.
That's it.

[jvanname]

I personally ignore most quantum computation because quantum computing is overhyped. Think about it. Quantum computing promises exceptional speedup for some specific problems. Reversible computing promises moderate speedup for all problems. It is important to get better at computing everything and also to try to get an exceptional speedup for specific tasks. But quantum computing has been overwhelmingly hyped while few have heard of reversible computing. This is not good since the old strategy of simply shrinking transistors and making everything smaller is not going to work any more. This means that we will need another strategy for improving performance in computation, and partially reversible computation is a part of the solution.

Heck, even things that are pretty much impossible like antimatter engines that can propel people to the speed of light are hyped much more than reversible computation. The reason for this is psychological rather than a result of any deficiency of the promises of reversible computation. People are unwilling to accept that the laws of physics may not always make computation easier and in order to compute within the laws of physics and saenergy, one must make tradeoffs between energy efficiency per bit operation and time/space. And the word 'reversible' sounds less magical than the word 'quantum', and people cannot accept that.

For this reason, I am going to ignore any news about quantum computation.

-Joseph Van Name Ph.D.