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...
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.