spektormax Posted October 4, 2006 Share Posted October 4, 2006 Ok so many of you have heard of the famous private/public key cryptological algarithum RSA which things such as GPG/PGP are based on. SOme of you know that the algrithum is based on using 2 large prime numbers (up to 4096 bit) and mulitiply them together to form a semi-prime. The inhernet strength of the algarithum is based on the fact that you can not factor a semi-prime number in polinomial time. That means there is no widely known algorithm that can factor it in time O(b^k) for any constant k. There are published algorithms, however, that are faster than o(ab) for any number a greater than 1. In other words, there are verifiably algorithms which are super-polynomial but sub-exponential. In particular, the best published asymptotic running time is for the general number field sieve (GNFS) algorithm, which, for a b-bit number n, is: O(exp(((64/9)b^(1/3))(log(b))^(2/3))) So esencialy what that little exserp from wikipedia means is that its hard to factor the number. The fastest known way to do this on a normal (no wuantum computer) is the general number field sieve (GNFS) algorithm. The easyest way is the direct search or basicly deviding by 1,2,3 and so forth up to the number. While direct search is easy, when dealing with large numebs up in the 200 digits, its way way too slow. Now RSA curently offers a compitiotion http://www.rsasecurity.com/rsalabs/node.asp?id=2093 for basicly taking a large semi-prime number and breaking it down into it's 2 prime factors. A team at the German Federal Agency for Information Technology Security (BSI) holds the record for factorization of semiprimes which is the RSA-640, a number containing 193 decimal digits (640 bits), on November 4, 2005. The factorization required several months of computer time using the combined power of 80 AMD Opteron CPUs. Now the next one in the list is RSA-704 which is a 212 digit number. Here's the fun part, RSA Security is offering a $30,000 to anyone who can factor it. Heres where Hak5 coomes in, I'm thinking of using the GNFS algarithum inorder to factor the RSA-704. I am mostly doign this sorta just becaue I think its cool. I have set up #RSA in the irc (irc.hak5.org) and I desperatly need some math experts and coders. All contributers will recive a share of the prize porportinal to the amout of work they do. And of course, the Hak5 "Higher UPs" will recive a cut as well. Well ok thats about it, hopefully we can all put our heads together and win $30,000 Quote Link to comment Share on other sites More sharing options...
Sparda Posted October 4, 2006 Share Posted October 4, 2006 Any chance of spltiting that in to a paragraph or two? :roll: Quote Link to comment Share on other sites More sharing options...
PoyBoy Posted October 4, 2006 Share Posted October 4, 2006 sweet. IM pretty good at math. Maybe I can help a little bit. (maybe) Quote Link to comment Share on other sites More sharing options...
omega_ion Posted October 4, 2006 Share Posted October 4, 2006 I'm in AP Calc, idk if that counts as a math expert or not.. Quote Link to comment Share on other sites More sharing options...
PoyBoy Posted October 4, 2006 Share Posted October 4, 2006 I will be next year, so thats why i put (maybe) cause i dont really know too much Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 yeh yeh and NO i WILLNOT FIX MY GRAMMER Im math not engligsh lol Quote Link to comment Share on other sites More sharing options...
moonlit Posted October 4, 2006 Share Posted October 4, 2006 Raise your hand if you a) tried to read that and b) managed to read and fully understand it... Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 (a+b)^2= a^2+2ab+b^2 Quote Link to comment Share on other sites More sharing options...
comcipher Posted October 4, 2006 Share Posted October 4, 2006 Good luck with that one, I think i'll stick to achievable goals ;) Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 If you're thinking of factoring a 212+ digit number with the machines we have available to us, there's no way in hell we could beat MIT, Stanford, U of M and every other top college who's certainly pitting their best against the numbers. It would take machinery that surpasses even that of metatron's to efficiently factor the number and whos to say it would be done before someone else. If we were to somehow find a way to distribute the cpu load (much like folding@home), then we could stand a chance but we might as well aim for a higher number because the majority of people will be working on the next to be factored. I like the idea and more than willing to donate time into this but I'm no coder but I am rather good at math so that's where I could help. PS, someone get metatron on this, he's got the serious hardware and a fricken phd in advanced mathmatics. Raise your hand if you a) tried to read that and b) managed to read and fully understand it... <Raises Hand> Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 esecinaly I could code it if I coudl get the general number field seive algarithum no good explinations online (ill keep looking) but yeh I mena we coudl go for the $50,000 I guess. Just thought that rainbow tables were good but they made no $$, this will and it will be cool as well Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 Please, type your posts in word, open office, whatever and spell check them. I want to help but your posts set off migrains in the back of my head. Quote Link to comment Share on other sites More sharing options...
moonlit Posted October 4, 2006 Share Posted October 4, 2006 Raise your hand if you a) tried to read that and b) managed to read and fully understand it... Quote Link to comment Share on other sites More sharing options...
VaKo Posted October 4, 2006 Share Posted October 4, 2006 I got half way threw that and had a seizure... Money was mentioned though. Quote Link to comment Share on other sites More sharing options...
Garda Posted October 4, 2006 Share Posted October 4, 2006 I read an mostly understood it. problem is, like was mentioned before, people much smarter, better educated and with better equipment than us are probably already working on the problem. Now i'm not one to just quit and be a loser about things, but it makes no sense to fight battles you couldn't win. if however, you still wanna try, for whatever dumb reason, i'll be willing to join you in your pointless endeavor. oh, and get firefox 2, it has built in spell check. Trust me, you'll certainly make good use of it; and think about using paragraphs. Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 What he's saying is that he wants help factoring a very large, semiprime number using the GNFS algorithm: into the two prime numbers that when multiplied, equal the origional. And by doing so, make lots of money. The problem with this however, is that it takes a HUGE amount of processoring power to factor the number (200+ digits) and therefore he's looking for help from coders to possible create a program that would be run by us to help factor the number. I don't see how we could, as a group, help factor the number as it would have to be some sort of international cluster but hey, if someone's got an idea, let's hear it. Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 I;m just saying with the rainbow tables almost out of the wya, we might as well do something cool, its this or a full char NT rainbow table, and while fesible, and useful, NT!=$$ Quote Link to comment Share on other sites More sharing options...
VaKo Posted October 4, 2006 Share Posted October 4, 2006 See if metatron can spare his toaster or something. Bound to be more powerful then the rest of our shit put together. Quote Link to comment Share on other sites More sharing options...
Garda Posted October 4, 2006 Share Posted October 4, 2006 I don't think that even writing it in assembly would make that much of a difference. Anyone got a supercomputer lying around. Actually, the NSA is probably reading this, i'll just ask them. Hey, NSA, can we borrow one of your supercomputers just for a little, like, just to crack this little number? /me sits and waits Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 Haha, easy guys. I kinda like this idea. It's rather rediculous for the vast majority of us (no wait, all of us) as we've got no where near the necessary equipment to factor the number but it's still interesting to read about something like this and learn more about it. Just too I just can't just enter it into my ti-84 plus and have it spit out the answer. Quote Link to comment Share on other sites More sharing options...
VaKo Posted October 4, 2006 Share Posted October 4, 2006 Could someone not make a folding@home style client for it? Or is the math all wrong for that to work? Quote Link to comment Share on other sites More sharing options...
manuel Posted October 4, 2006 Share Posted October 4, 2006 /me refuses read that simply because it has not natural breaks. Dude, Spek, I sincerely hope that you do not turn in your school work like that. At least take pride in your writing, and in yourself byu showing others that you can write properly. That is all I have to say. -Manuel Quote Link to comment Share on other sites More sharing options...
armadaender Posted October 4, 2006 Share Posted October 4, 2006 Could someone not make a folding@home style client for it? Or is the math all wrong for that to work? That's what I was thinking but the logic behind it wouldn't work. Say you wanted to factor a basic function say, f(x)=x^3 - 3x^2 + 2x. This is obviously x = 0,2, and 1. But let's say you wanted to distribute the load between two computers. You would split the problem in two: 'x^3 - 3x^2' and '2x'. * The same way folding@home works, splitting up the work * Then the first computer would factor x^3 - 3x^2 = 0, which would then be x = 0, 3. And the other computer would have '2x = 0' which is zero. The point of this rambling being, I don't see how it would be possible to 'cut-up' the work of one particular problem because the anwsers in the end would not be correct. But I could be wrong, there may be some formula out there that would make it possible, especially for semiprime numbers. Quote Link to comment Share on other sites More sharing options...
cooper Posted October 4, 2006 Share Posted October 4, 2006 I've actually worked on this type of thing before (don't ask. It's on the forum somewhere). The big thing I think is to reduce the amount of numbers to actually test. About 80% of the keyspace can be thrown away for being obviously not prime. The other 20% can mostly be thrown away aswell, but it's a little more tricky to discover this. Would it be an idea to create a rainbow table that basically holds true primes for a given keyspace? Should make the brute-forcing approach more efficient. Note that with GNFS you can distribute the load of assembling the numbers, but the sieving stage of the algorithm has to be done on a single box and can take quite a while to complete aswell. Quote Link to comment Share on other sites More sharing options...
spektormax Posted October 4, 2006 Author Share Posted October 4, 2006 eh the thing about rainbow tables is that it takes about 15x the times more time to generate them than it does to just go thru a normal brute force. (it gets even worse the more keysapce you have) SO I donno how high you have to get before the primes help you Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.