Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

RSA-576 Factorization Officially Announced

timothy posted more than 10 years ago | from the what-google-does-in-its-spare-time dept.

Encryption 141

product byproduct writes "RSA Security finally has a news item about the December 2003 factorization of RSA-576. (See earlier Slashdot coverage). We now know what the computational cost was: the 174-digit number was factored "using approximately 100 workstations in a little more than three months"."

cancel ×

141 comments

Sorry! There are no comments related to the filter you selected.

So... (-1, Offtopic)

DarkHelmet (120004) | more than 10 years ago | (#8994961)

So... this is a news story, about a news story about something that's already posted on Slashdot.

Free karma everyone! Let's celebrate! Please link to the posts you choose to plagerize.

Thank you.

Re:So... (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8994973)

Yeah... except it took 2 months with 100 work stations to work that very thing out.

You seem much quicker though.

WARNING, PARENT IS A GOATSE LINK (-1)

Anonymous Coward | more than 10 years ago | (#8994990)

I'm at work you sick bastard

Re:WARNING, PARENT IS A GOATSE LINK (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8995056)

Yes, SourceForge has went downhill lately :-)

Re:So... (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8995287)

If I link to a post that I copy than I am not plagiarizing. am I?

0010010110 (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8994963)

01000110 01101001 01110010 01110011 01110100 00100000 01110000 01101111 01110011 01110100 00100000 01110011 01110101 01100011 01101011 01100101 01110010

It has to be asked... (-1, Troll)

troon (724114) | more than 10 years ago | (#8994966)

...why? What's the point?

Re:It has to be asked... (2, Interesting)

Sheetrock (152993) | more than 10 years ago | (#8994985)

Especially in light of all the projects one could be donating computer cycles to, such as protein folding or SETI.

What does this tell us? That if you throw enough machines and/or money at a solvable cryptographic challenge you'll solve it?

Re:It has to be asked... (1)

Chilliwilli (114962) | more than 10 years ago | (#8995022)

Couldn't agree more.. but from what I see they didn't use a distributed client.

Re:It has to be asked... (1)

Xilman (191715) | more than 10 years ago | (#8995479)

Couldn't agree more.. but from what I see they didn't use a distributed client.

Not entirely true. The article states that three of the contributors were part of NFSNET [nfsnet.org] which does have a distributed client.

Paul

Re:It has to be asked... (4, Insightful)

lewko (195646) | more than 10 years ago | (#8995028)

No.

It tells us HOW MANY machines we need to throw at the challenge.

The whole key to protecting information is to make it cost more to recover the information than it is worth.

For example, if information is going to need to be kept secret for twenty years, projects like this help you learn based on current technology, how much crypto is sufficent (or overkill).

Re:It has to be asked... (1)

ezzzD55J (697465) | more than 10 years ago | (#8995041)

For example, if information is going to need to be kept secret for twenty years, projects like this help you learn based on current technology, how much crypto is sufficent (or overkill).
True, although that only really matters for asymmetric (public/private, such as RSA) algorithms; for symmetric algorithms, you may as well use 256 bit keys, because it's just as fast as 128 bit keys, and minor breaks are unlikely to ever make attacks practical.

Re:It has to be asked... (1)

Chilliwilli (114962) | more than 10 years ago | (#8995053)

Surely a complexity calculation would suffice? After running a few iterations of the solver surely they could just calculate how long the key space would take to cover and divide by two.. why the need to run it until completion?

Re:It has to be asked... (3, Insightful)

RupW (515653) | more than 10 years ago | (#8995123)

Surely a complexity calculation would suffice? After running a few iterations of the solver

Because there's no motive to optimise the solver. Open up the project, offer a prize and you'll get many eyes looking for the absolute best solution - then you can study the complexity of that.

Re:It has to be asked... (0)

the_unknown_soldier (675161) | more than 10 years ago | (#8995057)

another everest perhaps???

Re:It has to be asked... (1)

cybervarun (774601) | more than 10 years ago | (#8995119)

In a sense, yes.
If we all remember our RSA encryption methods, or in fact any encryption method, they are all breakable, it's just a matter of enough computing power to do it. With RSA all you have to do is factor the big prime number pq into p and q and then you know phi = (p-1)(q-1) and from there you can get the decryption exponent no problem.

Encryption was designed to be just unbreakable enough, not totally unbreakable. 576-bits is a small one compared to what is often used for critical data these days, and every RSA factorization prize will be taken. But trust me it will be a lang time before you see the next ones show up, since eachadditional bit makes the problem a much harder one.

It'll be like this at least until quantum computing makes it all obsolete :) Every so often you will see that another RSA

Re:It has to be asked... (0)

Anonymous Coward | more than 10 years ago | (#8995445)

factor the big prime number pq into p and q

Well, as Bill Gates has told us, that would indeed an tremendous mathmatical advance.

I have a solution right now, assuming the big prime pq where p != 1: p = pq, q = 1.

Sorry. I'm sure you just mistyped it, but I couldn't resist.

Nothing compared to Distributed RC5-72. (0)

Anonymous Coward | more than 10 years ago | (#8995683)

More than 160000 PII 266MHz computers working 24 hours a day, 7 days a week, 365 days a year!

RC5-64 is so solved, they are solving how to crack RC5-72.

RC5-72:http://www.distributed.net/rc5/ [distributed.net]

open4free (c) (tm) (R)

Re:It has to be asked... (3, Insightful)

StarfishOne (756076) | more than 10 years ago | (#8996534)

IMHO projects like Folding@Home, TSC, United Devices, Lifemapper or ClimatePrediction.net are far more important then breaking a piece of encrypted material.

Like RC5 for example. If you break the RC5-64 key, everyone is happy. Then they want to break the RC-72 key.

Wow.. it takes ages and ages.. and what does it *really* proof?

Yes, it is breakable too.. wow. I'd rather have a few new medicins available, thank you :)

What I'm trying to say: there is plenty of computer power available on this world.. but not nearly near enough! There are far more important and interesting things to do with it then breaking some non-sense line of text!

do people care? (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8994972)

no, you dirty hippies, they do not

Lots of hardware... (5, Insightful)

basil montreal (714771) | more than 10 years ago | (#8994982)

That's a ton of computer hardware to use on factoring... I wonder why they didn't just use a distributed system (like seti@home) to do this... at least it's free.

Re:Lots of hardware... (5, Interesting)

ezzzD55J (697465) | more than 10 years ago | (#8995023)

Because it's difficult to efficiently parallelize (distribute) the factorisation algorithm, especially the final step which so far has always happened on 1 machine. In fact, if you can paralellize the final step of the GNFS (general number field sieve is generally used for these factorisations), you have yourself a PhD. thesis (in math and/or CS), I remember reading in sci.crypt.

Re: i'm super-intelligent like HAL9000. (0)

Anonymous Coward | more than 10 years ago | (#8995415)

With my PC, I can crack RSA-4096 using Quantic Computing, hehehe, the algorithms are so very difficult and unknown by the people.

open4free (c) (R) (tm)

Re:Lots of hardware... (1)

jmdjmd (727273) | more than 10 years ago | (#8995033)

You mean like the contribution of http://www.nfsnet.org/ ? And not everything can be done there - the final step (the matrix step after the sieving) isn't easily done in parallel. It was done on a Cray at the CWI for the previous challenge, and this one used a 16-computer high-speed LAN I think.

Re:Lots of hardware... (3, Insightful)

Chilliwilli (114962) | more than 10 years ago | (#8995074)

I'm sorry but factorisation problems and SETI really infuriate me. Firstly we can calculate how long something will take to compute with ease using simple the simple CS complexity analysis we all learnt at university.. then theres the SETI people.. not that I don't want to know whether there's life on other planets but to be honest there is so much we don't understand on our own planet that could have far greater reward for us all. Things I'm talking about might be research into climate, new fuels, medicines. The only distributed task I contribute to is folding@home because all others don't seem worth the extra energy and heat my PC will put out.

half agree (1)

essreenim (647659) | more than 10 years ago | (#8995223)

I think that distributed computing is wonderful. It allows us to divide and conquer which is what the developed world should be about.

I agree that the analysis could just as effectively be done using bif-O notation and all that, but I still dont think we should knock it.
If you have a problem with people factoring RSA keys, then just dont take interest - go somewhere else.

Personally, I would like to distributed computing used to find out more about the origins of our universe etc..

Re:half agree (1)

essreenim (647659) | more than 10 years ago | (#8995316)

That would be big-O

Re:half agree (1)

GTRacer (234395) | more than 10 years ago | (#8995641)

Big-O! Big-Ooo Biiig-Ooo Big-O! Bwaaaaaaa Ba Bwaa bwaaa...

GTRacer
- R. Dorothy can take my mod points any day

Re:Lots of hardware... (1)

KingOfBLASH (620432) | more than 10 years ago | (#8996231)

There are plenty of projects out there like that, you just have to search for them. I just posted a comment on the granparent about distributed.net, and I personally am working on a distributed computing project to debut in the summer looking for concatanated primes, The Catcon Project [sourceforge.net]

Re:Lots of hardware... (1)

KingOfBLASH (620432) | more than 10 years ago | (#8996191)

Go to distributed.net [distributed.net] and download their client. You can work on factoring RC5-74 (a 74 bit number from RSA). They've just finished up RC5-64 (A 64 bit number from RSA). If your computer finds the key, you get $1,000 and $8,000 goes to charity. They also have other distributed projects, like seti@home, including one to search for mathematical constructs known as Optimal Golumb Rulers. The best part is the client runs at the minimum priority, so you only give up cpu cycles if you don't need them. I've yet to notice any kind of lag because it was running on my machine.

Still safe for a while (5, Interesting)

BuddieFox (771947) | more than 10 years ago | (#8995002)

We should still be reasonably safe using the RSA-algorithm for a while more since the number is the equivalent of a 576-bit key. Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).

Safe, that is unless someone invents quantum computers and makes them easy to produce.. :)

Re:Still safe for a while (-1, Interesting)

Sheetrock (152993) | more than 10 years ago | (#8995025)

Bear in mind, using bits to exponentially increase cryptographic strength only works until you reach the Berenstein factor, which is a practical limit on the number of S-boxes that can be stacked in any particular corner of the cryptographic chamber. After a certain point, which varies according to the chamber ceiling, it is possible albiet less space efficient to take advantage of parallel stacking to some extent.

As with cryptographic cracking, it comes down to the speed and capability of the hardware above all else. Sometimes algorithms can be tweaked (as by adding bits to the key) but it's important not to focus on any particular attribute or assume a characteristic of one cryptographic function holds true for all of them, or even across the same class (such as block ciphers).

Re:Still safe for a while (4, Informative)

Ckwop (707653) | more than 10 years ago | (#8995055)

Wow nice random word generator.. Can I have a go?

Seriosuly, It's utter rubbish. I mean please explain to me how you stack an S-box into a corner of a cryptographic chamber..

It's just a substitution you muppet.. And cryptography isn't all hardware speed.. I mean WEP [berkeley.edu]

was broken with trivial computing power!

Simon.

Re:Still safe for a while (1)

El Neepo (411885) | more than 10 years ago | (#8995904)

WEP had a flaw in the protocol.

The flaw made it possible to inject unauthorized packets and reduce the time/space needed for brute forcing the key.

Re:Still safe for a while (1)

Martin Blank (154261) | more than 10 years ago | (#8996205)

That was exactly his point. Much is made of how long it takes to crack whatever random bit of encrypted text because almost everyone loves the idea of brute-forcing their way through a problem, but few people can even see -- let alone appreciate -- the elegance of the guy in the corner working quietly on whittling away at an algorithm. Anyone can attack a problem with raw computing power, but how many people can poke at methods of streamlining the computation to bring down the difficulty by a few orders of magnitude, eventually making some of the toughest algorithms beatable within their lifetime?

Personally, I think it speaks volumes that NSA isn't satisfied with 256-bit algorithms like AES and are pushing for 512- and even 1024-bit in certain government circles. Makes one wonder what weaknesses they've found that concern them.

Re:Still safe for a while (2, Interesting)

andalay (710978) | more than 10 years ago | (#8996209)

WEP had a flaw in the protocol.

The flaw made it possible to inject unauthorized packets and reduce the time/space needed for brute forcing the key.

Thanks for demonstrating a common misconception in cryptography: it is all about encryption and decryption. Its not. Its also about the algorithms and protocols you use in your applications. Encryption/decryption is a factor in the security but it is not the whole point of cryptography.

As a result, when people break SSL,WEP, it is as much a part of practical cryptography as factoring integers

Re:Still safe for a while (5, Informative)

thedanc (449477) | more than 10 years ago | (#8995097)

Bear in mind, using bits to exponentially increase cryptographic strength only works until you reach the Berenstein factor, which is a practical limit on the number of S-boxes that can be stacked in any particular corner of the cryptographic chamber. After a certain point, which varies according to the chamber ceiling, it is possible albiet less space efficient to take advantage of parallel stacking to some extent.

Mods -- how could you let this get modded up? First, S-boxes are in DES, not RSA. Next, even if the random reference was to the correct cryptographic algorithm, the rest of the comment still makes no sense at all.

C'mon people, post if you have a clue, and only if you have a clue.

Re:Still safe for a while (0)

Threni (635302) | more than 10 years ago | (#8995113)

> C'mon people, post if you have a clue, and only if you have a clue.

Yeah, like that request is going to work. I find people posting nonsense here and having it modded up as insightful amusing. It's just an extension of what happens elsewhere.

FWIW (-1)

Anonymous Coward | more than 10 years ago | (#8995191)

The origianl poster knew exactly what he was doing. And he was successful. He was testing slashbots and moderators, under completely transparent conditions so that we might make our own observations of his experiment.

My conclusions: People are still gullible.

Re:FWIW (0)

Anonymous Coward | more than 10 years ago | (#8996066)

And I'd like to also add "petty."

Re:Still safe for a while (0)

Anonymous Coward | more than 10 years ago | (#8995484)

Ahh but you fail to factor for time warp field obsucrsion.

Re:Still safe for a while (5, Interesting)

Ckwop (707653) | more than 10 years ago | (#8995026)

Also remember the moore's law doesn't apply to factoring algorithms.. This is because for the GNFS the *memory* speed is what's important and that isn't growing nearly as quickly..

Not convinced? Look at the linear proportionality in this graph [inria.fr]

Simon.

Re:Still safe for a while (1, Informative)

Anonymous Coward | more than 10 years ago | (#8995110)

You complete idiot. Linearity in the _length_ of the key vs. year means _exponentially_ faster-running factoring over time. But if you couldn't figure that out for yourself, you could at least look up your screen a couple of inches where they state:

For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

At any rate, time to go buy a G5 I think, they are supposed to have pretty fast memory.

Re:Still safe for a while (2, Insightful)

cortana (588495) | more than 10 years ago | (#8995152)

For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

Sorry for sounding like a dick, but Moore's Law states that the number of transistors per unit area doubles every eighteen months. This does not directly correspond to an increase in computer "speed".

Re:Still safe for a while (0)

Anonymous Coward | more than 10 years ago | (#8995184)

well why don't you do something constructive for a change and enlighten the authors of the article in question instead of me you useless slashdot faggot

Re:Still safe for a while (1)

thogard (43403) | more than 10 years ago | (#8995364)

no, but history has shown if you can get 2x the transistors you can solve more than 2x the problems at the same time.

If my package limit only allows 16,000 transistors but in 4.5 years you get 128,000 transistors, you can solve far more problems and that can give you far more preformace than Moore's law by its self.

Re:Still safe for a while (1)

AmericanInKiev (453362) | more than 10 years ago | (#8995487)

Sure it does.

Even if one did not INCREASE the number of total transistors - the fact that they are closer together means the clock propogation delay is reduced thus MHz can increase without loss of synchronicity.

electricity does not travel even as fast as the speed of light - that and heat dissapation are the primary barriors to Moore's law.

AIK

Re:Still safe for a while (-1, Redundant)

Alomex (148003) | more than 10 years ago | (#8995209)

The following was posted by an AC, presumably because he was afraid of losing Karma. However it is right on the money, so I'll post it under my name and karma-whore for it. As I said he's absolutely right.

You complete idiot. Linearity in the _length_ of the key vs. year means _exponentially_ faster-running factoring over time. But if you couldn't figure that out for yourself, you could at least look up your screen a couple of inches where they state:

For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

At any rate, time to go buy a G5 I think, they are supposed to have pretty fast memory.

Unless... (1)

RKBA (622932) | more than 10 years ago | (#8995088)

Unless someone comes up with a better factorization algorithm. In fact, if anyone knows of a software package that can solve a system of 640 boolean equations in 640 boolean unknowns, I can give you the factorization of the RSA-640 challenge number [rsasecurity.com] . :-)

Re:Unless... (1)

ezzzD55J (697465) | more than 10 years ago | (#8995134)

As it happens, satisfiability [satlive.org] algorithms can solve systems of 640 variables quite easily. No, it's true they can't solve 640-bit factorisations yet, or they would have :). The difficulty of satisfiability systems for randomly generated problems lies much more in the ratio of clauses to variables than number of variables alone.

Re: it's not trivial. (0)

Anonymous Coward | more than 10 years ago | (#8995528)

They are not 640 variables, they are more.
I *believe* that they are O(k*n^2) or possiblely worst-case O(k*n^3) boolean variables for SAT.

For n = 640 bits, n^3 = 262'144'000 boolean variables, you will need a cheap little-expensive 64-bit supercomputer like Opteron 148 with a lot of RAM!!!.

open4free (c) (R) (tm)

Safe from whom? (1, Insightful)

dcavanaugh (248349) | more than 10 years ago | (#8995124)

OK, it took 1000 machines and 3 months for this particular example. The task is not impossible, and there are people who really can get their hands on 1000 machines.

If the goal is personal security, I agree that the average credit card hacker is not going to make the investment. On the other hand, the NSA has the hardware resources to attack on a grand scale, with perhaps even better algorithms.

It will be a while before RIAA and MPAA can hijack NSA resources to pursue P2P users, so I guess we ARE still safe for a while.

Re:Safe from whom? (1)

tolan-b (230077) | more than 10 years ago | (#8995169)

it took 1000 machines

100

Re:Still safe for a while (1)

andy666 (666062) | more than 10 years ago | (#8995317)

Yes, but more importantly, this shows the superiority of elliptic curve cryptography - compare this with the size of the recently cracked elliptic curve key.

Re:Still safe for a while (1)

tomstdenis (446163) | more than 10 years ago | (#8995359)

Surperior in what sense? ECC is typically slower [though not by a wide margin] on desktop processors where multiplication is not that expensive.

Sure ECC has the size thing beat and is better suited for smaller machines, oh and is neater math, but that's about it ;-)

Tom

Re:Still safe for a while (2, Interesting)

dmaxwell (43234) | more than 10 years ago | (#8995832)

The rules are different for public key cryptography. You are correct in that every bit added to a symmetric crypto key doubles the keyspace. In public key crypto which RSA is one type of, it is necessary to add 10 bits to double the difficulty. That 10 bit number is somewhat fuzzy. It can be a little more or a little less depending on whether we are talking about elliptic curves or Diffie-Hellman and others.

Security (5, Insightful)

nuclear305 (674185) | more than 10 years ago | (#8995035)

Of course, the whole idea behind key strength is rather moot if the user gets careless with his keys/passphrase.

Unfortunately, crypto is only as strong as the user(weakest link)

While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.

Of course, unless you're the NSA and measure their servers by acres...

Re:Security (4, Interesting)

CoolGopher (142933) | more than 10 years ago | (#8995093)

we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.

Of course, unless you're the NSA and measure their servers by acres...

Or if you grabbed the source for the latest windoze worm and modded it to bruteforce keys in addition to spreading...

I have a suspicion that doing that would give you a supercomputer that quite possibly ranked #1 on the supercomputer charts, and for free to boot*.

*) Comes with complimentary government provided lodging and meals.

Re:Security (0)

Anonymous Coward | more than 10 years ago | (#8995146)

> *) Comes with complimentary government provided lodging and meals.

Only if, as in the Unabombers case, your brother helpfully provides your details to the FBI. Lets face it - they're not going to catch anyone without any help, are they, as McVeigh, Unabomber, 9/11 etc have shown only too clearly.

Re:Security (1)

foidulus (743482) | more than 10 years ago | (#8995194)

While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.
While that may be true, there is still a significant chance that, with less hardware, the hacker can always get "lucky" and be able to use less computing power to "guess" the factorization. For instance, a hacker could just start with a prime number that is an arbitrary distance from the square root and just use less computing power to keep on guessing(guessing distributes very well, but it is incredibly inneficient). The same calculations that show the maximum amount of time that guarentee them the key also show there is a good chance they could stumble upon it.

Re:Security (1)

Xilman (191715) | more than 10 years ago | (#8995581)

Actually, the chance is negligible if you try that algorithm. Guesswork just doesn't cut it, unless you like betting at odds of 10^170 to one against.

Responding to the parent post: rather a lot of hackers have easy access to 100 node farms. It's not difficult any more to find 100 cpus, especially for an algorithm such as GNFS which doesn't need especially fast communications between them. The final stages are more of a bottleneck than the sieving, but far from impossible for reasonably clueful people.

Paul

Re:Security (1)

thogard (43403) | more than 10 years ago | (#8995409)

I think that RSA's weakest link is the "Euclidian algorithm" which has a few a few other options.
RSA keys aren't 1:1 and while my math isn't good enough to prove it, they are 1:many as this code [abnormal.com] shows how it works.

The advantage of one way encryption... (3, Funny)

MosesJones (55544) | more than 10 years ago | (#8995040)


I encrypt everything on my hard-drive using one-way compact encryption, it only cost me $100 and converts every file into 0 bytes that can't be de-crypted by anyone... not even me. Now THAT is proper security.

I previously used 2^(10e20) bit encryption which would have taken several universes to crack. Unfortunately it took one earth life to encrypt a 1 Mb file so I had to revert to the super-secure method above.

And Yes I do have a tin-foil hat... why do you ask ? Oh and the application that does the one way encryption. Well I work on Windows but I get this Unix utility called Cygwin and the guy sold me a program that does the encryption. I had a look at what was in encrypt.sh and what it says is

cat /dev/null > $1

Amazing how simple UNIX makes encryption... but then I use Windows so its all beyond me.

Re:The advantage of one way encryption... (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#8995062)

Lamest attempt at funny karma-whoring I've seen for some time...

Hundred computers * 3 months (5, Interesting)

Gopal.V (532678) | more than 10 years ago | (#8995046)

That makes it 240000 computer hours ... too cheap .. Think about this :

"Toy Story 2" had about 800,000 computer hours worth of rendering.
"The Hulk" had 2.5 Million computer hours [nydailynews.com]
My office has nearly 400 fast machines , imagine this running them makes it 25 days . Running that every weekend makes it 12 weeks or 3 months ... It's a weekend job if I can sneak this in as along with the next upgrade.

DDoS time is over with all networks being careful about... the next big windows worm will be a distributed processing program :)

Re:Hundred computers * 3 months (3, Interesting)

duffbeer703 (177751) | more than 10 years ago | (#8995130)

Think about the commercial application of cyrpto... would anyone invest Pixars IT budget to steal a few credit card numbers?

Even with military-style secrets, timing is key. If a US war plan is intercepted by a foreign intelligence service, only to be decrypted months later, that data is pretty useless.

Re:Hundred computers * 3 months (2, Interesting)

Short Circuit (52384) | more than 10 years ago | (#8995196)

would anyone invest Pixars IT budget to steal a few credit card numbers?

It depends on the credit limits of the cards, and whether or not the holder knows the data's been accessed..

Factoring in advance (1, Interesting)

Anonymous Coward | more than 10 years ago | (#8995058)

If you knew that factoring big numbers was important to breaking encryption, and would be for quite a long time wouldn't you simply have started a huge factoring effort decades ago? I know I would have.

Re:Factoring in advance (3, Insightful)

RupW (515653) | more than 10 years ago | (#8995099)

If you knew that factoring big numbers was important to breaking encryption, and would be for quite a long time wouldn't you simply have started a huge factoring effort decades ago? I know I would have.

Factoring what? You won't know the number you need factored until you intercept or steal the encrypted data.

You could, I suppose, start multiplying every pair of primes together and try and organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

Re:Factoring in advance (1)

ezzzD55J (697465) | more than 10 years ago | (#8995158)

Factoring what? You won't know the number you need factored until you intercept or steal the encrypted data.
Not true, because if you can factorise the modulus in the public key (which is generally easy to get), you can generate the private key.. That's the whole point to this factorisation business :)

Re:Factoring in advance (2, Informative)

RupW (515653) | more than 10 years ago | (#8995318)

Not true, because if you can factorise the modulus in the public key (which is generally easy to get), you can generate the private key.

Yeah, that was misleading - I was just trying to say you need a target for your arbitrary factor effort. In my mind I'd figured you'd have to have the encrypted message to know what private key it was encrypted for - although I realise now that's not necessarily true (and neither's the reverse). But it could be for real tinfoil-hat types :-)

There's no good reason, either, why a public key can't be kept as confidential as a private key or a symmetric cipher key - it's just that once you publish it to a few people there are more points of failure. And if you don't have the public key (in GPG's implementation at least) you don't have anything to try and factorise because it's not bundled with the encrypted data.

Re:Factoring in advance (5, Insightful)

tadmas (770287) | more than 10 years ago | (#8995379)

You won't know the number you need factored until you intercept or steal the encrypted data.

You don't have to steal anything. The number to factor (the modulus) is given away as part of the public key.

organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

For 1024-bit numbers, the factors will be on the order of 512-bits. The density of primes is rougly 1/ln(n), and ln(2^512) is about 355, so you should expect around every 355 numbers to be prime. That's only 3e151 numbers, not to mention that you'd have to figure every product of the two, which is 0.5*(3e151)^2, or 7e302 numbers.

Staggering doesn't begin to describe how many of these things you'd have to store.

Re:Factoring in advance (0)

Anonymous Coward | more than 10 years ago | (#8996261)

not to mention that you'd have to figure every product of the two, which is 0.5*(3e151)^2, or 7e302 numbers

Err, while division is indeed a bit slower than multiplication it might pay off in this very case..

Re:Factoring in advance (0)

Anonymous Coward | more than 10 years ago | (#8996071)

How would you store it?
There is less than 10^100 atoms in the universe.

40 Licks (3, Funny)

thpdg (519053) | more than 10 years ago | (#8995063)

It begs the question, how many workstations, for how many months, would it take to find out
How many licks does it take to get to the center of a Tootsie Pop?
I'm afraid the world will never know.

Re:40 Licks (0)

Anonymous Coward | more than 10 years ago | (#8995078)

The response from the master machine was "Ask Mr. Owl."

Re:40 Licks (-1)

Anonymous Coward | more than 10 years ago | (#8995080)

That was so retarded, it hurt.

Re:40 Licks (2, Funny)

Anonymous Coward | more than 10 years ago | (#8995125)

Theh-Ree.

Re:40 Licks (1)

bryane (614590) | more than 10 years ago | (#8995692)

1

2

3

CRUNCH

3

If anyone wants... (3, Informative)

Phidoux (705500) | more than 10 years ago | (#8995094)

... to waste 3 months and 100 computers trying to read my RSA-576 encrypted information, they are welcome

Re:If anyone wants... (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8995189)

Can the moderation be modded as funny?

Too late (-1, Troll)

mkro (644055) | more than 10 years ago | (#8995100)

Of couse, NSA found a way to do the exact same thing with a Casio pocket calculator back in 1973.

128 bits for symmetric cryptography (0)

Anonymous Coward | more than 10 years ago | (#8995112)

I remember an article written some time ago
from a Dutch (I think) guy. He was stating that
for symmetric cryptography (i.e not RSA,
Diffie-Hellmann and the likes) a 128 bit long
key is enough. He was making the assumption
that cracking a 128 bits key (again, for a
symmetric algorithm) would produce, even with
processors 1000 more efficient heat-dissipation
wise than current chips, so much heat that the
Netherlands would be under sea level due to ice
melting.

However, I cannot remember where I read it, and
can't find it with Google. Can someone please
provide a pointer for this article? Now that
I'm more savvy with cryptography, I'd like to
double check if the paper indeed make sense or
if it is just a bunch of BS.

Re:128 bits for symmetric cryptography (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8995336)

Well, The Netherlands are also known as "Holland" ("hole - land") for the fact that 1/3th of their country lays below the sea-level [wish.net] already .
(that's one of the reasons you're best off hiring a Dutchman to build your dams, just think back of the Delta project [iadc-dredging.com] .)
So flooding it wouldn't be such a "dramatic effort".

Virginia Tech (1, Interesting)

artlu (265391) | more than 10 years ago | (#8995159)

If you think about it, this means that VA could do 1024 bit in 1month. Gotta love the G5 supercomputer!
artlu [artlu.net]

Re:Virginia Tech (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8995214)

fucking mac faggot

Re:Virginia Tech (3, Insightful)

Chexum (1498) | more than 10 years ago | (#8995418)

Uh, oh, someone is bad at math...

I don't think VA's unknown numbered G5 park is about 2^448th more powerful than 100 PC(?) nodes. I don't think it's possible.

Or, I simply have been trolled :)

On the other hand, let me check my sig again...

Re:Virginia Tech (0)

Anonymous Coward | more than 10 years ago | (#8996419)

That'd be you, sir. That the algorithm is superpolynomial doesn't mean that every bit doubles the effort needed.

Re:Virginia Tech (0)

Anonymous Coward | more than 10 years ago | (#8995582)

shutup

Why waste all the CPU power? (4, Funny)

tangent3 (449222) | more than 10 years ago | (#8995380)

There's a far easier [slashdot.org] way to crack the the key

Re:Why waste all the CPU power? (1)

the MaD HuNGaRIaN (311517) | more than 10 years ago | (#8995881)

if(location.equalsIgnoreCase("Soviet Russia")){
SecrtetKey.crack(sessioin.getRemoteUser());
}

Anyone know what the predicted strenght was? (3, Interesting)

pmcevoy (10501) | more than 10 years ago | (#8995485)

Does anyone know what the predicted lifetime of the 576 bit key was?

I mean, when they say that we should be using 4096bit keys today, how long do they predict that it will take to crack that key? (taking into account Moores law and perhaps linear growth over time of the number of clients contributing CPU cycles). Is it possible to guestimate?

Jens Franke (5, Interesting)

greppling (601175) | more than 10 years ago | (#8995501)

(As far as I understand, he and Thorsten Kleinjung wrote most of the software used, and did most of the work in the project, while the other institutions were rather donating computing time.)

I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating. His office consists of 3 huge desks (plus a computer desk); on each of them there is huge bunch of completely unorganized papers lying around, mixed with empty yoghurt cans.

His mathematical skill is enormous, he has done research in quite a lot of different areas of mathematics (analysis, algebraic geometry, algebraic topology, category theory), but he never bothers at all with making his results well-known. (In fact, at least one time he actually had to be persuaded to even publish his result, which got immediately accepted in Inventionaes, the most highly regarded journal in pure mathematics.) He even couldn't be bothered to apply for a much better-payed position at another university in Germany when he was almost urged to do so.

Anyone who knows him will burst out laughing when he reads that he supposedly said "I'm very proud of all these individuals from around the world and their efforts to solve this first factoring challenge." and all this other stuff in that paragraph of the article. I bet the author of this press release desperately tried to get some phrases longer than 5 words out of his mouth, gave up, and then decided to just make up all the quotes.

Now with his mathematical skills, number factoring is (in his own opinion) a rather dull activity. The reason he is doing this is that he expects an economic breakdown soon, and he thinks of his knowledge in number-factoring as an assurance against the coming job crisis. (Of course, his position is guaranteed by the German state until his retirement.)

But if you manage to get along with him, he is actually quite nice and extremely helpful.

Re:Jens Franke (2, Interesting)

Xilman (191715) | more than 10 years ago | (#8995707)

I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating.

I also know Jens quite well (we are on first-name terms) and he seems sane enough to me. Perhaps I have hung around with mathematicians too much!

But if you manage to get along with him, he is actually quite nice and extremely helpful.

Seconded. Thorsten Kleinjung is also one of the good guys and very helpful.

Paul

m!od down (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8995622)

exactly what 7Ou've

Next Time, Hire Google (3, Interesting)

VernonNemitz (581327) | more than 10 years ago | (#8995929)

They say that Google is preparing an IPO, but sometimes I wonder what they need the money for. They already had enough money for 10,000-100,000 servers, after all. If they doubled or quintupled that acreage of computer-farm, would your search-results come to you down the Internet pipe so much faster that you'd be glad the did?

And they had the money to hire the experts needed to manage that cluster like a single supercomputer. Sure, they probably got some of that initial funding from ordinary venture capitalists, but what if some Govt. outfit helped, on the grounds of requesting access for occasional factoring purposes? After that IPO gets invested in a bigger farm, not even 2048-bit keys may be safe.

So, has any Slashdot reader checked the results? (1)

dpbsmith (263124) | more than 10 years ago | (#8996174)

Does the numeral posted here [rsasecurity.com] actually equal the product of the numerals posted here? [rsasecurity.com]

The last digit looks OK, anyway. :-)

No, don't bother to flame me for laziness... I already know...

There was a time when I would have tried to do that on paper by hand, just to keep in practice. These days, not only am I too lazy to try that, but I don't currently have any software system at hand that implements indefinite-sized integer arithmetic... and I'm too lazy to implement one.

Re:So, has any Slashdot reader checked the results (1)

nebaz (453974) | more than 10 years ago | (#8996508)

java does this. It works on most platforms. See java.math.BigInteger

soooo.... (2, Insightful)

MasTRE (588396) | more than 10 years ago | (#8996348)

It took longer for them to come up with the press release than it did for their code to be broken. Lookin' good, RSA!
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?