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 Factored

michael posted more than 10 years ago | from the long-division dept.

Encryption 321

An anonymous reader writes "I thought Slashdot would have picked this up several days ago, but apparently not. Although you still won't see any mention of it on the RSA challenge site, Mathworld is carrying the news that a team at the German Bundesamt fur Sicherheit in der Informationstechnik submitted a factorization of RSA-576 on December 3. RSA-576 is the smallest challenge number that RSA Security offers a cash prize for, to the tune of $10,000"

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

GNAA Ass Packer (-1, Troll)

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

GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the first organization which
gathers GAY NIGGERS from all over America and abroad for one common goal - being GAY NIGGERS.

Are you GAY [klerck.org] ?
Are you a NIGGER [tux.org] ?
Are you a GAY NIGGER [gay-sex-access.com] ?

If you answered "Yes" to any of the above questions, then GNAA (GAY NIGGER ASSOCIATION OF AMERICA) might be exactly what you've been looking for!
Join GNAA (GAY NIGGER ASSOCIATION OF AMERICA) today, and enjoy all the benefits of being a full-time GNAA member.
GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the fastest-growing GAY NIGGER community with THOUSANDS of members all over United States of America. You, too, can be a part of GNAA if you join today!

Why not? It's quick and easy - only 3 simple steps!

First, you have to obtain a copy of GAY NIGGERS FROM OUTER SPACE THE MOVIE [imdb.com] and watch it. (click here to download the 280MB MPEG from BitTorrent [idge.net] )

Second, you need to succeed in posting a GNAA "first post" on slashdot.org [slashdot.org] , a popular "news for trolls" website

Third, you need to join the official GNAA irc channel #GNAA on EFNet, and apply for membership.
Talk to one of the ops or any of the other members in the channel to sign up today!

If you are having trouble locating #GNAA, the official GAY NIGGER ASSOCIATION OF AMERICA irc channel, you might be on a wrong irc network. The correct network is EFNet, and you can connect to irc.secsup.org or irc.easynews.com as one of the EFNet servers.
If you do not have an IRC client handy, you are free to use the GNAA Java IRC client by clicking here [nero-online.org] .

If you have mod points and would like to support GNAA, please moderate this post up.

This post brought to you by Penisbird [nero-online.org] , a proud member of the GNAA

G_____________________________________naann_______ ________G
N_____________________________nnnaa__nanaaa_______ ________A
A____________________aanana__nannaa_nna_an________ ________Y
A_____________annna_nnnnnan_aan_aa__na__aa________ ________*
G____________nnaana_nnn__nn_aa__nn__na_anaann_MERI CA______N
N___________ana__nn_an___an_aa_anaaannnanaa_______ ________I
A___________aa__ana_nn___nn_nnnnaa___ana__________ ________G
A__________nna__an__na___nn__nnn___SSOCIATION_of__ ________G
G__________ana_naa__an___nnn______________________ ________E
N__________ananan___nn___aan_IGGER________________ ________R
A__________nnna____naa____________________________ ________S
A________nnaa_____anan____________________________ ________*
G________anaannana________________________________ ________A
N________ananaannn_AY_____________________________ ________S
A________ana____nn_________IRC-EFNET-#GNAA________ ________S
A_______nn_____na_________________________________ ________O
*_______aaaan_____________________________________ ________C
um, dolor. Nunc nec nisl. Phasellus blandit tempor augue. Donec arcu orci, adipiscing ac, interdum a, tempus nec, enim. Phasellus placerat iaculis orci. Crasa sit amet quam. Sed enim quam, porta quis, aliquet quis, hendrerit ut, sem. Etiam felis tellus, suscipit et, consequat quis, pharetra sit amet, nisl. Aenean arcu massa, lacinia in, dictum eu, pulvinar ac, orci. Mauris at diam tempor ante ullamcorper molestie. Ut dapibus eleifend ipsum. Nam dignissim.

Worth every hour. (-1, Offtopic)

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

Even though it took us three days to figure it out, to be honored by the RSA feels so good. I want to thank everyone for helping us achieve this!

