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

Breaking RSA with a quantum computer?

schneier.com

Post reply on HN
Print view View original

101–110 of 161 posts

Re: Breaking RSA with a quantum computer?

#101

Post by greggarious »

bawolff wrote: post #38
greggarious wrote: post #37

Earlier quoted context omitted.

What practical things can be done once RSA is broken?

Breaking RSA is a practical thing. E.g. forge email (most dkim keys are 1024 bit rsa). Break ssh (depends on key algo chose). Break pgp (depending on settings). Mitm https connections, Etc.

So if you were going to explain it to someone who's less technical, maybe saying "remove HTTPS" would be an oversimplified way to explain?

(I don't think my contacts aren't going to know what SSH or PGP is, if that helps.)

Re: Breaking RSA with a quantum computer?

#102

Post by rezonant »

HWR_14 wrote: post #75
Strilanc wrote: post #61

I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work.…

The difference is Shor is attempting to prove something. This article is by a security researcher who cares about staying ahead of threats. That is, a 10% chance that RSA-2048 was broken means he's screaming about changing to -4096 or another standard. Because he is trying to make security systems reliable. Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being…

It sounds like you are talking about Schneier (the blog author and well known security researcher) and the parent post is talking about the paper Schneier is blogging about. And comparing it to another paper by a different author.

I don't think there was a comparison between Schneier and Shor, or I missed it.

Re: Breaking RSA with a quantum computer?

#103

Post by rezonant »

px43 wrote: post #95
miga wrote: post #87

Earlier quoted context omitted.

It is fair to say, that in security assessment you estimate lower bound on complexity of hacking. Schor proved upper bound.

There are two cryptographers being discussed here. Peter Shor, and (Claus) Peter Schnorr. Neither are Schor.

Shor, Schnorr, Schor and Schneier.

Re: Breaking RSA with a quantum computer?

#104

Post by quotemstr »

greggarious wrote: post #37
gronky_ wrote: post #33

You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap

What practical things can be done once RSA is broken?

Decrypt decades of pre-PFS archived encrypted internet traffic.

Re: Breaking RSA with a quantum computer?

#105

Post by HWR_14 »

rezonant wrote: post #102
HWR_14 wrote: post #75

Earlier quoted context omitted.

The difference is Shor is attempting to prove something. This article is by a security researcher who cares about staying ahead of threats. That is, a 10% chance that RSA-2048 was broken means he's screaming about changing to -4096 or another standard. Because he is trying to make security systems reliable. Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being…

It sounds like you are talking about Schneier (the blog author and well known security researcher) and the parent post is talking about the paper Schneier is blogging about. And comparing it to another paper by a different author. I don't think there was a comparison between Schneier and Shor, or I missed it.

I am talking about Schneier. I may have misread the parent post

Re: Breaking RSA with a quantum computer?

#107

Post by bodhiandphysics »

rrjjww wrote: post #25
claytongulick wrote: post #17

Earlier quoted context omitted.

All that would need to happen for this exact scenario to occur would be for anyone, anywhere to find a case where P == NP. [1] P !== NP is a theory that has never been proven, so it very well could happen in reality. This is one of those things that keeps me awake, like Carrington events [2]. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem [2] https://en.wikipedia.org/wiki/Carrington_Event

As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem? To rephrase if this is not the case - what value does solving P = NP provide?

Think about cryptography for a second…. In cryptography you need a problem that if you know the key is fast to decode but if you don’t is really slow… like you would have to search all the possibilities one by one. Such problems are (basically…) called NP. P are all the algorithms that are fast on computers. If P = NP than any problem you could use for cryptography could be decoded fast

Re: Breaking RSA with a quantum computer?

#108

Post by EGreg »

rubberband wrote: post #77
Strilanc wrote: post #61

I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work.…

Let me know if you find such a betting venue... I'll take the same side. I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.

Just deploy a smart contract on, say, Ethereum MainNet.

One side will publish the public keys for RSA and the private key signature can take the money.

The other side will likewise lock up some money, but that money can be moved by a smart contract method after a certain date, if the first account still has money in it. You can have multiple dates, for removing some or all of the money in the multiple bets against it. For example, "$200 that it's cracked by 2004".

The main problem with bets and contests is that the side which knows the private key can simply withdraw the money itself. That’s why you need the private key to be generated by all parties involved in a ceremony.

Re: Breaking RSA with a quantum computer?

#109

Post by ofcrpls »

EGreg wrote: post #108
rubberband wrote: post #77

Earlier quoted context omitted.

Let me know if you find such a betting venue... I'll take the same side. I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.

Just deploy a smart contract on, say, Ethereum MainNet. One side will publish the public keys for RSA and the private key signature can take the money. The other side will likewise lock up some money, but that money can be moved by a smart contract method after a certain date, if the first account still has money in it. You can have multiple dates, for removing some or all of the money in the multiple bets against it…

I want you to plan my next birthday party.

Re: Breaking RSA with a quantum computer?

#110

Post by EGreg »

ofcrpls wrote: post #109
EGreg wrote: post #108

Earlier quoted context omitted.

Just deploy a smart contract on, say, Ethereum MainNet. One side will publish the public keys for RSA and the private key signature can take the money. The other side will likewise lock up some money, but that money can be moved by a smart contract method after a certain date, if the first account still has money in it. You can have multiple dates, for removing some or all of the money in the multiple bets against it…

I want you to plan my next birthday party.

Funny you say that. We did it in 2013: https://qbix.com/docs/users.pdf
Post reply on HN