Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

arxiv.org

Post reply on HN
Print view View original

91–100 of 146 posts

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#91

Post by AlanYx »

reikonomusha wrote: post #85
kjrose wrote: post #23

It's an interesting theory but like most items in quantum computing it is purely theoretical. Not sure how much it would cost to build. I hope someone gets a grant to work out the engineering difficulties in this.

I would say most items in quantum computing are not theoretical. They’ve been demonstrated. Moreover, quantum physics is by far our most accurate theory of physics we have What is still hypothesized is whether these elements, which have been demonstrated to work in small numbers (<100), will work in large numbers.

Until someone successfully demonstrates an error-corrected qubit, it's probably fair to still call a lot of work in the quantum computing realm theoretical.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#92

Post by DarmokJalad1701 »

azatris wrote: post #56
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

I do not know much about quantum computing. But could you explain what makes these computers quantum? Is it the configuration of these transistors to invoke some quantum phenomena?

Here is a long-ish video that explains quantum computers without using pop-science hand-wavy terminology

https://www.youtube.com/watch?v=F_Riqjdh2oM

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#93

Post by mabbo »

gjm11 wrote: post #74
jakozaur wrote: post #70

One day you can start calculating private keys based on public keys. This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle. This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).

Imagine that you find Satoshi's private key and start trying to sell his million bitcoins. Approximately one minute after you start this process, someone will figure out that either (1) bitcoins no longer securely belong to anyone or (2) Satoshi thinks selling off all his bitcoin is a good idea. Approximately two minutes after you start this process, the price of bitcoin will plummet. Sorry, you will not be taking ho…

You're not thinking big enough.

Anyone can sell bitcoins and make money. But if you have the power to destroy bitcoin, well then you can short the entire bitcoin market and clean up.

Frankly, I would just walk into the door of a large hedge fund and sell them to the key for $5B. They'll do far better than I ever could, and $5B is more money than I can possibly use in my lifetime, while being a tiny cost of business for them.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#94

Post by Itsdijital »

gjm11 wrote: post #74
jakozaur wrote: post #70

One day you can start calculating private keys based on public keys. This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle. This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).

Imagine that you find Satoshi's private key and start trying to sell his million bitcoins. Approximately one minute after you start this process, someone will figure out that either (1) bitcoins no longer securely belong to anyone or (2) Satoshi thinks selling off all his bitcoin is a good idea. Approximately two minutes after you start this process, the price of bitcoin will plummet. Sorry, you will not be taking ho…

There is a theory that the key to satishi's wallet is hidden somewhere in the beginning of the blockchain. So it might not be too wild if coins started moving

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#95

Post by CodesInChaos »

PeterisP wrote: post #90
hannob wrote: post #36

Earlier quoted context omitted.

That's not how this works. An attacker can record the key exchange. That is not using RSA, today it's usually some variation of elliptic curve diffie hellman. But that is just as vulnerable to quantum attacks as RSA. So you're attacking the key exchange, not the RSA signature. What you're probably alluding to here is the forward secrecy property of TLS. But that is only true under the assumption that the key exchange…

Interesting, I had assumed that the whole purpose of Diffie-Hellman and the like is to ensure that the ephemeral keys which are generated during the process can't be recovered from recorded traffic even if you later find out the private keys used by the parties. Or is it the case that it's secure from just knowing the private keys, but efficient factorization e.g. Shor's algorithm can break the whole process?

The server holds the private key associated with the certificate for a long time.

If you don't use ephemeral keys that means that compromising the sever (hacking, subpoena, etc) that will allow an attacker to decrypt any session they recorded which used that long term key.

If you use ephemeral keys, the attacker needs to learn the ephemeral private key instead of the long term private key to decrypt the session. The server throws away the ephemeral private key (plus the symmetric session key) after a short time. So a later compromise of the server will not allow an attacker to decrypt old sessions.

An attacker who can break the underlying cryptography on the other hand can still break the ephemeral keys used for the connection, since they (unavoidably) learn the public key from the handshake. It might increase cost, because they need to break each connection separately, but at that point the security margin is terribly thin.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#96

Post by upofadown »

hk1337 wrote: post #18
stirlo wrote: post #2

Just to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.

So, then I am definitely good using 4096 RSA?

Sure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size:

* https://www.schneier.com/blog/archives/2017/05/post-quantum_...

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#97

Post by dcow »

Strilanc wrote: post #88
thesz wrote: post #82

Earlier quoted context omitted.

You are off by orders of magnitude. The difference in memory density between DRAM and SRAM (register file) is not 100 times, more like 10x. Standalone "registers" - memory elements of pipelines, state machines etc, - are again not more than ten times less denser than SRAM. After DRAM goes SSD and after SSD goes disk. The difference in price per GB for SSD and disk is about four (4x) times, I looked for that numbers r…

Are you sure? I was just going off a quick search of Amazon, where 1 GB of ram cost ~30$, 1 TB of disk cost ~50$, and a CPU with ~1MB of L2 cache cost ~200$. Based on that I actually thought 100x was a comfortable underestimate, not an overestimate.

CPU cost is not dominated by the cache size is the problem, I think.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#98

Post by IncRnd »

MichaelMoser123 wrote: post #51
tbabej wrote: post #12

This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).

interesting qeustions that is not related to the feasibility of this idea: would this news item cause some more fluctuations in the rate of digital currencies?

The results of this could, however this is simply theoretical at the current time.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#99

Post by IncRnd »

dzdt wrote: post #9

Quantum computers of this scale are probably 5-15 years out. Basically this is a warning that if you have secrets that should still be kept secret over that timeframe, you should not be using RSA today.

Five years is incredibly close for this type of computer to be built!

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#100

Post by IncRnd »

PeterisP wrote: post #19
carlmr wrote: post #13

Earlier quoted context omitted.

Even if it was, 177days for cracking your password with the most advanced technology that exists in the world, still means you have some very powerful enemies. Practically you don't need to think about it.

I.e. you can solve it by rotating your keys/certificates every 90 days, like the expiry term given by Letsencrypt.

Unfortunately, this doesn't solve the complete issue.

Consider that Internet traffic is recorded today and has been for some time. This means that the certificate rotation isn't the entire solution. Algorithm types and sizes along with ephemeral certificates should be considered.

Post reply on HN