RSA slightly broken

ccshan writes "Adi Shamir, the "S" in "RSA", discovers a factorization method that renders 512-bit keys vulnerable to cryptoanalysis today. " (its at the NYT:you know what that means)

Re:Prime-contest

You are thinking of Euclid's proof for the existence of infinitely many primes.

Take all the known primes, multiply them together and add 1. Call this x. x is not divisible by any known prime, so either x itself is a new prime, or some unknown prime divides x.

Note that there is no way to ensure x itself is a prime. In particular, there is no known formula for generating another prime from any quantity of known primes.

Security through openness

Interesting article - it shows again how important it is to only trust those algorithms that are open, published and subject to the scrutiny of the community. I am always amazed by the number of companies who really believe that keeping their encryption algorithms or security holes secret somehow makes them more secure. On a related note, I've often wondered if someday someone will find a fast, general algorithm for factoring. Such an algorithm might exist but be as yet undiscovered or it may be the case that brute force is about as good as can ever be done. Fascinating stuff, cryptoanalysis - I strongly recommend reading Applied Cryptography by Bruce Schneier to anyone who is interested in this sort of thing.

AES

FWIW, the (NIST) is currently evaluating several candidates for the new Advanced Encryption Standard (AES) [nist.gov]. This standard will presumably become the officially approved US Gov encryption methodology. One nice thing about this project is that most of the candidates have made their algorithms available for public scrutiny. Furthermore, it appears that there is concern about IP issues (e.g., patents).

This was taken from the AES site:

A process to develop a Federal Information Processing Standard (FIPS) for Advanced Encryption Standard (AES) specifying an Advanced Encryption Algorithm (AEA) has been initiated by NIST. NIST is currently soliciting candidate algorithms for inclusion in the AES. It is intended that the AES will specify an unclassified, publicly-disclosed encryption algorithm available royalty-free worldwide, that is capable of protecting sensitive government information well into the next century. It is also hoped that this standard will be as widely accepted as the Data Encryption Standard (DES) in the private and public sectors.

I looked at one of the algorithms, but it just made my head hurt.:)

Re:Factoring technology

No, there is no known plaintext. You don't encrypt the message, you encrypt a key for conventional cryptography and encrypt the message with that one. And the key you encrypt is (and should be, or you have a problem) a random number of which nothing is known about by an attacker.

quantum cryptanalysis = TEOTWAWKI

Each bit added to a number makes it exponentially harder to factor using a classical computer. Factoring techniques will improve, but there is no reason to believe anyone will ever develop a polynomial time factoring algorithm for a classical (non-quantum) machine.

Factoring large numbers in polynomial time is one of only two known algorithms for quantum computers. A modest quantum computer, if it could be built, would crack every prime-factorization cryptosystem currently in use (which is everything, essentially).

Researchers here at the Media Lab have already built a two quantum-bit bulk spin-resonance quantum computer. There are significant technical challenges to building a quantum computer large enough for cryptanalysis, but there is currently no reason to believe that this is impossible. If it can be done, it will almost certainly be done in the next five to ten years; major governments and private companies all over the world are pouring lots of money into this effort.

RSA is good, but we need to start developing cryptography algorithms which aren't factoring based (or reducible to prime factoring), and we need to start NOW. If there isn't a strong, widely-available non-factoring crypto implementation if/when the quantum computing breakthrough happens, all hell is going to break loose.

You're worried about the banks dropping a few transactions on Y2K? How about someone spoofing the Federal Reserve Banking Netowrk and bringing the global economy to its knees.

parallax

Factoring technology

If I'm not mistaken, RSA becomes free in September 2000 (patent expiry). Maybe this is RSA's way of "planned obselecance". :)

Because it relies on the product of two large primes, RSA will always be vulnerable to advances in factoring technology. In about five years, even the 1024-bit keys may become easily breakable. Until a real method to factor numbers faster than currently becomes available, we are going to find that RSA is still the most powerful encryption algorithm available (security vs. speed). I would recommend that the minimum key length in bits be increased to at least 8 times the maximum for easily broken keys.

In this case, 512 is easy to break, so 4096 should be the standard. This should yield a number of years of security. And, as always, make sure you give your keys one-year expiry dates.

It's about the increase in computer power, not RSA

Shamir has designed on paper a parallel machine that can crack 512 bit keys in a 'reasonable' amount of time.

All this heralds is that computing power has acheived another milestone, and that it's gotten easier/faster to factor numbers - and thus crack crypto.

Let it be pointed out, though, that the difficulty increase for each bit increase is exponential, not linear, so 768/1024/2048 bit RSA keys should be safe for quite some time...

maybe 10 years? HHOS.