Eindhoven (The Netherlands) - Researchers at Eindhoven University of Technology claim to have crack the “Internet security of the future” – the McEliece cryptosystem, which is considered to be a candidate to safeguard Internet data traffic when quantum computers arrive.

The scientists said they have successfully developed and tested a way to speed up attacks on McEliece, a 30-year old a public-key encryption algorithm and are now able to decrypt a McEliece ciphertext in just one week on a cluster of 200 computers. Eindhoven University of Technology Tanja Lange announced that the software was run recently on several dozen computers in Eindhoven, Amsterdam, France, Ireland, Taiwan and the United States. A lucky computer in Ireland found the ciphertext.

McEliece, an asymmetric key algorithm developed in 1978 by Robert McEliece, is based on algebraic coding theory and uses a class of error-correcting codes, known as Goppa codes. The idea of the encryption is to create Goppa code as the private key and present it as linear code, which is the public key. Knowledge of the private key is necessary in order to decode the public key (linear code).  

Since 1978, the McEliece system has not attracted much acceptance in the cryptographic community, but is considered to be extremely strong and scalable. Its main drawbacks are an extremely large public key (219 bits); an encrypted message that is much larger than the plaintext message and increases the chance of transmission errors and the fact that the technology cannot be used for authentication or signature schemes because of its asymmetric nature.    

Attacks on the McEliece encryption have been reported before, for example by Valery Korzhik and Andrew Turkin in 1991, but there has been no evidence that the encryption was actually cracked. In 1993, scientists suggested to replace the Goppa codes with different algebraic code to make the system more secure. However, there is no proof either that this is actually the case.

New claims that a McEliece ciphertext has been decoded in just one week may prompt second thoughts whether this system is strong enough for the quantum computer age – a time that is expected to bring much more powerful computers that we have today. The researchers noted that the McEliece cryptosystem can be scaled to larger key sizes to avoid their attacks, which means that the technology could remain a candidate for post-quantum cryptography.

Larger key sizes have been used in cryptography in the past and are likely to stay with us in the future. For example, banks are still using RSA code from 1977 to protect electronic transactions – albeit with much larger keys than initially planned. The researchers said that “a single PC would need only 3 weeks to break the parameters from the original paper.”

But they haven't answer the real question...

Nov 03, 2008 01:38     

...Can this new software or ciphertext help us max out Crysis...???
Franklin report abuse vote down vote up Votes: -6

Re: But they haven't answer the real question...

Nov 03, 2008 04:13     

yes, they were decrypting super secret cheat codes ;)
Raf report abuse vote down vote up Votes: -3

@Franklin

Nov 03, 2008 04:30     

lol that really made me laugh
Ish report abuse vote down vote up Votes: -5

I am uncertain about quantum computing.

Nov 03, 2008 09:39     

I think it will be a very small field. :)
Ralf The Dog report abuse vote down vote up Votes: +0

Re: Crysis

Nov 03, 2008 13:30     

obviously the new cypher key will also increase required screen resolution to 1,000,000,024 x 1,000,000,680 and minimum system requirements will be a 10 core Vcpu with 2Tb of gdr26 memory and a separate cold-fusion 21 gigawatt power supply
robocop3 report abuse vote down vote up Votes: +0

quantum computing

Nov 03, 2008 15:33     

It's a small field, a large field, and a maybe-so field, all at the same time.
MorituriMax report abuse vote down vote up Votes: +5

@: MorituriMax

Nov 03, 2008 17:36     

Glad to know you got the joke, unlike the guy who voted me down. :)
Ralf The Dog report abuse vote down vote up Votes: +1

Erratam

Nov 04, 2008 05:23     

Hi, There is an erratum in the 4th section, line 3. It is “The McEliece cryptosystem has a very large public key (219 bits).” which should be corrected to “The McEliece cryptosystem has a very large public key (2^19 bits).” Best regards, Ali Rabiee -- http://alirabiee.com/
Ali Rabiee report abuse vote down vote up Votes: +2

RE: Erratam

Nov 04, 2008 07:40     

219 bits would be a rather small key.
Ralf The Dog report abuse vote down vote up Votes: +0

Large keys

Nov 04, 2008 12:09     

2^19 bits, not 219bits...
Joel Mussman report abuse vote down vote up Votes: +0

whats a cpu

Nov 05, 2008 23:52     

seriously
john report abuse vote down vote up Votes: -1

Re: Wolfgang Gruener - Title

Nov 16, 2008 20:33     

I really don't want to simply bash on you guys since I really don't like most comments that do that (but mostly due to the way they are written...). That said... Ok, granted that quantum computing is still not here yet and most do not know exactly how it will really be (kudos for MorituriMax's comment). But take a look at the title you got there: "Scientists crack possible future quantum computer age encryption" You're talking about an encryption from today (or from the past...) not from the future and that does not exist yet! You've probably also already read that quantum computing would (at least in theory) make all public encryption (as we know them now) completely useless. Reading the title, what I read is this: "some scientists were already trying to figure out some sort of encryption mechanism for use with quantum computing, whenever was it to arrive, but some other scientists already broke that one". So basically, your title is so wrong and so misleading that I got "angry" enough at reading this article.. enough to write such a huge comment.. Please try to use more descriptive titles... Please drop eye-catchy-that-really-is-wrong-and-means-absolutely-nothing titles... Thanks.

Q report abuse vote down vote up Votes: +0