Evidence that the McEliece Cryptosystem is resistant to Quantum Computing Attacks

A paper was posted on the preprint server Physics arXiv showing that the McEliece public key cryptosystem is resistant to efficient quantum algorithms based on the ideas of Shor’s algorithm, which famously yielded an efficient method for factoring integers. From the abstract

Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have post-quantum cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks. In this article we show that the McEliece cryptosystem over rational Goppa codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states.

Shor’s algorithm is a general method for computing the period of certain functions, and it can be applied to computing the orders of elements modulo a composite number for example (see my post Quantum Computing: are you Shor? for some details). Shor’s algorithm is not directly applicable to the McEliece cryptosystem since it is based on a hard problem from coding theory, and is not obviously solvable by computing periods of functions. The new paper seems to demonstrate that no connection will be found.

However the authors caution that there may be another quantum approach distinct from the principles of Shor’s algorithm that efficiently breaks the McEliece cryptosystem. On the other hand, there is a growing consensus that NP-complete problems do not have efficient quantum algorithms (see the diagram in this post), and the McEliece cryptosystem is based on an NP-hard problem (which means it is at least as hard as an NP-complete problem).

There is also a nice background post on the physics arXiv blog.

Related articles by Zemanta

• 1978 Cryptosystem Resists Quantum Attack (science.slashdot.org)
• Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing Attacks That Defeat All Common Codes [Encryption] (gizmodo.com)

RSA-512 factoring service: two weeks effort for $5,000

Ron Kane is offering a service to factor 512 RSA keys for a cost of about $5,000, taking two weeks or so. He describes the service as

Estimation on calculating the private key is 2 weeks (we have 2 separate clusters running, sometimes its rented to another company) .

We will be calculating on our private cluster / super computer, no groups / companies / other individuals involved, your private key will not be exposed to the internet anywhere!

Your private key will be sold once, only to you. In case someone else asks us to factor the same numbers, we will decline the request.

How we work:

• You make a down payment
• We will start calculating the key
• When the private key is ready, we will sign something with it and send it to you to verify it
• You pay us the remaining sum we agreed
• We give you plain numbers, or we can embed the private key in a smartcard (multos or JCOP)

You can contact him here, but if you are a bit more patient you can do it yourself. Some recent sampling results showed that a few percent of web servers are still running 512-bit keys.

Solo Desktop Factorization of an RSA-512 Key

It was recently announced that Benjamin Moody has factored an RSA-512 bit key in 73 days using only public software and his desktop computer. The first RSA-512 factorization in 1999 required the equivalent of 8,400 MIPS years over an elapsed time of about 7 months. The announcement was made all the more intriguing in that it came from a mailing list associated with a user forum for Texas Instruments calculators.

The public key in question is used to verify signed OS binaries for the TI 83 Plus and the factorization means that

… any operating system can be cryptographically signed in a manner identical to that of the original TI-OS. Third party operating systems can thus be loaded on any 83+ calculators without the use of any extra software (that was mentioned in recent news). Complete programming freedom has finally been achieved on the TI-83 Plus!

The original post from Moody was not very informative, but the subsequent Q & A thread drew out more details. Moody used public source factoring software on a dual-core Athlon64 at 1900 MHz. Just under 5 gigabytes of disk was required and about 2.5 gigabytes of RAM for the sieving process. The final computation involved finding the null space of a 5.4 million x 5.4 million matrix.

Most security people would rightly claim that RSA-512 is known to provide little security as a key length, however this does not mean that 512-bit public keys are not in use today by companies other than Texas Instruments. By the way, someone is offering an RSA 512 factoring service with a “price indication” of $5000.

CORRECTION, Feb 19, 2010: The original post said the factoring was done in 73 hours when the correct value is 73 days, as pointed out in the comment below. Thank you to Samuel for pointing out the mistake.