Slashdot Mirror
A Mighty Number Falls
space_in_your_face writes "An international team has broken a long-standing record in an impressive feat of calculation. On March 6, computer clusters from three institutions (the EPFL, the University of Bonn, and NTT in Japan) reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number — 2^1039 - 1 — that is 307 digits long." The lead researcher believes "the writing is on the wall" for 1024-bit encryption. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."
I read TFA, it didn't say what the factors were. Does anyone know?
Give me Classic Slashdot or give me death!
That's not even the point. The algorithm used to factor 2^k - 1, is generally the SNFS which is a highly optimized variant of the NFS, even faster than the GNFS. To factor RSA numbers you need the GNFS.
That said, not all 1024-bit numbers are hard to factor, in fact you have about a 1 in 300 chance of pulling 1024-bit prime out of your ass. The trick here is that RSA numbers are random and have less algebraic structure than Mersenne numbers.
Of course, with all that said, people should be using ECC anyways.
Tom
Someday, I'll have a real sig.
NSA research indicates that 1024-bit encryption is unbreakable and everyone should be using it.
Knowing this, too, will not help you pick up chicks in a bar....
"All great things are simple & expressed in a single word: freedom, justice, honor, duty, mercy, hope." --Churchill
SNFS != GNFS. Factoring specific 1024-bit numbers of that form isn't always super hard.
That they pulled off a SNFS on a 1024 bit number is cool, but not the same amount of work for a GNFS against an 1024-bit RSA key.
Tom
Someday, I'll have a real sig.
governments. Who, incidentally, are the prime targets for using encryption against.
FGD 135
I understand that they'll be able to crack 1024, but still, 3 years to see my e-mails. It's not worth it for them. Now when they got it down to 3 hours I'll be worried, but by then we'll probably be using 4096.
True, but what you need to think about is forward secrecy.
There are lots of things being transmitted today that are still going to be in use three years from now. For example, think of financial information: if you use an encryption standard that's acceptable right now, but can be broken in three years (or, is trivially breakable in three years due to increases in computer power or techniques), then you're in trouble, because some of that information is still going to be sensitive/valuable in three years. The fact that you'll be using 4096 bits then doesn't matter, if someone grabs it now and crunches on it for a while. Same with identification numbers (SSNs, etc); if I grab a batch of numbers today, most of them will probably still be good in ten or fifteen years, and some of them will still be good in 30 or 40. That's how far out you need to be thinking when choosing an encryption standard for that data.
There are some things where only immediate security matters (transmitting big session keys that get thrown away a few hours or minutes later), but many other things -- and I think general file encryption falls into this category -- where it's hard to predict for how long the encrypted information might be sensitive or valuable.
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
infinity left to go!
You mean, like generating a analogous OTP out of a pseudo-random number generator? Not only has that been done before, but you're still left with a key: The seed which produced the pseudo-random sequence.
The Navajo code-talkers worked because the encoding was extremely obscure (security through obscurity at its finest!) and cryptography was still in its infancy. I sincerely doubt that the Navajo codes would stand up to a modern cryptographic analysis.
http://en.wikipedia.org/wiki/Navajo_Code_Talkers
Javascript + Nintendo DSi = DSiCade
Adi Shamir designed one already. Instead of 11 months, it takes 12--but it could (in theory) factor any 1024-bit number.
http://xkcd.com/c257.html
Navajo code is pretty easy to crack.
This
Yes, The RSA Algorithm for public key encryption is based on the difficulty of factoring very large numbers. The key size is the number of bits in the number that has to be factored to break the encryption. Many of the modern security systems, including Verisign certificates for secure websites are based on RSA encryption and 1024 is a very common key size in use. Thus the ease of factoring 1024 bit numbers would indeed be a matter of concern.
RSA 101.
But with this kind of computation time, you just have to send lots of junk traffic to make them waste all their computing resources. If you send out 500 messages a day, only 1 of which has actual usable information in it, then they are going to be wasting a lot of computing resources just to find out which messages actually have usable information. With computation times this high, it would be easy to flood them with data so that they wouldn't have enough time to decrypt everything.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
There are actually three prime factors; the two you listed, and the small factor 5080711. Thus:
8 637648010052346319853288374753 * 20758181946442382764570481370359469516293970800739 52098812083870379272909032467938234314388414483488 25340533447691122230281583276965253760914101891052 41993899334109711624358962065972167481161749004803 659735573409253205425523689
2^1039-1 = 5080711 * 5585366661993629126074920465831594496864652701848
is the correct factorization, as can be readily verified.
Also:
http://www.heise.de/english/newsticker/news/90031
Quantum computers have that one nagging flaw: they don't actually exist.
The Navajo language basically served as a one time pad in WWII
No, they served as code-talkers. A one-time pad is a system whereby every bit of the encryption key is independent of the others (never reused, unlike codewords) and entropy is maximal. Simply translating stuff from one word to another is simple substitution, a simple code.
The reason Navajo Code Talkers were succesful wasn't because the scheme was particularly advanced. In fact, it would have been computationally trivial to break. However the messages relayed were only ever "tactical" in nature; i.e. communications in the field, of use during a fight, but old news in about 10 minutes. Had Navajo code talking been used to relay top-secret messages, it would have been broken fairly quickly. The reason for its success was that is was extremely cheap to implement for the US, and the secrets protected weren't valuable enough to spend huge effort on breaking. Economics, rather than mathematics.
Navajo wasn't used in Europe, because Germany had sent anthropologists to the US to learn native languages, anticipating precisely this scheme.
SCO employee? Check out the bounty
It's simply insane to use general purpose computer clusters to factor prime numbers when specialized devices built for factoring prime numbers can do the job thousands of times faster per node. These stunts are meaningless. All money funds for those waste of times should be put into developing better purpose built devices and more clever algorithms.
here's an example pdf of one such device. It's a tin can with single chip that has LED's integrated onto a shift register and a light detector at one end. costs about the same as one super computer node and is faster than a large cluster. Note that it's designed by the S in RSA so this is not baloney. it's not perfect and it needs technology refinement to scale to numbers larger than about 512 bits. That's where money wasted on this stunt should have been spent.
What's even stupider is that the calculations themselves serve no purpose. Anyone with an napkin and a pencil can tell you whether or not the calculation is feasible on a given size computer cluster. The expected time to crack in a brute force application of a seive is entirely predictable. So what does cracking one prove?
People who do this are more than harmless idiots. They waste money.
Some drink at the fountain of knowledge. Others just gargle.
Really it's not that bad of an idea. Create something that looks like image spam. Hide the encrypted information using stenography in the image, and send it out to millions of people, including the intended recipient. Everybody except the intended recipient deletes the message. It makes it harder to track down who you are communicating with, and harder to find out which messages actually contain useful information. It's similar to in olden days when they used to put a secret message in the classifieds of the newspaper. Only the people who know that it was supposed to be there could actually get the hidden message, but it was there for everyone to see.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
Not sure if this is a new idea, but this topic got me thinking. Decrypting something means is really just a mathematical transform. We say its "decrypted" if the end result "makes sense". But what if we didn't know what the final data should look like? How would we ever know it was decrypted?
Decryption itself only makes sense once we know what method was used, ie RSA, DES, Blowfish etc. However what if that algorithm itself was dynamic and formed part of the encryption? Sort of like a more generalised version of onion encryption, ie encrpyting the same content a number of times using different algorithms. So that the algorithms used and the sequence in which they are used form a sort of "meta-key"
Is that before or after looking at the machine? ;-)
(forgive me, I love quantum-related jokes... ^_~)
(forgive me, I love quantum-related jokes... ^_~) Yes.
(forgive me, I love logic-related jokes
The Tao of math: The numbers you can count are not the real numbers.
in fact you have about a 1 in 300 chance of pulling 1024-bit prime out of your ass
Wow, now *that* is a cool trick!
This has already been done as early as 10 years ago.
I was working in Eastern Europe on a now unclassified project, working against a low budget illegal foreign intelligence agency. They were selling and distributing porn CD's and DVD's with thousands of pictures, one or more of which would contain an encrypted stenographic message. Their contact would purchase the DVD at one of hundreds of little markets, and decrypt the proper image(s).
It was really quite a good plan. Not only were there many possible valid messages to one or more agents, but there were also an unknown number of false messages, they even may have even been all false messages that could only be put together by inference. However, since they were encrypted with PGP, we never were able to break that particular system before I left the project.
The real genius of the plan was that it brought them in some much needed cash as well.
The television will not be revolutionized.
Use bc instead.
The factors are correct. Just checked.
And don't doubt me, I'm a 3 digits UID
Quantum computers have that one nagging flaw: they don't actually exist.
Quantum computers have that one nagging flaw: they actually exist.
-- If you try to fail and succeed, which have you done? - Uli's moose
The reason 3DES provides an effective key length of 112 bits, not 168, isn't because only two keys are used instead of three. We only bother using two keys because the effective length of three-key 3DES is still only 112 bits, so there's little reason to bother storing and managing a third.
The reason the effective length is only 112 bits is something called the "Meet in The Middle" attack. Suppose three keys were used and that the attacker has plaintext and ciphertext to mount a known-plaintext attack. An attacker can apply the first encryption step to the plaintext message using all possible 56-bit keys and then store the results in a big dictionary. Then, the attacker picks a 112-bit key and performs the first two decryption steps on the ciphertext. If the result is in the dictionary, then the attacker has probably found all three keys. If not, he picks another 112-bit key and tries again. So the attacker's work is (a) the effort required to create the dictionary plus (b) the effort required to brute force search a 112-bit keyspace. Since (b) completely dominates (a) we can ignore (a) and use (b) as our estimate of the attack complexity.
In the case of any quadruple encryption, then, the Meet in the Middle attack would require building a dictionary of all possible encryptions using the first two keys, then brute forcing the space of the last two keys. So, the effective strength is equivalent to the size of two of the four keys. Quintuple encryption is equivalent to three keys. Double encryption is equivalent to one key, which is why 2DES was never used.
What does all of this have to do with 1024-bit RSA keys? Not a thing. 1024-bit RSA keys consist of numbers that are the product of two 512-bit prime numbers. That means they're pretty sparse among the set of all possible 1024-bit numbers, and it means they have a particular mathematical structure that can be exploited.
Symmetric ciphers, like AES, are different. Unless there's something wrong with them, their keyspaces are flat, meaning that if they use n-bit keys, every possible n-bit value is a legitimate key. They have no particular mathematical properties, and there is no way to identify the right one except by trying them all.
So, assuming that AES doesn't have some weakness that allows attacks faster than brute force to succeed, how long until we need to use keys bigger than 256 bits?
Forever, basically. Barring weaknesses in the algorithm, 256-bit symmetric keys are safe until, as Bruce Schneier put it "computers are built from something other than matter and occupy something other than space."
In Applied Cryptography he outlines an interesting little computation to demonstrate why this is. Suppose you had a computer that contained a 256-bit register that was maximally efficient, meaning that toggling a bit required exactly one quantum of energy. Since smaller units of energy don't exist, you can't do better than that[*]. With that assumption, you can calculate how much energy it would take to cycle your 256-bit counter through all possible states. Schneier calculates that if you could capture all of the energy from a typical supernova and run your counter on that, you could count from 0 all the way up through about 2^219. So you'd need about 130 billion supernovas to run your counter through all of its 2^256 possible states.
That completely ignores the energy you'd need to perform a trial encryption with each of those values, and it also completely ignores how long it would take to perform all of these operations.
Quantum computers that can somehow handle the complex structures of symmetric ciphers, or some other radical change in computing technology would be required to make 256-bit keys accessible to brute force. A flaw in AES is far more likely, IMO.
[*] Just because someone will call me on it, I should point out that reversible computing means that in theory you might be able to do better than the theorized maximally-efficient computer. In practice, that probably isn't going to make your energy budget small enough to be reachable, and it certainly isn't going to help with the time factor.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Perhaps you should see the Prime Number Shitting Bear.
n gbear.html . Enjoy.
Originally at http://www.primenumbershittingbear.com/ but that's long dead, so I dug it out of the Wayback Machine and put it up at http://rpresser.googlepages.com/primenumbershitti