Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

We are sorry to see you leave - Beta is different and we value the time you took to try it out. Before you decide to go, please take a look at some value-adds for Beta and learn more about it. Thank you for reading Slashdot, and for making the site better!

1978 Cryptosystem Resists Quantum Attack

samzenpus posted more than 4 years ago | from the built-to-last dept.

Security 185

KentuckyFC writes "In 1978, the CalTech mathematician Robert McEliece developed a cryptosystem based on the (then) new idea of using asymmetric mathematical functions to create different keys for encrypting and decrypting information. The security of these systems relies on mathematical steps that are easy to make in one direction but hard to do in the other. Today, popular encryption systems such as the RSA algorithm use exactly this idea. But in 1994, the mathematician Peter Shor dreamt up a quantum algorithm that could factorise much faster than any classical counterpart and so can break these codes. As soon as the first decent-sized quantum computer is switched on, these codes will become breakable. Since then, cryptographers have been hunting for encryption systems that will be safe in the post quantum world. Now a group of mathematicians have shown that the McEliece encryption system is safe against attack by Shor's algorithm and all other known quantum algorithms. That's because it does not depend on factorisation but gets its security from another asymmetric conundrum known as the hidden subgroup problem which they show is immune to all known quantum attacks."

Sorry! There are no comments related to the filter you selected.

Good but not great (1)

