Shor’s algorithm is an algorithm for quantum computers which allows for efficiently factoring of numbers. This in turn allows Shor’s algorithm to break the RSA public key cryptosystem. Further variations on Shor’s algorithm break a plethora of other public key cryptosystems, including those based on elliptic curves. The McEliece cryptosystem is one of the few public key cryptosystems where variations on Shor’s algorithm do not break the cryptosystem. Thus it has been suggested that the McEliece cryptosystem might be a suitable cryptosystem in the “post quantum world”, i.e. for a world where a quantum computer is built (and if your a commenter who wishes to simply post the quantum computers are like string theory, please…save your keystrokes.)
Recently, Tanja Lange and coworkers Daniel Bernstein and Christiane Peters have undertaken classical attacks on the McEliece cryptosystem. A public key cryptosystem gives you security as a function of the size of a hard computational problem. For example in the RSA cryptosystem, the problem is closely related to the hardness of factoring. Thus the number of digits in the number being factored gives one a handle on how hard the problem is. For example if you perform RSA using a number which is, say 20 digits long, then I can easily break the key system using my laptop. But if you make the number large enough, then there is no classical computer with enough computational power to break the system. Thus the size of the number to be factored serves as a security parameter. What Lange, Bernstein, and Peters demonstrated was that if one used the original security parameters for the McEliece cryptosystem, then they could break the cryptosystem using classical computers in two weeks on a cluster of one hundred computers. See the press release here and the paper here. Notably I believe that prior authors had noted that the original parameters for the McEliece cryptosystem did not provide enough security (though I don’t know whether an explicit attack was carried out as the authors do here.) The authors also, notably suggest new security parameters for the McEliece system. (A cool part of the paper is where they thank all the different institutions for the computer time!)
So this is very cool work, an explicit attack on the McEliece system which breaks the original proposed security parameters. And it gives suggestions for what reasonable security parameters should be for the system (which is not used in practice much because the algorithm has a huge key size and is not too fast.)
Cool, but how it world did the author/editors of techradar manage to get out of the above story an article titled Quantum computer security cracked. Wah? Um, no quantum computer security was cracked. Doh. That’s a long way from the original cool work (though the article doesn’t mess up as badly as that title.)
O brave new quantum world!
Cool! Well, sort of, I guess. Cool, because anything crypto-related is cool and cracking something like that is always an interesting math problem. Not so cool if you rely on it for data security. And dumb title.
Oh, and it’s ‘elliptic’ curves, not ‘ecliptic.’
Your link to McEliece cryptosystem is broken. Drop the %22 from the end of it to get McEliece cryptosystem.
Doh, typos fixed.
Ecliptic curves is some sort of science/freudian slip.
Interestingly the fly study in question isn’t Drosophila. But the research is still worth it as apparently the fly being studied can really really wipe out crops.
Without the security of Ecliptic curves, no Astrologer’s proprietary research will be safe. Of course, I say that primarily because I’m a Virgo with Moon and Venus in Virgo.
Which reminds me, re: “the article doesn’t mess up as badly as that title”, that it seems strange in 2008 that so many newspapers in the USA have an Astrology column, and so few have an Astronomy column. And I just saw John McCain on CNN rallying supporters with anger that Barack Obama wants a $3,000,000 earmark for an “overhead projector at a planetarium” in Chicago. While Sarah Palin attacks research funding of “fruit flies” notwithstanding that our knowledge of genetics — including of Down syndrome — depends heavily on the study of Drosophila. Hence I’d prefer that we not quibble about errors in publications. The real war is between Science and Ignorance.
I’m Professor Jonathan Vos Post, and I approve this message.
This is obvious, because if to generate prime number is not so hard (n^2 or n^3, where n number of bits roughly) then if you know one (user) prime number part then you can generate very many as possible primes number in time n^2 and to check them in linear time of roughly n if they going to crack – matching with thise user known… Another talk if nobody know this user number, then probably need shor algorihm. So any known virus or somthing can hack – stole part of RSA by troian say and take money. So safety is doubful of banks, but good news is that seems nobody seems is disapointed by virtual money. Because maybe there is more safe ways than RSA… Like one time run, but computer still not very safe and user never can know is there no any speculations about his money, but like saying, if better to by and cheapier with virtual moneys, then shouldn’t be problems seems.
It seems like even any RSA number of cash can be opened by multiplaying all known prime numbers, which take aditional n^2 time, so roughly break RSA is twice harder than create like to take all money from bank and all peiples cashes need just twice more powerfull computer or twice more time.