so just increase to 4096 or 8192 bits or beyond?
Breaking RSA with a quantum computer?
51–60 of 161 posts
Re: Breaking RSA with a quantum computer?
#52Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.
Re: Breaking RSA with a quantum computer?
#53Earlier quoted context omitted.
In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetche…
> we just switch to the one time pad encryption "just". So how do you do the key exchange?
Email it obviously
Re: Breaking RSA with a quantum computer?
#54Earlier quoted context omitted.
I will admit that I have no idea how that would look like. If quantum computer can be as capable as one envisioned in Jormungand, I am not sure if anything short of declaring them a weapon is needed.
Quantum computers aren't magic, they have specific capabilities that can be planned around. Google 'post-quantum cryptography' for current work on quantum resistent algorithms, some of which are already being deployed to production.
Any sufficiently advanced technology is indistinguishable from magic. I will openly say that I not understand it beyond knowing that, in a very general sense, it is not based on ones and zeroes. If I do not understand it, it is difficult for me to wrap my head around it and what it can and cannot do.
It might not be magic, but it might as well be ( and may end up being next hype train ).
Re: Breaking RSA with a quantum computer?
#55A note to cast further suspicion on the immediate risk severity: The researchers indicate use of a computer built with superconducting qubits in the abstract, to that, superconducting qubits present barriers such as - limited coherence time due to common atmospheric muon events, and resulting phonons - limited topological connectivity, further increasing needed coherence time.
Limited coherence time is not explained as simply as "atmospheric muon events". There are a variety of reasons, some environmental, others a result of imperfect fabrication, etc. that contribute to decoherence, gate error, etc.
I know that, but I recall specific literature reflecting the specific effect mentioned[0] and it seems intuitive that the surface area and orientation currently in use for these qubits may potentiate the effect, I think the other effects you list are barriers to other qubit registers as well.
[0] https://ai.googleblog.com/2022/01/resolving-high-energy-impa...
Re: Breaking RSA with a quantum computer?
#56Earlier quoted context omitted.
In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetche…
Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
so print it via pressure into the inside of a sealed envelope? that's how they send me my PIN.
Re: Breaking RSA with a quantum computer?
#57> Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics.
Yeah, that alone is impressive. Schneier led a group that wrote Twofish, which was one of the AES finalists before losing Rijndael.
Re: Breaking RSA with a quantum computer?
#58I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...
I’d be interested to speculate how cryptocoins would fair also, not that it isn’t already a sh1t show XD
Re: Breaking RSA with a quantum computer?
#59Earlier 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?
There are roughly four possibilities for P = NP:
* P != NP. In practical terms, nothing changes.
* Nonconstructive case. The resulting algorithm looks something like some primality test algorithms (which I'll describe): essentially, if a number n is composite, then there is some (X + a)^n = X^n + a in Z/nZ (X is a polynomial here). If you test "enough" a's, then you can prove whether n is prime or composite. A nonconstructive case would mean we have a proof that you only need to test poly(lg n) a's to confirm truth, without necessarily telling which a's you have to test. In this world, there is no practical change to problems--the proof doesn't yield an effective algorithm to actually solve any NP-complete problem.
* Combinatorial algorithm for an NP-complete problem. The good example here is what has been done to prove L = SL. The result is "technically" in L, but the factors in the algorithm run very quickly into "more than the number of atoms in the universe" phase. The goal is to find a memory-less algorithm (can't use a visit stack) that can prove a path between two points in an undirected graph, and it turns out that you can transform the graph into another one that will guarantee that you will visit every node in a certain amount of time. The found result has a new graph that replaces every node with more nodes than exist atoms in the universe, so it technically meets the requirements but is completely and totally impractical. Sometimes people handwave this possibility by saying that once an algorithm is found, people will find better results, but this result hasn't been improved on in close to two decades.
* "Simple" algorithm for an NP-complete problem. This is the result that really, really changes things. Once you get a simple algorithm for one NP-complete problem, you can generally find analogous ways to get simple algorithms for other NP-complete problems. However, the research done to date does suggest that this is perhaps the least likely solution: looking at the "hard" instances of SAT problems, it does seem that there is a certain complexity that is at best reducible via some sort of combinatorical nightmare construction rather than the kinds of decompositions that yields "simple" algorithms.
Re: Breaking RSA with a quantum computer?
#60Earlier quoted context omitted.
Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
I remeber in the very early 2000s, a guy had a stopwatch sized whos-it, and it kept flashing numbers on it. Updated every 5 minutes. Apparently, some cesium based list of numbers, again, was 20 years ago. Point is, it was a one time pad...
You mean this?
https://en.wikipedia.org/wiki/RSA_SecurID
I'm not sure but I don't think this is OTP?