Jump to content

Hak5 RSA Securty Compitition


Recommended Posts

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

Link to post
Share on other sites

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>

Link to post
Share on other sites

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

Link to post
Share on other sites

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.

Link to post
Share on other sites

What he's saying is that he wants help factoring a very large, semiprime number using the GNFS algorithm: c09a5f0e7b5a01c84b3410bafd08316f.png 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.

Link to post
Share on other sites

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

Link to post
Share on other sites

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.

Link to post
Share on other sites

/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

Link to post
Share on other sites
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.

Link to post
Share on other sites

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.

Link to post
Share on other sites

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

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...