alphatel (1450715) | more than 4 years ago | (#33293786)

Don't start feeling too secure about the so-called McEliece encryption system - a candidate for the security of Internet traffic in the age of the quantum computer [science20.com] (2008 article)

Re:Good but not great (5, Informative)

pushing-robot (1037830) | more than 4 years ago | (#33293954)

Feel secure again. Only a variant was broken. [iacr.org]

Re:Good but not great (2, Informative)

alphatel (1450715) | more than 4 years ago | (#33294600)

Feel secure again. Only a variant was broken. [iacr.org]

The date of your document July 2008 precedes the successful decryption in October 2008.

Re:Good but not great (1)

pushing-robot (1037830) | more than 4 years ago | (#33294644)

Which might be why it says:

This attack has been implemented and is now in progress.

Timeless saying applies here... (-1, Redundant)

Pojut (1027544) | more than 4 years ago | (#33293792)

If it can be engineered, it can be reverse-engineered.

Re:Timeless saying applies here... (2, Insightful)

Jack9 (11421) | more than 4 years ago | (#33293824)

> If it can be engineered, it can be reverse-engineered.

How does that apply to this article, in any way?

Re:Timeless saying applies here... (5, Insightful)

da cog (531643) | more than 4 years ago | (#33293882)

It doesn't apply to this article. The way that one typically breaks a cryptosystem is not by reverse engineering (which is not even meaningful here, given that the algorithm is already completely open), but by finding a clever new way to solve the mathematics underlying the system using less information than the designers of the system had thought was needed.

Re:Timeless saying applies here... (5, Insightful)

Frequency Domain (601421) | more than 4 years ago | (#33294132)

Actually, with really hard-core crypto systems there are three traditional ways to break them: 1) rubber hose; 2) dumpster diving; or 3) box of chocolates/bouquet of roses.

Re:Timeless saying applies here... (1)

Ancient123 (724901) | more than 4 years ago | (#33294264)

Mod parent up... It is surprising how true that is.

Re:Timeless saying applies here... (2, Funny)

ae1294 (1547521) | more than 4 years ago | (#33294298)

Actually, with really hard-core crypto systems there are three traditional ways to break them: 1) rubber hose; 2) dumpster diving; or 3) box of chocolates/bouquet of roses.

What no wad of Cash xor hookers & blow?

Re:Timeless saying applies here... (2, Funny)

sznupi (719324) | more than 4 years ago | (#33294618)

W8, why both of them wouldn't work?

Re:Timeless saying applies here... (0)

modmans2ndcoming (929661) | more than 4 years ago | (#33295188)

WTF... OK... I can deal with slashdot being overrun by morns who know little but act big, but now we have to put up with text-ese ? Can't the slashdot admins create a table of symbols to outlaw users from using? Please stick to classics....WTF, IANAL, ROFLMAO, STFU, RTFM, etc. none of this modern crap like W8, UR, et cetera.

Re:Timeless saying applies here... (3, Funny)

ae1294 (1547521) | more than 4 years ago | (#33295342)

WTF... OK... I can deal with slashdot being overrun by morns who know little but act big, but now we have to put up with text-ese ?

His UID is lower than yours so shouldn't it be "I can deal with that slashdot was overrun by morns who knew little when I signed up. (eol)"

Re:Timeless saying applies here... (1)

jcwayne (995747) | more than 4 years ago | (#33295454)

<3

Re:Timeless saying applies here... (1)

ae1294 (1547521) | more than 4 years ago | (#33295526)

I love you too... but it's a secret remember?

Re:Timeless saying applies here... (1)

modmans2ndcoming (929661) | more than 4 years ago | (#33295934)

This is a newer ID. I have been on slashdot since '99

Re:Timeless saying applies here... (3, Interesting)

treeves (963993) | more than 4 years ago | (#33294712)

That falls under the generalization of (3).
(1) Threat/intimidation/violence
(2) Exploit a careless mistake
(3) Bribery/persuasion

I suppose (1) and (3) even could blur together into "influence" (negative and positive).

Re:Timeless saying applies here... (1)

shinzawai (964083) | more than 4 years ago | (#33294878)

In the morning.

Re:Timeless saying applies here... (1)

modmans2ndcoming (929661) | more than 4 years ago | (#33295144)

I don't think XOR is the appropriate logic operator. cash is not mutually exclusive from hookers and dope as a bribe.

Re:Timeless saying applies here... (1)

ae1294 (1547521) | more than 4 years ago | (#33295312)

I don't think XOR is the appropriate logic operator. cash is not mutually exclusive from hookers and dope as a bribe.

True but when you mix the two something odd happens and all of the money gets overwritten with blow somewhere in the FIFO buffer...

Re:Timeless saying applies here... (1)

jcwayne (995747) | more than 4 years ago | (#33295502)

Cash is actually the superposition of hookers and blow.

Re:Timeless saying applies here... (1)

ae1294 (1547521) | more than 4 years ago | (#33295600)

Cash is actually the superposition of hookers and blow.

I purpose we petition for a grant to study this theorem in extreme detail as it just might lead to a grand unifying theory with black jack.

Re:Timeless saying applies here... (1)

SageMusings (463344) | more than 4 years ago | (#33295866)

and hookers. Okay, forget the Black Jack!

Re:Timeless saying applies here... (1, Insightful)

Anonymous Coward | more than 4 years ago | (#33295650)

This exchange is illustrated here:

http://imgs.xkcd.com/comics/security.png

Re:Timeless saying applies here... (1)

Hylandr (813770) | more than 4 years ago | (#33294486)

It doesn't apply to this article. The way that one typically breaks a cryptosystem is not by reverse engineering (which is not even meaningful here, given that the algorithm is already completely open), but by finding a clever new way to solve the mathematics underlying the system using less information than the designers of the system had thought was needed.

So, you're saying 640k should be enough?

- Dan.

Re:Timeless saying applies here... (1)

CarpetShark (865376) | more than 4 years ago | (#33294894)

If it can be engineered, it can be reverse-engineered.

How does that apply to this article, in any way?

I think he's saying that this article does not qualify for reverse-engineering ;)

Re:Timeless saying applies here... (4, Insightful)

kalirion (728907) | more than 4 years ago | (#33293856)

If it can be engineered, it can be reverse-engineered.

That only works for "security through obscurity" type of problems. A good encryption should not be "solvable" - it must be brute forced. The question is how expensive the brute force method is in processing power and time.

Re:Timeless saying applies here... (0)

Anonymous Coward | more than 4 years ago | (#33294082)

Yes, and you crack public key encryption by reverse engineering its specific algorithm as parametrized by its key. It just takes you a while with any algorithm but Shor's.

Re:Timeless saying applies here... (1)

human-cyborg (450395) | more than 4 years ago | (#33295560)

I can engineer a dead flower by leaving a live flower on a table without water for a week. Can you reverse engineer a living flower from that dead flower?

Hidden subgroup problem is under active research (5, Informative)

da cog (531643) | more than 4 years ago | (#33293834)

It is worth noting that solving hidden subgroup problem is a subfield of quantum computing that has been active for a while. Although we can't figure out how to solve it in general, we can solve specific instances of it; for example, I think that factorizing is one such instance.

Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.

The article agrees with you (5, Informative)

fishexe (168879) | more than 4 years ago | (#33294020)

Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.

From TFA:

However, it's worth pointing out that while the new work guanratees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks. It's perfectly possible that somebody will develop a quantum algorithm that will tear it apart as easily as Shor's can with the RSA algorithm. "Our results do not rule out other quantum (or classical) attacks," says Dinh and co.

Re:The article agrees with you (5, Funny)

DarkKnightRadick (268025) | more than 4 years ago | (#33294354)

You read the article?!

Feed him some cat food (3, Funny)

A nonymous Coward (7548) | more than 4 years ago | (#33295440)

Maybe he did, maybe he didn't.

Oh (1)

Ryanrule (1657199) | more than 4 years ago | (#33293844)

I see

ElGamal?? (4, Interesting)

neiko (846668) | more than 4 years ago | (#33293846)

Would ElGamal also be immune since it's based on Discrete Logarithms?

Re:ElGamal?? (1)

Narksos (1111317) | more than 4 years ago | (#33293998)

Would ElGamal also be immune since it's based on Discrete Logarithms?

No, Shor solved the discrete logarithm problem in quantum-polynomial time too.

Can be broken? (0)

Anonymous Coward | more than 4 years ago | (#33293848)

"Can be broken" is a red herring. It is a simple matter to design log-in systems that prevent iterative attempts to test passwords that have been "broken".

The simplest form of security, "security by obscurity" remains effective despite quantum computers and server farms.

It is a mathematical exercise to determine time to "decrypt" a secure area or volume based on iterative password tests.

Even something as crude as a visual word input prior to a Slashdot anon post serves even this hacker-rich community.

Just anon, not coward.

Re:Can be broken? (2, Informative)

Reason58 (775044) | more than 4 years ago | (#33293924)

This is not a brute-force attack. The article refers to a method of deriving the private key from the public key (which is available for anyone to download).

conspiracy theory (4, Interesting)

craftycoder (1851452) | more than 4 years ago | (#33293850)

I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?

Re:conspiracy theory (2, Funny)

Anonymous Coward | more than 4 years ago | (#33293926)

No. Nothing to see here.

If you want to test it (4, Funny)

Atmchicago (555403) | more than 4 years ago | (#33293932)

Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.

Re:If you want to test it (3, Funny)

fishexe (168879) | more than 4 years ago | (#33294050)

Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.

But how will I know they're not just knocking at my door out of a desire to make my acquaintance?

Re:If you want to test it (5, Funny)

c6gunner (950153) | more than 4 years ago | (#33295338)

But how will I know they're not just knocking at my door out of a desire to make my acquaintance?

Easy. If they use your door knocker, they want to make your acquaintance. If they bring their own [gaam.com.au] , they're coming for more than tea and crumpets.

Re:If you want to test it (5, Interesting)

Anonymous Coward | more than 4 years ago | (#33294402)

Even then, they would probably spend a long time creating other circumstances in which to pick you up that would give plausible deniability as to how they caught on.

One can google one's own references as I'm sort of lazy today, but a good example: the British had thoroughly broken Enigma during WWII, and at one point in the war knew where -every- German U-boat was. This created a dilemma for them: should they act on this information, and if so, how to do it without tipping their hand? If they just went and rounded up every single one, it would be pretty obvious that the code had been broken.

What they did, according to the stories, is send out disinformation that a) they had ramped up production of a bunch of new long-range sea-spotting planes (they didn't, they only had the resources for a few); and b) these planes would fly near where they already -knew- the U-boat was, and 'spot it' (making sure it was obvious they'd been seen by the U-boat itself before flying back). The British were also careful not to find too many U-boats -- only the ones that they needed out of the way for critical operations. The Germans were convinced they just had really bad luck and were the victim of a very expensive and thorough patrol system by the British.

If the guys in dark suits can crack PGP, Blowfish, etc. easily, they won't obviously act on it until they first get dirt on you via other means. :p

Re:If you want to test it (1)

superdave80 (1226592) | more than 4 years ago | (#33294922)

That's a great idea. However, I'm not sure what you mean by 'questionable content'. Would you mind emailing me a few examples?

Re:conspiracy theory (1)

Sarten-X (1102295) | more than 4 years ago | (#33293934)

Possible, yes. Within the realm of imaginable possibility, no.

Re:conspiracy theory (1)

MagicM (85041) | more than 4 years ago | (#33294046)

Within the realm of imaginable possibility, yes. Within the realm of possible possibility, no.

Re:conspiracy theory (1)

debile (812761) | more than 4 years ago | (#33294026)

-----BEGIN PGP PUBLIC MESSAE BLOCK-----

mQENBExW0NkBC ADvqmg39Grmq7Yf2WQrbcJdOyHPNg/dmh mVLmXjGtQzdf5GvRMa
9Z5CzKtJR/eZCXRUQYpkBaQ25 ZrGWe+qGO6yUTFUKciaRqw3 REvTp35RwM7fQJdk
5o9powG2nQLG uj55F390hprx6Gc8RTyN QrejU3IOt0gsQ3PUnSM9bSvJ8ZX3k+c2

-----END PGP PUBLIC MESSAE BLOCK-----

With the crypted Echelon IP I just published, if NSA has a way to decrypt the message and want to track me, Slashdot will be offline in 5, 4, 3...2......1

Re:conspiracy theory (1)

Hawke666 (260367) | more than 4 years ago | (#33294442)

"MESSAE BLOCK"?

Re:conspiracy theory (1, Funny)

Anonymous Coward | more than 4 years ago | (#33294594)

-= "MESSAE BLOCK"?

You've broken the encryption!

Re:conspiracy theory (1)

metacell (523607) | more than 4 years ago | (#33294610)

Damn! They got to him before he posted!

Re:conspiracy theory (1)

gringer (252588) | more than 4 years ago | (#33294864)

With the crypted Echelon IP I just published, if NSA has a way to decrypt the message and want to track me, Slashdot will be offline in 5, 4, 3...2......1

127.0.0.1? Why am I able to log into that with my current username and password?

Re:conspiracy theory (5, Insightful)

woolpert (1442969) | more than 4 years ago | (#33294048)

I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?

Simplistically:
If THEY bought out 50% of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would only have a 50% chance of having one first.

More realistically,
If THEY bought out a significant percentage of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would likely only be a few months / years (at best) ahead.
And since the outlook on the QC front is rather bleak (in terms of a functional QC with any real power) the odds are strongly in favor of THEY not having squat.

Especially in today's world it isn't like top researchers are fragmented and isolated. In the past it was possible for a governmental organization to use its greater vision to collect isolated researchers and be the first to introduce them to each other, magnifying their individual efforts. Today everybody who is anybody in these fields is at least aware of the others, if not following closely.

Re:conspiracy theory (2, Insightful)

Anubis IV (1279820) | more than 4 years ago | (#33294434)

Of course, your point doesn't consider the fact that the information sharing only goes one way. If THEY come up with something new, it's not always put back out into the field where it can be worked on by others and built upon. If THEY then find something new, THEY can be the first and only ones building upon it, and THEY do not have to sacrifice the ability to build on everything else that is coming out in the field as well. If that something new is a breakthrough concept, then THEY may be able to build a lead of years or decades. Of course, as you pointed out, researchers tend to be much more aware of what is going on these days than in the past, due to the speed and ease of communication, which reduces both the likelihood of THEM getting a breakthrough first and also reduces the time that THEY will likely be the only ones exclusively holding that knowledge. Despite that, I seem to recall hearing stories of various encryption ideas the NSA developed in the '70s and '80s which weren't developed in the open until the late '90s and early 2000s (sorry, no citation).

Re:conspiracy theory (0)

Anonymous Coward | more than 4 years ago | (#33294456)

Especially in today's world it isn't like top researchers are fragmented and isolated.

There are researchers, and then there are classified government researchers - i.e. the NSA. The latter are still generally estimated to be 20 years ahead of the civilian world when it comes to encryption research.

Re:conspiracy theory (2, Funny)

euxneks (516538) | more than 4 years ago | (#33294776)

Simplistically: If THEY bought out 50% of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would only have a 50% chance of having one first.

Unfortunately, that same 50% chance collapsed to a more stable 0 once observed.

Re:conspiracy theory (1)

mrops (927562) | more than 4 years ago | (#33294912)

So what you are saying is that both the possibilities exist but we won't know until the cat is out of the box, where did I hear this before?

Re:conspiracy theory (1)

rahvin112 (446269) | more than 4 years ago | (#33295128)

Real World:

The NSA creates a front company called Quantum Research and funds it with black project money.

DARPA creates a front company called Skynet Research Ltd and again funds it with black project money which is unreported to congress or the public.

Both companies then hire CEO's from the public sector and give them no knowledge who they really work for. Quantum Research then gets "VC Money" from Skynet Research and goes on a hiring spree to develop quantum computers and hires and provides grants to 50% of the quantum research field. After successfully creating a quantum computer and producing a few "prototypes" said company declares to their employers that the cash has run out and they are going into liquidation. Said prototypes appears to disappear into liquidation and are never "seen" again.

And because everyone thought the companies were legitimate businesses not government research no one is the wiser to what has occurred.

This is standard operating procedure for the spy agencies and research branches like DARPA. DARPA seeds the educational community across many apparently unrelated disciplines. The NSA then creates front companies with access to the DARPA research, drives the company like an innovative startup, once innovation or invention occurs the company is folded and the assets or inventions are sequestered to the NSA with a few key employees that all along knew they were working for the NSA who then take the prototypes, enchance them and working with defense contractors replicate and expand the computers.

Just FYI the NSA is building a 50,000+ square foot computer complex in Utah on a millitary base (Camp Williams) that is going to use so much power they have to build a power plant to power it.

Optimist (1)

cowboy76Spain (815442) | more than 4 years ago | (#33294140)

I think you are too optimistic. I do not mean that "THEY" have one (I do not know/not answer). The issue is that the statement should read:

I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of their enemies.

After all, why limit it to only "ours" enemies after spending so much on it?

Re:conspiracy theory (1)

metacell (523607) | more than 4 years ago | (#33294580)

Of course we don't have any of the quantum computers the grey aliens ga... eh, I mean, we haven't come that far yet.

Re:conspiracy theory (1)

AliasMarlowe (1042386) | more than 4 years ago | (#33294698)

I wonder if "THEY" already have one of these quantum computers

Pardon my lack of paranoia. It's because "they" are out to get you, not me.

No (0)

Anonymous Coward | more than 4 years ago | (#33294782)

I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop

I happen to work at [CENSORED] and I must assure you that there's no need to worry, our research clearly indicates that making such computers is impossible.

Hey, you know that girlfriend of yours that sends you those pictures? She's hot!

Yeah, but... (0)

Anonymous Coward | more than 4 years ago | (#33293894)

Quantum computing needs exponential space. :)

New assymetric algorithms needed? (4, Interesting)

mlts (1038732) | more than 4 years ago | (#33293962)

Symmetric algorithms are at least in their second generation (DES/Lucifer now AES) of production use, with decades of study and close analysis by a lot of good minds.

Asymmetric algorithms are still essentially the first generation. Take RSA. It has been out for so long that its patent has expired more than 15 years ago. Even elliptic curve cryptography has been out at least 20 years, because the NeXT had it in NeXTStep 3.0 (and ended up getting pulled out of the OS due to ITAR).

Even cryptographic hashes have been through a number of iterations. We had MD4, then MD5, then SHA-1, then SHA-256, now are looking for something to replace SHA, similar to how Rijndael replaced 3DES and DES.

Maybe it is time to have a contest to have a standard asymmetric algorithm to replace RSA, DSS, and ElGamal? Something fundamentally designed to resist quantum computer attack as well as other threats.

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33294276)

Why not just use quantum key exchange and one-time pads and never have to worry about theoretical future brute-force attacks ever again?

Re:New assymetric algorithms needed? (2, Informative)

mlts (1038732) | more than 4 years ago | (#33294400)

Three reasons:

1: Public keys are not just used for real time exchanges. Public keys are sometimes used for data archiving where the private keys are held in an offline area. Same with keys that sign programs to detect tampering.

2: Quantum links are really, really slow. Instead of a one time pad, realistically you want to generate a key through the secure channel via a Diffie-Hellman handshake that is used for some time then chucked (like for a transaction or for a chunk of data.) Then send the bulk data through a standard link.

3: Quantum key exchanges have had some issues that could allow an attacker to get knowledge of the key.

4: One would have to drop parallel pipes everywhere that supported quantum channels. It is hard to get ISPs to drop one chunk of fiber, much less the fiber needed to interconnect for the secure quantum channels and the partial photons.

5: There is the issue of trust. You can set up a quantum exchange with another machine and come up with a key that you know hasn't been touched... but is that really your bank, or is it some site in Elbonia that is patched in? Quantum key selection won't help you here in knowing that you are talking to the right host.

Regardless, even if we had secure point to point connections via quantum key generation and bulk tunnels, public key cryptography is still an important part of life, even if it to sign documents and ensure they won't be tampered with.

Re:New assymetric algorithms needed? (1)

Timothy Brownawell (627747) | more than 4 years ago | (#33294418)

Because for a lot of uses, that would be solving the wrong problem.

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33294604)

Quantum key exchange and one-time pads are completely different options. One would use one or the other, but not both.

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33294314)

The difference here is that DES had to be replaced. Its very slow, and has too small a key length and block length. MD4, MD5 are completely broken, SHA1 is showing serious weaknesses, and by extension SHA2 probably has similar weaknesses.

RSA and ECC have not shown any sign of weakness yet aside from theoretical attacks and numerical attacks that can be countered with longer keys.

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33294446)

In other words you're asking for a problem in NP that is not in either of BQP and P. Should be simple enough, we'll get right on it.

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33294516)

That's easy - 3SAT. The hard part is making a decent encryption algorithm out of it.

Re:New assymetric algorithms needed? (2, Insightful)

FrangoAssado (561740) | more than 4 years ago | (#33295370)

What you're describing is a NP-complete problem -- assuming P != BQP != NP. But I'm guessing that you already know that :)

Still, it's still very hard to build a cryptosystem that exploits the hardness of solving NP-complete problems. The main problem is, NP-completeness only guarantees that some instance of the problem is hard, it says nothing about a specific instance. So, for instance, if you have a specific 3-SAT formula, there's no guarantee someone can't come up with a solution for it in polynomial time.

That being said, there are some candidates for a cryptosystem based on NP-completeness. Check for example the McEliece cryptosystem [wikipedia.org] .

Re:New assymetric algorithms needed? (1)

Kjella (173770) | more than 4 years ago | (#33295098)

If we had a fundamental understanding of problems that aren't solvable by quantum computing, some insight into whether P != NP or not then maybe. But we don't and until then, RSA has a lot going for it - for one it's extremely simple. So simple we went through and did examples on paper, of course with reduced bits. People have been trying to find an algorithm to factor integers for the last 2000 years, it's not a trivial task using conventional computers.

Shor's algorithm is impressive but it needs registers of q qubits where N^2 < 2^q < 2N^2, and N is 2048 bits which makes N^2 4096 bits so you need ~4096 qubits. So far the top public scientists are having huge issues getting more than a handful of qubits working together in a coherent state, and the problems only grows worse the more bits you add to the mix. Of course someone is going to suggest the possibility that the NSA might have overcome all that, but if so they're way, way ahead of the state of the art, and I don't mean in maths but more in physics and engineering. To put it this way, if they're that far ahead of the game we should ask them for the plans for the space elevator...

Re:New assymetric algorithms needed? (0)

Anonymous Coward | more than 4 years ago | (#33295736)

Don't forget other non-quantum machines that can factor RSA-1024, such as TWIRL and TWINKLE, that can easily factor up to RSA-1024 in a decent amount of time.

RSA needs replaced by something made this century somehow.

It's "Caltech", not "CalTech" or "Cal Tech" (2, Informative)

3.1415926535 (243140) | more than 4 years ago | (#33294096)

Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ [caltech.edu] and, you know, read any of the words on the page?

Re:It's "Caltech", not "CalTech" or "Cal Tech" (0)

Anonymous Coward | more than 4 years ago | (#33294362)

Thank you! I studied there, and it's always annoying to see it spelled incorrectly as "Cal Tech".

On the other hand, it helps differentiate know who actually went there and who didn't.

DEI, FEIF.

Re:It's "Caltech", not "CalTech" or "Cal Tech" (3, Funny)

Anonymous Coward | more than 4 years ago | (#33294416)

Pidantic much? {sic}

Re:It's "Caltech", not "CalTech" or "Cal Tech" (0)

Anonymous Coward | more than 4 years ago | (#33294528)

Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ [caltech.edu] and, you know, read any of the words on the page?

who gives a shit? Only pedantic Slashdotters, thats who!

Re:It's "Caltech", not "CalTech" or "Cal Tech" (1)

lgw (121541) | more than 4 years ago | (#33294648)

Slashdot has editors? You do realize that the guys who post stories on the front page aren't editors in the classic sense, right? They have only the "content controller" role, and don't do the sort of editing one associates with "edited prose". Your UID is low enough that none of this should be news to you.

Also, no one cares how you spell Cal Tech.

Re:It's "Caltech", not "CalTech" or "Cal Tech" (0)

Anonymous Coward | more than 4 years ago | (#33294684)

The way I was taught, it should be "Cal. Tech."

Of course, they probably trademarked Caltech, so that trumps any grammar rules.

There's an xkcd for that. (0, Redundant)

Kaenneth (82978) | more than 4 years ago | (#33295488)

Its callled a "one-time" page (0, Redundant)

crovira (10242) | more than 4 years ago | (#33294182)

torn off of a "one time" pad.

Anyone can transmit the page ID age the encrypted text in the clear and be assured of totally secure communication between the two parties who have both the encryption key and the decryption keys.

The algorithm consists of something non-computable.

In my case my the WEP2 key on my wireless LAN consists of my own unique way with keys (like I was going to tell you my idiosyncratic keying algorithm,) and an entire paragraph from a book on my shelf of selections from my favorite author (like I was going to tell you who that really was.)

Now extent that of a whole pad of keys...

Unbreakable is a phrase that comes unbidden to my lips.

Re:Its callled a "one-time" page (1)

supradave (623574) | more than 4 years ago | (#33294238)

Of course, that presumes a purely random one-time pad.

Re:Its callled a "one-time" page (1)

blueg3 (192743) | more than 4 years ago | (#33294344)

And a secure system for transmitting this pad from the sender to the receiver.

Re:Its callled a "one-time" page (0)

Anonymous Coward | more than 4 years ago | (#33294404)

We can transmit it using another one-time pad!

Re:Its callled a "one-time" page (1)

Sir_Lewk (967686) | more than 4 years ago | (#33294378)

1) I think (hope) you mean WPA2, not WEP2...
2) The proof for the perfect security of OTPs only applies if the pad is random. Not pseudo-random. You seem to be describing what amounts to a very primitive psuedo-random number generator, using pages of books as seeds. If you are not using random information, it is incorrect to call it a one time pad.

Re:Its callled a "one-time" page (1)

HeckRuler (1369601) | more than 4 years ago | (#33294420)

Wow you're ignorant. Or a very subtle form of funny.
Randomly generated one-time pads are definitely unbreakable. But the problems are generating the key and getting the key to the target as the key is as big as the text. So if you're using this to encrypt a connection, you need to split a 1Gig key, physically hand it to the target, and then you have 1Gig of communication before you need to hand him another stack of pads. It's good for sending code-words and like, emergency e-mails or something, but not constant communication channels.

Wait... you're using a pad for the key to a WEP2 encryption? And you're using books to generate the pads... that's... wow dude. Just wow.

HAHHAHA (0, Troll)

Schnoogs (1087081) | more than 4 years ago | (#33294220)

Another article that is over the head of 90% of the people who post here but that won't stop them from acting like they know something

Just ask Herr Jobs (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#33294300)

*pfft* I just broke the McEliece encryption on my iPad. There's an app on iTunes called iDecrypt...

Anonymous Coward (0)

Anonymous Coward | more than 4 years ago | (#33294346)

this is not really news worthy.

quantum computers will kill cryptography (as they are now) because of the ability to perform many computations at the same time. Factoring and algorithms to "break" a crypto system is about finding a shortcut, so that brute force can be avoided. But with quantum computers, brute force will be a more viable method.

especially, as with most computers and tech, the speed of quantum computers will only increase exponentially (once the first working one is stable and commerical), thus making brute force more and more viable. Increasing the key size will not be a viable solution unless we are willing to increase the key size exponentially as well.

so once quantum computers come out and get more refined, no pure mathematical crypto system will be safe.

Re:Anonymous Coward (0)

Anonymous Coward | more than 4 years ago | (#33295306)

You need to submit your name in order to receive a grant.

We have yet to see a real working quantum machine able to compute even an easy kids' version of RSA. The machines that have been built in the real world have done operations that a real computer does in a fraction of the time.

There is nothing to say if they are viable. Once an encryption breaking QC is built we may find that it indeed is able to calculate all the answers at the same time, but extracting the correct one takes 2^n or worse tries or some other unfeasable logistical problem. IMO, QCs are too much like the computing equivalent of perpetual motion not to be suspect.

Re:Anonymous Coward (1)

geekgirlandrea (1148779) | more than 4 years ago | (#33295396)

Quantum computers only provide a quadratic speedup for search problems like brute-forcing cryptography. Current secret key algorithms are safe.

Early connection? (5, Interesting)

steve_bryan (2671) | more than 4 years ago | (#33294350)

A sociological observation is that Shor was an undergrad at Caltech when McEliece was a professor there formulating the cryptosystem that would resist the quantum algorithm that Shor would develop years later. I wonder if knew each other.

Secure encryption (2, Interesting)

SnarfQuest (469614) | more than 4 years ago | (#33294494)

The only encryption method I've heard about that has not been found to be breakable is the one time pad. This method has the problem of exchanging the pads beforehand.

All of the major encryption machines used during WWII appear to have been broken. The new encryption methods are currently much harder to break, but the spooks are likely to discover some innovative method to break such algorithms.

Current methods using large prime numbers sounds like they are soon (next few decades) to be broken. If we got into a war where breaking these methods became important, I'm sure that quantum computers would soon become available, if they aren't already. Even if quantum algorithms aren't available, someone might come up with a way to calculate prime factors using a bacteria colony through DNA molecules. A method may cost a million dollars per factor found, but sometimes that is small change for the information gained.

I'm sure that there are groups looking for the next level of encryption. Something that isn't compatible with quantum methods, or requires it to reverse the encrypted data. Making it take longer and be more expensive to break is the goal of encryption.

Re:Secure encryption (0)

Anonymous Coward | more than 4 years ago | (#33294890)

The only encryption method I've heard about that has not been found to be breakable is the one time pad. This method has the problem of exchanging the pads beforehand.

And the problem of pad entropy, and the problem of keeping the pads secure once exchanged. And the problem of not being very practical for most purposes.

Re:Secure encryption (1)

cowscows (103644) | more than 4 years ago | (#33294936)

I'm not convinced that all these major breakthroughs in computing are just sitting right out of reach, waiting for a little war funding to make it happen. Computer technology has been moving so quickly the past couple of decades, and there's so much money to be made in these various fields, I'm sure the best and brightest are already working plenty hard on it.

I'm sorry, I'm an idiot- (1)

way2trivial (601132) | more than 4 years ago | (#33295272)

In the simplest of terms

I thought the whole point of the quantum computer was was it did the equivalent of brute forcing every single possible answer simultaneously

instead of checking a password say from

a
b
c ..z
aa
ab
ac ..az
ba
bb
bc ..bz

so a one letter password (normal computer) can be checked in 26 steps, and a 2 letter password in 676 steps..
each once then proceeding,

and on a quantum computer, I thought it threw the equivalent of the OED (all possible answers, all possible combinations) at the same time.

but only responding with the correct answer

will someone please tell me where my basis is way off?

$300 says... (0)

Anonymous Coward | more than 4 years ago | (#33295870)

$300 says that there's a quantum computer at Y-12 National Security Complex.

Introduction to post-quantum cryptography (2, Informative)

Anonymous Coward | more than 4 years ago | (#33295946)

There is an old paper, written by DJB, which gives a quick introduction to some (this and) other quantum computer resistant encryption methods: Introduction to post-quantum cryptography [pqcrypto.org]

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?