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."
Slide rule?
I read TFA, it didn't say what the factors were. Does anyone know?
Give me Classic Slashdot or give me death!
that was used for this? I don't think I have to worry about the usability of 1024bit encryption for a while yet.
"I use a Mac because I'm just better than you are."
I don't think that I care about this.
For an embarrassingly parallel, strictly integer application like this, I think the logical next step is to attack it with FPGAs. For such an application, it wouldn't surprise me if a large Alterera FPGA could give you at least the same computation power as a large cluster, for a fraction of the price (both for the hardware and the electricity to power the thing).
To make laws that man cannot, and will not obey, serves to bring all law into contempt.
--E.C. Stanton
"Security is about risk management. If you have something to protect that's valuable enough for someone to steal, and the only protection you have on it is 1,024-bit crypto, you deserve to have it stolen." -- Forgot who said it, but it was on /.
My blog
I can see the RIAA filing the lawsuit on a DMCA violation now....."That's our prime number/integer"
When I was your age we didn't have music file sharing utilities. We had to go out to a store and shoplift the CD.
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.
And by that time, I presume somebody would have figured an algorithm that works on general numbers as well as the SNFS works on 2^n - 1 type of numbers.
Rather than just digesting using some key, It seems to me that you could set up two 'encryption' agents which talk to each other and form a random proprietary "language" that only each other can understand. This would be very much like a one time pad - which is basically the only truly unbreakable encryption:
Code Talkers.
The Navajo language basically served as a one time pad in WWII - why not use programs which generate their own method of communication (their own "language") for use in transmitting information.
You simply could not crack it unless you already knew the information being sent.
Read my Very Short "Stories"
> The lead researcher believes "the writing is on the wall" for 1024-bit encryption.
All we have to do now is wait for the 3 clusters worth of computing power to hit mid range servers and 1024 bit crypto is useless.
The writing was always on the wall, we've been using 2048 bit crypto for PGP for years now.
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
it didn't say what the factors were
they are numbers that are only divisible by 1 and themsevles. duh.
...is that most Certificate Authorities who have trusted certs in the major browsers / e-mail programs will NOT sign a certificate for any keysize greater than 1024 bits.
This artificial limitation is going to become more and more glaringly obvious as time goes on.
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.
is that 90 - 95% of people don't seem to use it. You can move to a new apartment building (or house) and chances are you can get free Internet right away off of some soccer mom who didn't enable any encryption. (Yes I know routers don't use 1024). They need to enable encryption by default and randomly generate each router with a default password (random numbers and letters and print it in their manual)
Considering RSA Inc. sells X.509 token/smart card devices which support ONLY 1024-bit keys, I don't think it's going anywhere for a while.
A slashdotter who didn't build his own computer is like a Jedi who didn't build his own lightsaber.
uh huh. Right. Let's see you write a paper and an example implimentation of that. Good luck.
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
"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."
You left out the time factor. How long do you need for whatever to remain secret? At the end even if cracked it may no longer be relevent to whomever's doing the cracking.
But what about the other forms of public key encryption? Wikipedia also lists Diffe-Hellman, ElGammel, Eliptic Curve and others.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
What exactly do they mean by the "the writing is on the wall" for 1024-bit encryption? Does the 307 digit long set of prime factors have some bearing on the ability to break encryption, or is it just a reference to the amount of sheer computing power out in the industry today?
I'm having a hard time making the coorelation.
Lindsay Blanton
RadioReference.com
I just factored 2^2048 in a few milliseconds on a single computer. Your bank account balance was just donated to support world peace. RSA is doomed? Oh, wait? Are you saying RSA is based on numbers which are products of two large primes, not just some numbers with lots of small factors? Bummer!
Ok, I know this is an overplayed argument - the 'humanity' card. Like when NASA announces they've found a way to get 3 men to the moon for just under 8 billion dollars - and people say, "Umm, couldn't we use 8 billion dollars in Florida for our worst-in-the-country school system?"
Obviously, that's a long and involved argument. But in this case - factoring a very large prime number - just by using methods we *knew* would work - but had never dedicated the resources to - what kind of real progress is that? We haven't really learned anything - have we?
Wouldn't that computing time have been way way more valuable to any of the 'potentially useful' distributed computing projects floating around out there? This sounds like a monumental waste of sciences new most-precious resource - CPU time.
---
monumental waste!
Ace
The sieving step of the algorithm is indeed embarrassingly parallel, but what about the linear algebra step? I am pretty sure that part is not FPGA-able, yet.
85% of all statistics are made up.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Just the other day I was reading up on the RSA challange and was dissapointed to read that it had been cancelled. I was reading up on it because at work we were researching various algorithms for factoring large numbers. Good to know a the absence of a cash incentive hasn't slowed down progress in this field. ;)
This seems like cool work to me and maybe an app like this would be a great addition to Folding at Home for the PS3!
http://xkcd.com/c257.html
Navajo code is pretty easy to crack.
This
All you have to do is set up something like distributed.net and you can crank through pretty fast. If hackers can infect millions of systems for massive DDOS attacks I think they could probably create a massive distributed computing platform. Vista will only make things easier because it forces a powerful video card on every system. If the distributed network can harness those video cards for number crunching they'll be a lot faster than networks running on just the CPU.
At what price learning? At what cost wisdom? The price is a man's peace of mind, and the cost is his life.
Isn't this the way some cryptography systems work? Using Diffie Helman key exchange to decide a secret key. Assuming nobody knows the key is what makes it secure. Just like in WWII, they assumed the enemy didn't understand Navajo. I'm not sure what kind of computing would be necessary for the computers to agree on a decryption/encryption language. They'd probably have a set list of ciphers that they both supported. I don't think there's any way to create strong ciphers on the fly. Another problem is how to transfer the cipher language to the other machine without anybody being able to intercept it. I guess the best solution would be to use diffie-helman key exchange to generate a key that's the same length as the message, and use that to encrypt the message. You would effectively create a one time pad. However, I think that something of this nature is currently too resource intensive for any reasonable size of message.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
bool microsoft_fud_manager::HandleNews(){ //throw "unexpected condition"; //throw disabled by bg.
if( GetPlatform(clusters) == "Linux" ) then
return IssuePressRelease("Linux is a hackers tool breaking encryption");
}else if( GetPlatform(clusters) == "Windows"){
return IssuePressRelease("Windows Rules! We solve big problems");
}
IssueGeneralFud();
}
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
Perfectly secure methods (one time pad) are perfectly secure because even if you have the cryptotext and the plaintext, the probably that the cryptotext is the plaintext is the same for all plaintexts if you don't know the key (e.g. if you knew the cryptotext is one of two plaintexts, the probability that it was one or the other is 0.5 regardless of what you know about the algorithm).
The Navajo language is an example of security through obscurity, it's not comparable to one time pad. The Navajo language is susceptible to many attacks, e.g. frequencly analysis.
It's easy. 09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0
It would reference Klingon (sp?) language and quickly be filed in the circular file.
This package Does Not Contain a Winner
Is it really that easy now to learn an undocumented language, just from verbal radio transmissions and knowledge of related war events?
Incidentally, I suspect security through obscurity can serve a purpose in encryption. As I understand it, with public key encryption, it may be computationally intensive, but at least it can be automated and the problem is well-defined. If the eavesdropper had to first figure out, from the set of all possible encryption methods, which encryption method you were using, it may force her to apply human labor to finding the solution, which may be the scarcer resource.
Apology to Ubuntu forum.
"The Navajo language basically served as a one time pad in WWII..."
Ummm, no. A one-time pad is used, well, once. Code talkers (Navajo and others) worked because of the obscurity of the "code."
What you're describing is basically a home grown encryption algorithm. Reverse engineering an encryption algorithm is (relatively) trivial if you have access to one of the programs generating the 'language'. Now, given that most encryption algorithms developed by expert cryptographers prove to have chips and sometimes holes in them, what odds do you think a non-cryptographer has of making even a half-decent algorithm?
We've upped our standards. Up yours.
From http://www.ddj.com/blog/portal/archives/2007/05/wo rld_record_fo.html
Using the sieve program developed at the University of Bonn, NTT, EPFL, and the University of Bonn respectively provided 84.1 percent, 8.3 percent, and 7.6 percent of the calculation resources, and the calculation amount equivalent to 95 years of operation on a 3-Ghz Pentium D. PC clusters at NTT and EPFL, consisting of 110 and 36 PCs, respectively, were run in parallel for more than two months for the calculations. The results were 47 non-trivial solutions of the simultaneous equations defined by an approximate 70,000,000 x 70,000,000 large sparse linear matrix.
If I understand correctly this would be security via obscurity. All you'd have to do is learn the language and emulate it.
The largest RSA number so far factored is only 663 bits. 512 bits in 1999, 576 bits in 2003, 663 bits in 2005. Call it 100 bits improvement in 2 years. At this rate we should be due for a 700 and some bit number this year, with 1024 bits 5-10 years away.
The RSA Factoring Challenge has been suspended, i.e. they are no longer giving out prize money, but the numbers still stand as a good reference for where we are in comparison to 1024. There's a lot of mileage between here and there.
I'm hoping there are some crypto geeks in the audience who can answer this. I know that back in the days when DES (with 56-bit keys) was the best there was, some genius invented TDES, which was simply three passes of DES, for a total key length of 168 bits. However, running DES thrice does not triple the "security" (resistance to brute-force cracking) of the cipher, rather the 168 bit key provides security equal to that of a 112 bit key due to some mathematical technicality that I've forgotten.
Now for my actual question. There isn't a symmetric crypto algorithm that I know of that can use 1024 bit keys (except for stream ciphers, maybe RC4?); the best block cipher is AES (Rijndael) which supports 256 bit keys. If one would "invent" QAES, i e quadruple QAES, for a total key length of 1024 bits, what would the "effective" key length be?
Quality, performance, value; you get only two, and you don't always get to pick.
any security measure built by a man can also be broken by a man
there is absolutely no such thing as 100% security
and there never will be
for most of us, 99.9999999999999999999999% security will do
for the rest, sweaty heart palpitations and paranoid schizophrenia will do
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage 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
In [21]:len(str(2**1039-1)) Out[21]:313
not to be trite, but in the end, all that matters is love
>Think hard about this. How can we have privacy in the digital age?
By and large, "we" don't even use *mild* crypto, even in places where we really should be using *hard* crypto.
Do we actually *want* privacy? Seems not.
-fb Everything not expressly forbidden is now mandatory.
Your tax dollars at work...
Given enough time, it is. Incidentally, I suspect security through obscurity can serve a purpose in encryption. As I understand it, with public key encryption, it may be computationally intensive, but at least it can be automated and the problem is well-defined. If the eavesdropper had to first figure out, from the set of all possible encryption methods, which encryption method you were using, it may force her to apply human labor to finding the solution, which may be the scarcer resource. You must also exchange the rules of the language secretly if you want to maintain the security.
Also the assumption that we would need a human to figure out the language isn't necessarily true.
This
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.
oops here's a working link
Some drink at the fountain of knowledge. Others just gargle.
Twinkle, an older version of twirl, has a better wikipedia entry
Some drink at the fountain of knowledge. Others just gargle.
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"
I accept your reply.
It does make me wonder more, however. For example, imagine Alice, Bob and Jesus are having lunch. Alice turns to Bob and says, "Remember that thing I was telling you about?"
Bob says, "Oh, yes. Where that stuff was different than last time?"
"Yes, exactly. Only this time that same person did the same thing they did that one weekend."
Alice has transferred information to Bob and Jesus is confused. It seems that no amount of analysis could decipher what Alice and Bob are talking about. I suppose the implied information could still be considered a "key", but I imagine that this database of implicit information pieces could be very large.
Is there an analogy for this method of secret information exchange? It does seem that something akin to this method might work well.
Read my Very Short "Stories"
All you're doing in creating a "proprietary language" is combining the cipher and the key. Under normal circumstances, this is considered a very, very bad idea.
E.g., with the Navajo language, anyone who knows the language can decode any message sent using that system. It's not particularly secure. It was operationally successful for a lot of reasons that don't really have anything to do with the superiority of Navajo as a cryptosystem (i.e. they never captured any of the code-talkers). The reason why the code-talkers were useful has less to do with security than with speed: most other cipher systems worked by typing a message into a machine -- impractical in the field. But if one of the code-talkers had been captured, then the whole system would have been blown, since there's no easy way to change the "key."
In contrast, something like the Enigma machine used a key that's discrete from the apparatus. You take your machine, and configure the patch-cables in a certain way, and set the wheels up right, and encode your message. The receiver sets their machine up identically (based on a codebook which gives a different configuration for each message or day) and decrypts it. That's a much better system -- in theory -- because even if the enemy has the machine, they'd still be stuck without the key. It failed mostly because the German operators were human, and therefore lazy, and tended to not follow protocol a lot and reused the keys. (And the keyspace wasn't that large and could be brute-forced, which is what the British did with the very early computers.)
The apparent superiority of a natural-language "cryptosystem" like Navajo to electro-mechanical ones like Enigma is mostly because of the tendency of operators to become overconfident in mechanical ciphers. While a person speaking in a foreign language is conceptually easy to grasp ('hey, we'd better not let them capture him'), it's not as easy to understand why it's desperately important to not reuse Enigma keys, or to re-transmit the same message over and over using different keys, etc.
All modern cryptography (well, almost all, anyway) revolves around the idea of separating the key from the algorithm, and basing the security of the system only on the key. That is to say, even if your enemy captures the cipher machine and the text of the enciphered message, they shouldn't have any advantage in figuring it out versus just having the message. The advantage to this is that you can change keys easily, so you can change them often, and give your adversary less time to analyze each algorithm+key combination before you switch to the next one.
Also, a one-time-pad is really just a symmetric cipher where the plaintext and the key are the same length; it is the exact opposite of a 'proprietary language' like you describe (where the 'key' is knowledge of the language itself -- arguably long, but definitely finite).
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
"Is it really that easy now to learn an undocumented language, just from verbal radio transmissions and knowledge of related war events?"
What slashdotter doesn't think so?
That's effectively what a code is. In order to decipher the information, you need to find the codebook that explains the meaning. The problem with this scheme is two-fold:
1. Keeping the codebook secure. In electronic communications it is difficult to ensure that the codebook doesn't fall into the wrong hands. Imagine that Bob and Alice had their previous conversations in a crowded shopping mall rather than in the privacy of their home, and that they both had to shout to properly understand one another. All Jesus would have to do is either lay in wait while they have the conversation, or ask enough people who were present until he finds someone who remembers what their conversation was about.
2. Given enough samples of communication, Bob and Alice's code will eventually succumb to analysis. They'll keep talking about this person interacting with that person, which resulted in this event. If Jesus knows of the subjects (and come on, he's Jesus!) he'll eventually get the gist of who the subjects are. Thus the code fails in the same way an OTP fails when used more than once. (Thus why it's a one time pad.)
Javascript + Nintendo DSi = DSiCade
You still have to have a way to exchange that first bit of information so that both alice and bob know what they are both talking about without somebody getting a hold of that context. You're defining a recursion problem that doesn't seem to me to deal with the problem.
Most of the younger generation wants nothing to do with privacy! Hence why we have how ever many million myspace accounts and blogs. Remember when diaries used to be private and secret? Can we PLEASE go back to that?
Persistent Volume manager for Kubernetes - https://github.com/dwimsey/openshift-pvmanager
Next you'll try convince me he can't hit a curve ball...
I am billdar, and I approve this message.
If you know how many calculations a second a given program can do then the rest is pointless. You just divide total seconds by number of PCs in the cluster.
With climate change looming, pointless waste of electricity like this should be discouraged.
PS: It's well known that RSA will fall. Number factoring is one of the half-dozen-or-so tasks a quantum computer can actually do. It's just a matter of time before a working quantum computer renders the whole public-key system unsafe.
No sig today...
Now the part that jumped out at me is "computer time"
WTF is computer time? Cycles p/sec * number of procs in the cluster?
"8 months of calculations that took over a half century of computer time"
"11-month job took a century of computer time"
....so is a 14 month job one and half century of computer time? WTF??? I thought 8 months was 8 months not 1/2 century and 11 months is 11 months (or almost a year and not 100 F'ng years)...
Can someone please explain this crap to me....??? I just don't get the lingo...
I did 2^1040-1 yesterday on my TI-83...I knew that overclock was worth it!
Look at the "Suite A" algorithms. A lot of them are understood to be (older) implementations of PKI, such as FIREFLY.
But now that ECC-PKI and AES are out there and essentially implemented things the NSA thought needed to be implemented (or already did, perhaps experimentally), and these things have been tested and hammered on, well they said, fine, let's start using it.
So now you can do Top Secret on AES (with a NIST-approved implementation, of course)
THIS THING CAN TURN ON A DIME, MACROSSZERO STYLE ALSO FUCK BETA, ~NYORON
> Is there an analogy for this method of secret information exchange? It does seem that something akin to this method might work well.
It's pretty much like having a shared private key that you communicate through some secure channel beforehand. Oftentimes, they use another, more computationally expensive, cipher to exchange a key like that, then they use it with a simpler cipher to protect the communication.
The only difference is that the computer's secrets are long binary strings, whereas your example has people using shared experiences to secretly communicate. And if I may point it out, they're not doing very well even then. They probably wouldn't want their adversary to know even that they were exchanging something. What if they'd have been watched the last time they got that "thing"? So you have to scramble everything, although you can also use steganography to hide the very fact that you're communicating something secret at all.
Ah yes, I saw this as a glaring problem as well!
Oh well, back to the drawing board to dream up a method for an "n times pad"
Read my Very Short "Stories"
From TFA:
Is the writing on the wall for 1024-bit encryption?"The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking."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."Reading Lestra's comments, I get the feeling that he has a fairly high degree of confidence that they will succeed in making the leap to a mathematical generalization within a modest time frame.
Can any security researchers tell me what GPG key length I should be using in the real world to give me a good trade-off between computational simplicity and future security please? I'm only using crypto for email and secure file storage.
-P
Be my friend.
I don't know where she/he got her/his number, but it's wrong.
Use Python, Luke:
So the summary is wrong too: the number is 313, not 307 digits long. At least in base 10.
There's a hidden treasure in Python 3.x: __prepare__()
Proably we don't need infinite encryption schemes. I think this encryption thing has gone too far. If a,b,c are independent and there is a certain probability P(a|t), P(b|t), P(c|t) to decrypt each of the schemes within a certain time, when combined the P(a|t)*P(b|t)*P(c|t) can be made reasonable small.
This is all irrelevant since Jesus just gets the information straigth from Alice.
All girls like Jesus, because his hung like this **opens arms wide open**
The fact that the British made the Enigma machines in the first place was also a help. Germany improved on it, and it was a polish spy that uncovered the changes, but it was definitely a help that the mechanism was very well understood in the first place.
An old theology joke goes like this: "if god is omnipotent, can he make a rock so heavy he can't lift it?"
But for quantum computers the question has a resonance. Can a quantum computer create prime numbers so large that another quantum computer could not factor the composite?
I realize that there's always quantum crypto. But for most folks we need to be able to use RSA not some new scheme for the privileged.
Some drink at the fountain of knowledge. Others just gargle.
sage: 2^1039-11 50177535756899376584320794655559932591384900650140 34006389161562581754376322314451080388584562460719 42881076106983317459922215338711318936320121062386 22173921469033288521558997823700137184806201826907 36866953411252382072659135491210334387684495620912 6576528293887
5890680864316836766447387249177476247119386964598
Can anyone give us a glimpse of what the comparison is between the total computing power in this breakthrough vs. the perceived total computing power of the NSA, which most likely has been working on this same thing for a VERY long time?
It is pitch black. You are likely to be eaten by a grue.
If you have something that is valuable enough that someone is trying to break your 1024-bit crypto, you might actually have bigger problems than someone possibly breaking your crypto.
4 .htm
Meaning, you might keep an eye open for incoming Hellfire missiles or some such, or making sure your Oracle username/password isn't "scott/tiger":
http://www.fas.org/man/dod-101/sys/missile/agm-11
Give a man a fish and you have fed him for today. Teach a man to fish, and he'll say "WHERE'S MY FISH, YOU IDIOT?"
we still haven't found the 216 digit number which holds the key to stock market prices and the Torah.
try { do() || do_not(); } catch (JediException err) { yoda(err); }
Alice and Bob's memories constitute a "back channel" which, because it occurred in the past, is secure from Jesus.
If you have a secure back channel, then you can just use that to exchange AES keys (i.e. symmetric keys) and be done with it forever. AES won't be cracked for a century.
It is only when you have no such back channel, that you need asymmetric (i.e. public-key) cryptography like RSA or ECC. This is because you must exchange your keys over an insecure channel. Asymmetric cryptography relies on the hardness of problems such as prime factorization, which is what the current discussion is about.
FATMOUSE + YOU = FATMOUSE
This comment shows original thinking and, though you might not agree with it, a profound look on the current human condition. I'm shocked it's running at -1 right now.
/. fails us sometimes.
I guess
The lead researcher believes "the writing is on the wall" for 1024-bit encryption.
It should be noted (before people start panicking) that the 1024-bit key size refers to asymmetric or public-key cryptography (software like PGP, GPG, algorithms like DH/DSS, RSA), not to symmetric cryptography (software like TrueCrypt, algorithms like AES, Blowfish, Twofish, etc.).
A 256-bit symmetric key is completely infeasible to brute force and even if quantum computers become available, the complexity of brute force attack will still be 2^128 (which is again infeasible to brute force).
0100011001110101011000110110101100100000010000100
Patriotistically,
Philboyd Studge
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.
Erm, RSA uses composites. That's the problem.
Also FatPhil on SoylentNews, id 863
I always thought the easiest way to factor large numbers was to drop 'em off a high cliff and see what how it shatters once it hits the bottom.
(And they say a liberal arts degree's good for nothin'.)
Triv
You might not even need to learn it - you could just replay it in some situations.
Also FatPhil on SoylentNews, id 863
I figured if I don't try this, somebody else will. My TI-86 burst into flames while I was typing the factors in. When I pushed enter, it collapsed into a black hole which of course promptly fell through the floor and is no doubt as we speak falling towards the center of the earth, gaining mass as it goes, to eventually gobble the entire planet.
Just kidding.
The calculator spit out 5.89068299774 E310
Somebody wanna try it on an HP?
Titanic anyone?
The NSA's TRANSLATR would've had this computation figured out in no more than 4 hours!
Oops, sorry NSA, I meant TRANSLTR! Been too long since I read the book.
Mersenne prime update!!!
It's like the pacific World War II: nazis & japanese men were deciphering the british & american encrypted messages!!!
Their messages were encrypted with 1024-bit RSA!!!
This method was easy because 1039 is greater than 1024.
The german & japanese cryptographers like to decipher the british & american messages.
Over time as computers get faster and people write better programs any encryption code will be broken.
I think the most secure place in the world for any data, for now, is in the brain. Sometimes you enter something in it and no matter how hard you try you can't retrieve it. Now that is secure.
Now if I can find my keys...
Why tell you the calculation to generate the number, someone will just reverse engineer the number out of the hd-dvd/ blu-ray disc, like if they pick a random one; or figure it out by doing the math the way they did, you know a major university's servers are at work for a pirate right now. Forgive my ignorance if i missing something important
It wouldn't have mattered if they were using a rotating cleartext. TRANSLTR wouldn't have been able to crack that...
I guess another world record - the number with the biggest carbon footprint ... until CERN gets going and churns out new particle measurements to claim that crown again.
Is there anyone who dares to estimate the KWH used in this exercise?
Give your recipient some book. (Could be anything, preferably something long.) Then just send sets of three digit sequences of page#-paragraph#-word#. (You could encrypt those too if you wanted, but then you might be wasting time pushing it that far. Also you could add a fourth digit for letter/character in a word and mix it up on occasion.) Unless somebody else can figure out what exact book and publication of that book your recipient has as a key, good luck figuring out the message. And it's remarkably cheap to set up. Not to mention you could hand off some "recommended reading list" in public with some hidden schedule reference slipped in to rotate the keys now and then.
You haven't examined Xtianity very closely. Just to mention one of the more famous counter examples: Forgive them, for they know not what they do. I think your objection is more along the lines of "Why does God let people go to Hell, when He could stop them if He wanted to?"
http://science.slashdot.org/article.pl?sid=07/02/0 8/1355255
Halfway down UbuntuDupe says:
"No. If I needed to give someone in China the new encryption key, I'd simply put my own lock -- which only I have the key to -- on the suitcase. Then I'd ship it to him. Then he'd put his own lock on it (i.e., now it has my and his lock), and ship it back. Then I'd remove my lock and ship it to him. Then he'd remove his lock and open it."
Replace "new encryption key" with data. Replace later references to key and lock with OTP.
Works No?
Correction: he won't forgive them.
You know, God's not in the business of forgiving sin, he's in the business of rehabilitating sinners.
The number of digits in any positive integer x in base b is given by floor(log_b(x))+1. (Where the floor function "rounds down" to the nearest integer and log_b is the base-b logarithm.)
Thus, 2^1039-1 in base 10 has: floor(log_10(2^1039-1))+1 = floor(312.770165)+1 = 313 digits.
How did they find that out? Suddenly one of their Navajo communicators started talking with a German accent?
[clever sig]
fpgas are slow ;)
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
So...f ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff fffffffffffe :)
0x7ffffffffffffffffffffffffffffffffffffffffffffff
is prime...
Interesting
Who's first to write it as decimal here?
Who's to beat the lameness filter while writing it in binary?
45 5F E1 04 22 CA 29 C4 93 3F 95 05 2B 79 2A B2
5585366661 9936291260 7492046583 1594496864
6527018488 6376480100 5234631985 3288374753
×
2075818194 6442382764 5704813703 5946951629
3970800739 5209881208 3870379272 9090324679
3823431438 8414483488 2534053344 7691122230
2815832769 6525376091 4101891052 4199389933
4109711624 3589620659 7216748116 1749004803
6597355734 0925320542 5523689
=
1159420574 0725730643698071 48876894640753899791 70201772498686835353882248385
9966756608 0006095408005179 47205399326123020487 44028604353028619141014409345
3512334712 7396798885022630 75752809379166028555 10550042581077117617761009413
7970787973 8061870084377771 86828680889844712822 00293520180607475545154137071
1023817
is TRUE.
However, this value isn't equal to 2^1039 - 1.
The previous answer (=1.16e306) is between 2^1016 and 2^1017.
1729 = 9^3 + 10^3 = 1^3 + 12^3
11 months is quite good really, it took Deep Thought 7.5 million years to get to 42 !!!
That's the first time I'm hearing that. Wikipedia says a German engineer invented it in 1918 and sold it commercially. Neither the article history nor the discussion seems to argue against that.
Switch back to Slashdot's D1 system.
If you know in advance that you're going to start a war, you can do certain things during peacetime that are suspicious but not actually acts of war. For example, hire away the smartest upcoming new scientists in fields which have potential military applications. If they try to return to their home country after the war starts you can imprison them as traitors (don't execute them, that's free propaganda for your enemy), if they remain of their own free will you can use them for your own research programs, either way you deny their talent to your opponent. Or, as in this case, send legitimate researchers to discover things that might be difficult to find out once war is underway. In 1935 a German visitor to England could easily have discovered the location of important military bases, power plants, or heavy industry, drawn them on a map and returned without arousing suspicion. A few years later this would be cause for arrest and imprisonment or perhaps execution on charges of spying.
After WWI Germany was forbidden by treaty from creating an Air Force, because it was known that air support would be critical in any future war. So the government encouraged its people to learn to fly gliders and other primitive aircraft as an apparently harmless hobby. Of course this training significantly reduced the time needed to create an Air Force once Germany began to ignore the terms of its treaty. On the other hand they made the mistake of outlawing amateur radio, fearing that it would be useful to anti-government activists and, later, to the resistance in occupied countries. This meant that Germany was constantly short of skilled radio people, forcing them to expend more resources on "idiot proof" radar and communications hardware which could be maintained with minimal training and no radio knowledge, whereas Britain was able to easily find experienced amateurs who could operate and maintain their more primitive equipment.
There was an article a couple of years ago about someone filling a couple of racks with FPGAs, but the clock rates were only around 1-10MHz. Much too slow to be useful.
These days I'd imagine the NSA are using custom silicon. The logic is much simpler than an ordinary CPU (just repeated integer arithmetic cells) and there's much less external i/o. So clock rates in the low GHz sound pretty likely.
Given a large pile of money this should allow factorisation attacks in days rather than months.
Navajo as a written code would be near useless, I imagine. Navajo spoken on the battlefield is probably where the value was. If it takes you minutes to understand what was just said, that is a significant advantage. Still, writing down the words and cracking for the key nouns and numbers is about all it would take. Then when you heard those nouns and numbers again over the air you would have some idea what they are talking about. Navajo codetalking was all about battlefield communication I think, and is overrated today -- I mean, Japanese fought on for decades after the war ended due to their inferior communications setup.
I am not sure that Japanese ever much cared or doubted what American tactics would be, except maybe at sea. On land it was, "they will hit us hard everywhere", and they answered with human wave attacks. That kind of mis-match, and largely defensive tactics, hardly benefits from them learning what the Americans were up to every minute.
I come here for the love
For christsakes, at least read the list; I linked to it. And I did say only the public key algorithms, so AES isn't even relevant.
NSA Suite B:
What I said:
"...all the PK [public key] systems are based on elliptic curves, and not prime factorization, for the trapdoor function."
Of the algorithms in Suite B, AES and SHA aren't public-key algorithms; they're a symmetric block cipher and a hash function. The three relevant PK algorithms are ECMQV, ECDH, and ECDSA, and all of those are specifically noted as being "elliptic curve" variants, rather than the more common RSA-style prime-factorization-based algorithms.
PK algorithms which use elliptic curves use an entirely different set of mathematical functions as the basis for their 'trapdoor' or 'puzzle' (the function that's easy to compute but difficult to run backwards) from RSA. They're based on a variation of the discrete logarithm problem. (From what I understand, the purest form of the discrete logarithm problem isn't reversible at all -- you can run it in one direction, but from the output you can't figure out all of the input parameters were with certainty -- so specific variations of the general problem are used, of which elliptic curves are one.)
Given the popularity of RSA, I think its absence from the list is notable at the very least, and it's furthermore interesting that the NSA seems to really like elliptic curve systems as a basis for PK crypto. At least according to Wikipedia, nobody has ever published a proof of the mathematical hardness of elliptic curve systems...maybe they're even better than is currently realized. (Although, the real tinfoil hat response is, 'maybe they're really flawed somehow, and that's why the NSA wants you to use them!' However, I think this is doubtful for any number of reasons.)
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
There is at least one problem with a one-time pad. We *know* the information being sent, language. We know it's pattern.
Paul Anderson
"I drank WHAT?!" -- Socrates
Even simpler: He mails you his lock, you put it on the suitcase and ship it back to him. That's how asymmetric crypto (eg, PGP) works: I send you my public key, you encrypt a message with it and email it to me. And the practical problem is the same: verifying the authenticity of the lock, or public key.
Check out the wikipedia page on navajo code talkers. It even has the memo recommending navajo, as the navajo speaking tribes hadn't been visited by German anthropologist, unlike every other native american tribe.
SCO employee? Check out the bounty