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.”
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.”