Re:Worth every hour. (-1, Troll)

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

Ha, you wish you were involved. You probably aren't even German you kraut-wannabe

Factor this! (-1, Offtopic)

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

Second post! w00t!

shit (-1, Offtopic)

frogsarefriendly (723785) | more than 10 years ago | (#7656992)

Lameness filter encountered. Post aborted!
Reason: Please use fewer 'junk' characters.

MOD PARENT INTERESTING (-1)

Rectal Examination (711652) | more than 10 years ago | (#7657022)

etc.

YOU FAIL IT (-1, Offtopic)

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

omg, is that shit on your face???

Bring on the spam! (-1, Offtopic)

lisany (700361) | more than 10 years ago | (#7656997)

"plz plz plz plz join my team i wan the money so i can git a d8 4 da prom!"

Can't wait to see that from the people who have no idea what encryption is for.

Dinosaurs? (-1, Offtopic)

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

Will this allow us to clone dinosaurs and place them in a futuristic theme park?

Re:Dinosaurs? (-1, Redundant)

RightInTheNeck (667426) | more than 10 years ago | (#7657024)

Yes.

I think my form of encryption is better (3, Funny)

Wigfield (730339) | more than 10 years ago | (#7657006)

Ontday oyay inkthay osay?

Re:I think my form of encryption is better (4, Insightful)

cgranade (702534) | more than 10 years ago | (#7657028)

I don't know... maybe...
u sib;r jbiq (shifted all the keys to the left.)

Seriously, though, all of these ciphers can be broken. It's just a task of minimizing the value to the cracker by making it take as long as possible to get the data, under the thought that it just won't be worth the time.

Re:I think my form of encryption is better (4, Insightful)

wurp (51446) | more than 10 years ago | (#7657237)

Sure, all codes (except one time pads and equivalents) can be broken. The difference is whether it takes a day to crack the code or it can be proven that it requires either a centuries-sought breakthrough in mathematics or all the computers in the world working for ten thousand years.

I don't know how you feel about it, but quantitative differences on those scales qualify as qualitative differences to me. Your 2048 bit PGP key simply isn't crackable by any reasonable standard. The reason people succeed at these challenges is because the bar has been set intentionally low.

Re:I think my form of encryption is better (5, Informative)

hank (294) | more than 10 years ago | (#7657272)

They also set the bar at your "reasonable standard" - the factorization of a 2048-bit number brings in $200,000 USD.

http://www.rsasecurity.com/rsalabs/challenges/fa ct oring/numbers.html

Re:I think my form of encryption is better (1)

Snoopy77 (229731) | more than 10 years ago | (#7657037)

Ontday oyay inkthay osay?

otgay otay dmitaay tiay siay rettypay oodgay.

Re:I think my form of encryption is better (0)

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

Amnday itway, ywhay oesday onay oneway earnlay otay useway igpay atinlay operlypray?

If the word starts with a vowel sound, you just append way.

Re:I think my form of encryption is better (0)

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

You missed a 'u' in the second word.

Unless, of course, that was meant to happen in an effort to throw off someone trying to crack the cypher. In that case, it's ingenious!!!

It wold be good to se the letter " " no frther.

MOD PARENT GAY (-1, Offtopic)

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

see subject, tea bagger.

Re:I think my form of encryption is better (1)

LeninZhiv (464864) | more than 10 years ago | (#7657115)

V guvax gurer fubhyq or n fynfuqbg frpgvba jurer nyy cbfgf unir gb or va EBG13.
Guvf fvgr qbrfa'g yrg zr jnfgr rabhtu gvzr nf vg vf!

And while we're on this kind of thing, does anyone know what the point of the UNIX command "rev" is? (as in "$ echo This is pointless | rev" -> sseltniop si sihT)? Why on earth does that come installed on Debian, and does every distro and UNIX variant use it?

Re:I think my form of encryption is better (5, Funny)

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

it's so you can read the screen when you look at it over your shoulder with a mirror.

Re:I think my form of encryption is better (5, Funny)

the_argent (28326) | more than 10 years ago | (#7657178)

Or my personal favorite....

Double ROT13.

Which incidently, is hereby covered under the DMCA, if you manage to decipher it will be fully procecutable under the fullest extent of the law.

You know... (-1, Offtopic)

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

I bet they did this on Gentoo.

I can't help it, I must outburst (-1, Flamebait)

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

NIGGER! NIGGER! nigger nigger nigger NIGGERRRRR!! OOHh YEAH

FUCK

Re:You know... (-1, Offtopic)

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

Nope. emerge is still running.

~~~

Umm..k? (-1, Troll)

i_am_syco (694486) | more than 10 years ago | (#7657011)

Soo......what does this mean? RSA-576 sounds like the name of a fighter plane.

Re:Umm..k? (-1, Offtopic)

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

you must be fat.

Re:Umm..k? (5, Informative)

TedCheshireAcad (311748) | more than 10 years ago | (#7657058)

Not sure if this is a troll, but I may as well offer a simple explanation.

The RSA public-key cryptosystem takes advantage of the theory that factoring composite numbers is a computationally difficult problem. I'm not going to get into specifics, but the depth of the problem is in that the composite number acts more or less as a public key, and encoded within that composite number (as one of the factors) is the private key.

Being able to factor an RSA number is big news because it says that an RSA encoded message with a number of that size (576) can be defeated. Whether or not this is economical to defeat (i.e. time and resources put into the factoring effort) is really the key to this exercise, but one can now assume that a properly funded entity (most likely government) has the ability to defeat RSA-576.

Hope this helps.

Re:Umm..k? (4, Funny)

Snoopy77 (229731) | more than 10 years ago | (#7657081)

Soo......what does this mean? RSA-576 sounds like the name of a fighter plane.

Well i_am_syco, articles are there for reading. They can even increase your knowledge, and one day you may even learn how to spell psycho properly.

Re:Umm..k? (1)

Shadwell (709447) | more than 10 years ago | (#7657201)

one day you may even learn how to spell psycho properly.

Not a big Suicidal Tendencies fan are you? :P

Well, that's just fantastic, isn't it (4, Funny)

mcc (14761) | more than 10 years ago | (#7657014)

I think that composite numbers everywhere will sleep just a little bit less securely tonight, knowing that the Bundesamt fur Sicherheit in der Informationstechnik is out there, somewhere, waiting for them.

Yup.

What's the problem? (-1, Offtopic)

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

dd: reading `/dev/fd0': Input/output error
1268+0 records in
1268+0 records out

Re:What's the problem? (-1, Offtopic)

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

The problem is you have a bad floppy or a bad floppy disk controller. Might I suggest you have both of them checked for alien microbes? They are known to cause problems this time of year when all the outside is cold and frightful.

Is 576bit big? (3, Interesting)

The Real Chrisjc (576622) | more than 10 years ago | (#7657023)

Wow, I havn't really read in to it, but is that very big? I mean, they were talking about not too long ago that 128bit encryption is "almost impossiable" to break. If this is 576bit encryption, and they've broken it, doesn't this mean that 1024bit is looking slightly weak? Whats the 'difficulty' of breaking this key on a relative scale?

Chris

Re:Is 576bit big? (4, Interesting)

cgranade (702534) | more than 10 years ago | (#7657042)

It should go up exponentially, so that 1024 is much more than twice as hard. However, with Beowulf clusters and the new primability test, this is being offset quickly.

Re:Is 576bit big? (5, Funny)

I Be Hatin' (718758) | more than 10 years ago | (#7657179)

However, with Beowulf clusters and the new primability test, this is being offset

Woop! Woop! Woop! Bush-ism alert! Bush-ism alert!

Perhaps you meant primality?

Re:Is 576bit big? (4, Informative)

Sage Gaspar (688563) | more than 10 years ago | (#7657064)

Well, there is no uncrackable code. The idea is to make it as hard as possible. For each message transmitted using one of those keys, a potential codebreaker would have to dedicate however much time this team of professional scientists on powerful computers would take.

As technology gets better, the level of encryption gets better with it. It's a constant battle. Of course, you're not going to want to make RSA your sole method of encryption and post the key all over the web if you're working on ridiculously top-secret government projects, but then again, you wouldn't want to rely solely on any type of encryption and you wouldn't be transmitting it openly over the Internet.

Re:Is 576bit big? (3, Insightful)

mattjb0010 (724744) | more than 10 years ago | (#7657103)

Well, there is no uncrackable code

except for a correctly used one-time pad.

Re:Is 576bit big? (0, Informative)

Chmcginn (201645) | more than 10 years ago | (#7657204)

except for a correctly used one-time pad.

That depends on the message size - with a sufficiently large message, with any portion of it being known by the interceptor, you can eventually reverse engineer the encryption method used.

Regardless, a "correctly used" one time pad is pretty much useless. You'd need to have an entire library of them in order to have any kind of two-way communication. And that's a big hole in and of itself - if your library is a digital object, anyone who can gain access to it has your 'unbreakable' code. More importantly, you still have to get the one-time pad to your compadre in the first place - and who's to stop someone intercepting it there, unless you hand it to them? (In which case, why aren't you just telling them face to face?)

Re:Is 576bit big? (3, Informative)

tang (179356) | more than 10 years ago | (#7657236)

"with a sufficiently large message,.... you can eventually reverse engineer the encryption method used."

Nope! If your one pad key is the same size as the message you are sending, it is unbreakable. Knowing any portion of the message would not help you one bit. Except of course, that you know the part of the message that you know...but you already knew that, so it doesn't help with what you don't know...nevermind:)

Re:Is 576bit big? (1)

mattjb0010 (724744) | more than 10 years ago | (#7657241)

That depends on the message size - with a sufficiently large message, with any portion of it being known by the interceptor, you can eventually reverse engineer the encryption method used.

Well even if they have part of the message, they still won't be able to decipher the rest of it with a one-time pad. You mention the limitations, but there are situations where those aren't problems, eg you give the other party the one-time pad in person, then communicate only a few messages at some distance.

Re:Is 576bit big? (0)

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

The 128-bit encryption refers to secret-key encryption. This is very different from factoring a 576-bit number. Factoring corresponds to public-key encryption. Many more bits are required for a secure public-key than for a secure secret-key.

Re:Is 576bit big? (5, Interesting)

Ageless (10680) | more than 10 years ago | (#7657090)

When people talk about 128 bit encryption being hard to break they are talking about symmetric algorithms such as Blowfish. A 128 bit symmetric algorithm is still very, very tough to crack a key for.

This particular challenge is for the RSA algorithm which is an asymmetric algorithm. They require much longer keys to be secure. Right now most people recommend at least a 2048 bit key for RSA and plenty of people are using 4096 bit keys.

Comparativly, it should be a long, long time before anyone is worried about their current keys. Back in the day when PGP came out, it was fairly common for people to use a 512 bit key with RSA, but most used 1024. Those people could be concerned at this point that their old messages could be cracked.

Re:Is 576bit big? (0)

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

Did people use RSA for PGP encryption in those days? That does sound dodgy.

I knew there had to be a reason ElGamal is currently the default for encryption...

Re:Is 576bit big? (1, Insightful)

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

When you refer to 128 bit, that gerearlly is symmetric key Encryption (as in session key), and yes its still very hard to break via brute force.

When you refer to 1024 bit, this is generally asymmetric (as in public/privite key)

Two very different scales. I assume the 576bit is also refering to the latter which means the key is about half as long as the current standard.

Note that half the key length does NOT mean half as hard - think binary

sorry for any spelling errors;-)

Re:Is 576bit big? (3, Informative)

damiam (409504) | more than 10 years ago | (#7657107)

No. RSA encryption, and public-key encryption in general, uses significantly higher keysizes to attain the same security as private-key cryptosystems at lower keysizes. The difference is that, in a public-key cryptosystem, two parties can talk securely without already both knowing a secret key.

128-bit private-key encryption is virtually impossible to break, because you'd have to test every single 128-bit number. 576-bit public-key encryption is much easier, because you don't have to test every possible key. In this case, RSA uses prime numbers to generate keys. You have to factor the given 576-bit composite into its prime factors, which is much easier than testing every possible 576-bit key (or even every possible 128-bit key).

Re:Is 576bit big? (0)

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

I think you're comparing apples to oranges.

When talking about 40-bit or 128-bit keys, it is usually for symmetric algorithms such as DES, AES... RSA is a public-key system that usually uses larger keys (512, 1024, etc.). The "breakability" of a certain size of keys cannot be compared between such different beasts.

Re:Is 576bit big? (4, Informative)

Stephan Schulz (948) | more than 10 years ago | (#7657117)

Wow, I havn't really read in to it, but is that very big? I mean, they were talking about not too long ago that 128bit encryption is "almost impossiable" to break. If this is 576bit encryption, and they've broken it, doesn't this mean that 1024bit is looking slightly weak? Whats the 'difficulty' of breaking this key on a relative scale?
There is a different between keys for symmetric encryption algorithms like DES, 3DES, Blowfish, and keys for asymmetric (public key) algorithms like RSA and Diffie-Hellman. Symmetric 128 bit keys are still considered safe. 1024 bit asymetric keys are safe for the moment - I belive for long-term security sensitive applications, 2048 bit keys are recommended nowadays. Here [digitalenterprise.org] is a table comparing the cost of breaking (well, brute-forcing) symmetric and asymmetric cyphers for a given key lenght.

My PGP key is still 1024 bits, and I don't break a sweat.

Mine is 1024 too... (1)

Trejkaz (615352) | more than 10 years ago | (#7657230)

My key is 1024 too... but it's ElGamal. Is the ElGamal algorithm inherently more or less secure than RSA?

Re:Is 576bit big? (4, Informative)

Fnkmaster (89084) | more than 10 years ago | (#7657127)

128-bit encryption generally refers to key size in symmetric encryption algorithms, like 3DES, IDEA, etc. These encryption methods generally are broken by brute force searching a 128-bit space of keys - that means you have to check on the order of 2^128 different keys until you know if you've found the right one (obviously, this assumes that there are no fundamental cryptographic weaknesses in the algorithm, known-plaintext attacks or other stuff like that).


Assymmetric encryption algorithms, like RSA, rely on a hard problem with two parts needed to reconstruct the solution. In the case of RSA, those two parts are a large composite number with precisely two prime factors, and one of the prime factors (without one of the prime factors, finding out the other prime factor is deucedly difficult). Basically to "crack" RSA you have to factor the large composite number into its two prime factors. With RSA, the keysize refers to the size, in bits, of the composite and prime numbers you're working with. The thing is that you don't have to search an entire 512-bit keyspace to crack a 512-bit RSA key, you just have to try every reasonably possible _prime_ number that might be a factor of that 512-bit composite. And actually, you don't even really have to do that, since there are substantially better techniques for factoring numbers than brute force, requiring less computational effort.


So that, my friend, is why comparing "128-bit" encryption to "512-bit" or "1024-bit" RSA or other assymmetric encryption techniques (which are similar but rely on numerical problems other than factoring large numbers) isn't terribly meaningful.

Re:Is 576bit big? (1, Interesting)

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

You can't compare the key sizes of symmetric key algorithms (like DES or AES or Blowfish) with the key sizes of public key algorithms (like RSA or ElGamal). 128 bits for symmetric key algorithms is still practically impossible to break but 128 bits for RSA is now pretty easy to break. The difficulty of breaking these algorithms is thought to be exponential so adding an extra bit doubles the amount of time it takes to break the algorithm -- if this is true, then 1024 bits should still be safe (it will take 2^448 times longer than 576 bits assuming the same hardware and software).

Re:Is 576bit big? (2, Interesting)

FU_Fish (140910) | more than 10 years ago | (#7657132)

You may be comparing two different types of encryption. For block algorithms such as DES and AES, 128 bit is still fairly reasonable, however not for RSA (and other public key algorithms). Currently, 1024 bit RSA is considered reasonably secure and 576 is, as we can clearly see, quite insecure. I won't go into the details of why different algorithms need such drastically different key sizes here, but if you'd like to know more, the Crypto-FAQ [rsasecurity.com] is a good place to start.

Why the fuck is this modded troll? (0)

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

If anything, it deserves a few more insightfuls. He has politely asked a number of important questions about RSA encryption. Obviously Chris doesn't understand how this "breakthrough" matters in the big scheme of internet security, and he damn well deserves a polite response or two to help teach him about the impact.

Asshole mod: I hope you're satisfied.

Chris: I hope some of the comments from the other users have been useful to you.

Symmetric vs. public-key cyphers... (5, Informative)

Goonie (8651) | more than 10 years ago | (#7657210)

I'm not an expert, but IIRC you're talking about apples and oranges here.

When 128-bit cyphers are described as "secure", they're almost certainly talking about symmetriccyphers - that is, the key you use to encrypt the message is the same as the key you use to decrypt the message. There are no known ways to break currently acceptable symmetric cyphers (such as 3-DES and AES) faster than brute force - that is, trying each key one at a time. If you have a 128-bit key, this will on average take (2^128 / 2 = 2^127 ~= 10^38) tries before you get the key. This will take billions of years to do, even using a massively parallel computer.

The other sort of encryption, the sort we are talking about here, is public-key encryption, where you use two different keys to scramable and descramble the message. The advantage of this method is you can create a key pair, and give one key to everyone who wants to send you a message (the public key), and while they can send you message securely, it is very difficult for them to figure out your private key (and thhus read messages other people have sent you).

The bad news with public-key encryption is that the algorithms are considerably weaker than with secret-key cyphers. You can mount considerably quicker attacks than just brute-forcing the keyspace. Therefore, you need longer keys for equivalent levels of security. With RSA, the most common method, figuring out your private key from your public key is done by trying to figure out the factor of a very, very large number that is the product of two very large prime numbers. This is still very difficult to do, but it is a simpler problem than brute-forcing an entire keyspace. These Germans have just demonstrated the ability to factor a larger such number than anyone else has done before.

Whilst this is interesting, from what (little) I understand of cryptography it's still a very long way from here to cracking 1024 bit RSA keys. In any case, as the hardware makes it easier for the attackers, it makes it practical to go with longer encryption keys, so faster hardware is neither a help nor hindrance to attackers. The one proviso is, of course, the security of data encrypted by older cyphers.

They'll Get Sued (-1, Offtopic)

Omega1045 (584264) | more than 10 years ago | (#7657033)

I am sure there is some SCO code in the solution. They'll just get sued. Congrats, Defendants!

That's Easy (4, Funny)

paul248 (536459) | more than 10 years ago | (#7657035)

Look! I did it too!

1 2 3 4 6 8 9 12 16 18 24 32 36 48 64 72 96 144 192 288 576

michael (-1, Troll)

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

your such a fucktard

Hmmm. Complexity vs. Cash (4, Interesting)

silentbozo (542534) | more than 10 years ago | (#7657041)

Does anyone know the relative computational difficulty of cracking RC5-72 vs. trying to factor one of the RSA numbers? Given the higher monetary payoff, I'm wondering if I wouldn't be better off implementing and running a prime factor sieve, rather than running the RC5 client (which only runs on my W2k workstation, because the distributed folks never rewrote the older cores that run on my pre-OSX Macs.)

Re:Hmmm. Complexity vs. Cash (4, Insightful)

TedCheshireAcad (311748) | more than 10 years ago | (#7657113)

Well, the computational complexity of the General Number Field Sieve is:

O(exp(c*log(n)^(1/3)*log(log(n))^(2/3)))
where the value of c is reflected by the specific flavor of the NFS you're using, but in each case c>1

I don't know the complexity of RC5, but I can imagine it's not exponential like the NFS.

Re:Hmmm. Complexity vs. Cash (0)

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

I don't know the answer to your question, but I must show off some knowledge, so here's something I do know! But the answer to you question probably has nothing to do with what I just said.

Oh hell, that's very insightful! There's numbers after all!

Re:Hmmm. Complexity vs. Cash (2, Interesting)

Ninja Programmer (145252) | more than 10 years ago | (#7657128)

Factoring composite is probably somewhat easier in the sense that it doesn't require more hardware/brute force computational power, however, its probably harder in the sense that you need to be very famillar with the very latest in factoring algorithms and essentially be skilled and willing enough to implement the very leading edge known algorithms.

In other words, factoring RC5-72 requires Moore's law, plus a massively growing audience of people willing to participate. But even with the most optimistic projections, RC5-72 will not fall for decades. Factoring something like RSA-574 requires that you be up on the latest in computational mathematics as it relates to number theory. If you think you can bone up on the latest in factoring techniques in less than 10 years, then you probably have a better shot at the RSA prizes.

Or RC5-72 could fall tomorow (1)

Veramocor (262800) | more than 10 years ago | (#7657193)

......if you get lucky!

There is nothing that says you won't find the correct key in the 1st .1% of keyspace you search.

Mersenne Primes (2, Informative)

penguinoid (724646) | more than 10 years ago | (#7657050)

Mersenne primes [wikipedia.org] are a number of the form 2^n - 1, where n is some prime number. Mersenne primes are one of the easiest to find, and there is a quick (relatively) algorithm for checking whether it is prime. Not all Mersenne numbers are prime.

Re:Mersenne Primes (4, Interesting)

millette (56354) | more than 10 years ago | (#7657077)

the 40th Mersenne prime has been discovered 2-3 weeks ago and just proven to be correct. See http://www.mersenne.org/history.htm [mersenne.org] for more info.

Re:Mersenne Primes (0)

jrockway (229604) | more than 10 years ago | (#7657083)

2^4-1 = 15, for instance

Re:Mersenne Primes (0)

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

15 is not a prime

Re:Mersenne Primes (4, Informative)

millette (56354) | more than 10 years ago | (#7657146)

and 4 isn't either... so really 2^4-1 is a terrible example.
  • 2^5-1 = 31 is prime
  • 2^9-1 = 511 isn't prime since 9 isn't
  • 2^11-1 = 2047 isn't prime: 23 x 89

Re:Mersenne Primes (1)

penguinoid (724646) | more than 10 years ago | (#7657121)

The exponent must be a prime as well, but it still won't guarantee you get another prime.

Well Mr Smartypants poster... (-1, Flamebait)

narftrek (549077) | more than 10 years ago | (#7657051)

/. probably didn't notice because we don't care.

I'm sorry the rest of the geek world can't keep up with your mad geek-story-finding skillz.

</sarcasm>

Re:Well Mr Smartypants poster... (0)

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

It wasn't a) anti-Microsoft or b) anti-SCO, so no one on /. cares.

Reaction (5, Funny)

Angram (517383) | more than 10 years ago | (#7657066)

I think I speak for 99% of the population when I say...

"Oh."

The Other One Percent (4, Funny)

handy_vandal (606174) | more than 10 years ago | (#7657084)

I think I speak for 99% of the population when I say... "Oh."

I think I speak for the other 1% when I say ...

"Um."

-kgj

Cheaters! (3, Funny)

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

They probably just looked in the back of the book.

Re:Cheaters! (0)

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

Maybe in the back of The Book

Re:Cheaters! (0)

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

Acually they couldn't. RSA-576 is an even numbered question, and there are only answers to odd numbered questions.

Re:Cheaters! (5, Funny)

endx7 (706884) | more than 10 years ago | (#7657251)

They probably just looked in the back of the book.

No, that was an even problem. Only odd problems are in the back of the book.

Security by obscurity (-1, Troll)

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

Nobody should rely on security by obscurity to keep their data secure. The only difference between ROT-13 and RSA is a few prime numbers.

A HIT OF HELIUM (-1, Offtopic)

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

...psssssshhhhh

whoo! I feel light-headed

come on, +5 funny...

Re:A HIT OF HELIUM (0)

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

*POP*

...sorry...

RSA Challenge Challenge (1)

Caractacus Potts (74726) | more than 10 years ago | (#7657079)

Now there needs to be cash prize for discovering the discoverer when the challenge has been met. I just checked that site today.

Prime numbers (-1, Troll)

penguinoid (724646) | more than 10 years ago | (#7657086)

You can find more info about prime numbers at goatse.cx

Is this what you're talking about? (-1, Offtopic)

Wigfield (730339) | more than 10 years ago | (#7657145)

http://www.penguinhosting.net/~jpeck/prime/

Please be kind to my karma...

Re:Is this what you're talking about? (0)

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

Oh my lord. Get up, walk away from your computer, go into the bathroom, and drown yourself in the toilet. Seriously, you'd be doing humanity a favor.

Mod parent down! (0)

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

- Nasty
- Offtopic

Mod parent up! (0, Funny)

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

-- Funny
-- On topic

ROFL! (-1, Troll)

Steve 'Rim' Jobs (728708) | more than 10 years ago | (#7657258)

That's the funnniest thing I've seen all day!

Who modded this down offtopic?

The factors were (-1, Flamebait)

paul248 (536459) | more than 10 years ago | (#7657114)

49561029139355845747971386346688559685802770654976 22183978317743925946576415078139905781369527613655 89856824677545079939976358482997663812205232927942 98468955841793432926128

and 2.

Re:The factors were (3, Funny)

TedCheshireAcad (311748) | more than 10 years ago | (#7657157)

Your first factor is composite, slick.

This is a /. revolution, instead of spelling nazis, we now have composite number nazis.

Actually (0)

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

They're all composites, einstein. The first, third and fourth are even numbers. The second is a multiple of 5. Joke is on you.

Encryption is only needed (-1, Troll)

Sarojin (446404) | more than 10 years ago | (#7657122)

by those with something to hide (criminals/GPL users)

dammit! (-1, Offtopic)

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

well that just makes my luggage worthless!

Re:dammit! (0)

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

what the hell is that supposed to mean ? your carrying encrypted data in your suitcase which happened to use that same prime number ?

Oh no... (5, Funny)

RSA-576 (730686) | more than 10 years ago | (#7657141)

How could they *factor* ME without *my* own knowledge?! Somebody call the doctor... -RSA-576

Re:Oh no... (0)

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

with that uid you probably made the account after the story was posted. how lame.

Re:Oh no... (0)

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

you probably made the account after the story was posted.

Yep, he did [slashdot.org] .

ut_radio 9 8 (-1, Troll)

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

you made this name just to grab karma, didn't you? what a fucktard.

Notify RSA (4, Informative)

TheRedHorse (559375) | more than 10 years ago | (#7657142)

In order to win the prize, you must submit your result to RSA, they don't actively seek out winners. That's why RSA's page hasn't been updated.

They can submit their answer here [rsasecurity.com] .

Germany? (4, Interesting)

gr8_phk (621180) | more than 10 years ago | (#7657169)

I'm not suprised that someone has done it. Even the RSA site suggested 576 would fall soon. What I do find interesting is that it took 4 days for word to get out, and that the factorization was done in Germany. More interesting would be knowing what algorithm was used - is it new, or just further refinement of GNFS or MPQS with faster hardware?

4 days and no mention on RSA's website? (4, Funny)

product byproduct (628318) | more than 10 years ago | (#7657187)

They're busy multiplying the two 87-digit factors by hand, just to be sure.

Awww (4, Funny)

JDWTopGuy (209256) | more than 10 years ago | (#7657189)

Crap, there go my plans to factor it myself.

RSA-576? (0, Offtopic)

sharkey (16670) | more than 10 years ago | (#7657233)

RU-486 the Next Generation?
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?