Breaking News
News & Analysis

Quantum Computer May Crack Public-Key Encryption

RSA encryption not immune
3/10/2016 11:24 AM EST
13 comments
NO RATINGS
1 saves
More Related Links
View Comments: Newest First | Oldest First | Threaded View
Page 1 / 2   >   >>
R_Colin_Johnson
User Rank
Author
Re: 256-bit RSA does not need quantum computer
R_Colin_Johnson   3/18/2016 5:19:17 PM
NO RATINGS
Yes, as wave.forest notes, Shor'e quantum formula does crack EEC and more easily than RSA since EEC uses 372- bit security, whereas Monern RSA uses 1024 to 3073.

Terry.Bollinger
User Rank
Author
Re: Quantum computers are analog
Terry.Bollinger   3/14/2016 7:57:31 AM
NO RATINGS
@traneus, you raise a good and simple point that is often overlooked about quantum computing, which is this: The parallel processing of a "superposition of states" that is a major part (but not the only part) of why quantum computing is so fast is in fact pretty much the same thing as what used to be called analog computing. An analog wave form is after all just a superposition of an infinite number of sinusoidal states, so processing that wave in clever ways allows processing power from all of those states at the same time.

In quantum computing those sinusoidals are the different momentum states of the electrons, allowing you in effect to process at one time an "infinite" range of unique electron momentum states in the same circuit, at the same time. (I should note that there is also a more exotic, more powerful, and completely non-classical aspect of quantum computing that involves time. That part of QC cannot be replicated by any type of classical system, pretty much by definition, since only quantum systems can in certain ways be indifferent to the flow of classical time.)

In the old days, pretty much the same idea of processing many electrons states at once was implmented much more robustly by having populations of electrons form classical (vs the much more delicate quantum) wave forms. We called those systems analog computers, and when set up properly they could converge with truly amazing speed to an approxmate result.

And that also is the rub: "approximate" doesn't work when you are trying to factor a very larger number. It has to be exact!

However, there are ways to be clever about all of this by dividing up the problem in ways where you use multiple approximations to build collectively build towards a single well-defined solution. So the problem you raise is very much valid, but not necessarily insurmountable. After all, even we humans with our slow, rather bizarre, and fully classical mix of analog and digital (yes, digital: we use pulse coding to preserve signal levels as they are transmitted along nerves) signal processing are capable at times of exquisite levels of precision through a combination of approximation and feedback that lets us converge to feats such as a precisely thrown major-league baseball. There is no fundamental reason why the larger tool set of quantum computing cannot be also be configured so that despite the approximations and limits on resolution at individual stages of processing, the final result can be very precise indeed.

wave.forest
User Rank
Author
Re: 256-bit RSA does not need quantum computer
wave.forest   3/14/2016 6:05:15 AM
NO RATINGS
@ R_Colin_Johnson

The Shor's algorithm works for ECC as well.

Neither RSA nor ECC is secure under quantum computing. We all know it is coming. The question is "When?"

Your article is very good to raise the awareness.

On the other hand, the "May" in "Quantum Computer May Crack Public-Key Encryption" is not accurate either (LOL). It is not "May" - it is "Will". Your articles shows the advance. This advance is well accepted and this is why we are on post-quantum cryptography.

But, please forgive my picky-ness. Thank you for this very good article.

Navelpluis
User Rank
Author
Re: Quantum Computers *TO* Crack Public-Key Encryption
Navelpluis   3/14/2016 3:52:04 AM
NO RATINGS
@ Colin

You are ABSOLUTELY right. We should not sleep, but see the consequences when all our RSA secrets are on the streets in -perhaps- a couple of years from now. From government point of view this is a no-brainer: They certainly will invest in QC, depending of the regime you are living in -of course. Even for governmental critical communication: They should consider this fact too.

R_Colin_Johnson
User Rank
Author
Re: Quantum computers are analog
R_Colin_Johnson   3/13/2016 4:59:55 PM
NO RATINGS
You may be right there too, but the quantum computer makers claim its only a matter of time :)

traneus
User Rank
Author
Quantum computers are analog
traneus   3/13/2016 4:00:04 PM
NO RATINGS
Quantum computers are analog computers, so are sensitive to noise. I expect that scaling up will turn out to be more difficult than expected.

R_Colin_Johnson
User Rank
Author
Re: 256-bit RSA does not need quantum computer
R_Colin_Johnson   3/13/2016 1:12:01 PM
NO RATINGS
Yes, I think you are right--ECC is definately what those who want their secrets to stay secret should use. I'm not sure if there is a theoretical quantum algorithm for breaking ECC, but there may be. If there is, that would seem to be MIT's obvious next step. Let me contact them and get back to you. Thanks for sharing your expertise in RSA and ECC.

MortenC683
User Rank
Rookie
256-bit RSA does not need quantum computer
MortenC683   3/13/2016 5:35:52 AM
NO RATINGS
Where is the disconnect; As far as I know solving 128bit RSA is done in a few seconds on a standard PC. Seems 512bit RSA is cracked in hours these days. Furthermore, RSA key lenght for secure encryption went from 1024 bits to 2048 bits some time ago and 3072bits is next - if RSA is used at all. Elliptic Curve Cryptpgtraphy is more popular. For ECC 256 bits are still considered OK, but 384 bits is next. I don't think MIT is confued about the difference between RSA and ECC? Can we have an update of this article that clarifies? 

R_Colin_Johnson
User Rank
Author
Re: Quantum Computers *TO* Crack Public-Key Encryption
R_Colin_Johnson   3/11/2016 11:50:17 AM
NO RATINGS
You guys are all missing the point--MIT has cracked RSA and shown the proof of concept for 4-bits. Before this we all "knew"--meaning accepted the speculation--that quantum computers would eventually crack the prime-factor algorithm, but MIT has done it, and shown you step-by-step how to build a quantum computer to do it for any sized key. Yes, its prohibitively expensive now, but D-Wave and a new wave of companies (and nation states) now have explicit instructions on how to build an RSA cracker. Before it seemed to just be a matter of time, but now its proven! The code is cracked now--its just up to you to expand it from 4- to 128-bits using Shor's algorithm as extended by Kitaev. Don't use RSA if you never want your secrets revealed.

wave.forest
User Rank
Author
Re: Quantum Computers *TO* Crack Public-Key Encryption
wave.forest   3/11/2016 10:17:24 AM
NO RATINGS
Of course this is a significant advance, but it is well accepted that quantum computing is coming and will break RSA and ECC. The problem is money and time. So there are post-quantum crypto research.

The title is misleading. ;)

Page 1 / 2   >   >>

Datasheets.com Parts Search

185 million searchable parts
(please enter a part number or hit search to begin)
Like Us on Facebook
EE Times on Twitter
EE Times Twitter Feed