Slashdot Mirror
Win $200,000 In RSA's Factoring Challenge
BetaRelease writes: "All ye with excess CPU cycles to spare. Here's a chance to win as much as $200,000. Join RSA's Factoring Challenge." That means you can get $10,000 for figuring out the factors for this laughably easy, completely trivial number, or twenty times that if you can figure out a slightly nastier one. While it would probably take more horsepower to win any of the prizes than the prize money could pay for, admit it would be cool to trade a 98-digit number for a few years' salary.
Fucking hell, that was almost relevant. Unlike this.
If you *do* crack it, you will be sued and go to jail under the DMCA
home page for Linux
Please mod me up too, I posted a link !!!!
More or less yes. But (if I understood the way america count):
Thousand = 10^3
Million = 10^6
Billion = 10^9
Trillion = 10^12
The first (the 'easy') number is approximately 10^174. Its factors are in the order of 10^87. In that range, there is a prime number every few hundred of numbers, so your chances are in the 10^84
You have one chance in a trillion of trillion of trillion of trillion of trillion of trillion to find the good number.
So, basically, the contest is more about finding new ways to factorize big numbers. Not easy ways, but slighly more practical ones.
Cheers,
--fred
ok. hold on, just let me click ok..... DAMN IT!! windows crashed... i guess i have to start over.
I just showed the RSA numbers to my dolphin and he just laughed.... eeeeee eee eee
They want to see if it can be done efficiently, because they made the bet that it can't. One 617-digit number is only 10^-617 of the whole range of 617-digit numbers, it's almost nothing.
I have a nice factorisation of the 617
digits one, but it is too big to fit in this post...
Cut and paste the big number into windows calculator and watch the number pad go nuts.
i've decided i'm going to spend any free time i have at work on this project.
i've just requisitioned 8,000 reams of paper and 5000 number 2 pencils. wish me luck.
All the numbers are divisible by 1!!! Gimme the cash!
From the FAQ:
I don't think distributed.net will make much progress based on current algorythms. Most people just do'nt have that much memory to donate to the cause. Might be time to invest in memory makers if you think they will buy it.
Accually for 5 you only need to check for a last didget of 5. If the last didget was 0 it would be even, and we already have determined that it isn't even. Further we know that there are exactly TWO primes involved, so if it ended in 0 the only possibility is 2 and 5, which means the number is 10.
I don't know how to help you with 7, but I did just save you a millisecond with 5.
Right. Pick two (presumably large, though there is no reason it has it couldn't be 1 very large and one laughably small prime number) prime numbers. Multiplu them togather. If the answer is that number, you have the solution.
The only problem is it is easy (as in I once did this when I was taking a class, but since have forgotten how) to prove that there are a lot of prime numbers to chose from. We also know of good ways to find out if a number is prime, but no good way to find the factors if it isn't.
Still, have fun. It isn't that hard to find two prime numbers with a paper an pencil. Of course arthmitic mistakes are likely, and it takes a lot of time)
Just doodling on the back of a napkin, trying to figure out the best way to tackle this one.
The obvious way is pure Brute Force: Iterate between 2 and n, where n is the number. If the current iteration i divides into n, j times (with no remainder), remember the factors i and j, and then recursively repeat with i and j as values for n.
Continue until all values of n are non-divisible (prime)
Anybody have a better algorithm?
Want to learn about race cars? Read my Book
http://www.rsasecurity.com/rsalabs/faq/2-3-4.html
:)
Hmm...
All the Challenge numbers are the product of two primes, so there's only 2 factors. If we had a list of al the primes of length n, where n is the length of the longest Challenge number, this would be trivial. But since we don't...
Well, read the FAQ for yourseves.
Want to learn about race cars? Read my Book
You need only search the space up to the square root of the first number, a moments thought will let you see why.
I wasn't implying that it was easy.. if it was, they wouldn't give you $10,000 for doing it. I am merely pointing out that the original poster's comments had a fatal flaw.
GNU bc 1.05 can't even multiply 10(bignum 1)7779
*
106603(bignum2)62808643 w/o segfault & core dump. Bah.
[lameness filter - those are #'s, not CAPS!)
try { do() || do_not(); } catch (JediException err) { yoda(err); }
the 'arbitrary precision calculator' that *nix people (usually) have it right at their fingertips. Don't know what Windows users have to accomplish the task.
try { do() || do_not(); } catch (JediException err) { yoda(err); }
All those numbers are odd. I had an idea about dividing by 2 :)
Nyah nyah!
What "the government"?
Oh yes, you must be one of those Americans, the great nation that inhabits planet Unkasam all alone. And that planet is ruled by a government, better known as The Government.
Seriously, what's your puny government going to do if, say, Chinese, "came out tommorow with the solution for *all* of these"?
Yet again someone has to say this, but you never can't emphasize this message enough: Your're not alone, Yanks.
Prior art -- think distributed.net
Now go home and wait for a visit from the patent lawyers like a good little heathen.
Yes, someone could luck out. But do you realize what you are saying?
As an example, radioactive decay is, at the atomic level, a fairly random process, and the atoms are basically isolated. Any given atom could just pop at any moment, and at any given moment some of them are.
Realize now that, with some "luck", it would be very possible for a whole bunch of atoms to decay at once. There's nothing keeping them going at any certain rate other than probability; it's incredibly unlikely that any large number of atoms will do the same relatively unlikely thing at around the same time.
In this case, I would say that if you use your computer to try some random prime numbers, it's far more likely that you'll explode than find the correct numbers "on accident". Not a good risk, I say.
I have seen the future, and it is inconvenient.
Hah, amen. I used to know a guy who would always tell people that various government agencies were after him for his uber-hacking. He'd even pretend, like if he was driving his car there was a good chance he'd start skidding down side streets because someone was "tailing him".
Then again, he wasn't anything I'd call a "hacker", in any sense of the word. The best one-word description of him would be "wannabe".
I have seen the future, and it is inconvenient.
Of course, I'm sure that that is not what RSA Labs is hoping for. What would be much more interesting is if someone can come up with a method that doesn't take a massive number of cycles and could be quickly used on any such number.
Or more interesting yet, prove that one needs to work their butt off to factor it.
If one could either one, the prize would be much more than 200 grand.
That we know of. Prove it.
(And then we can all rest a bit easier when we use RSA, for example.)
There's actually a million dollar prize for solving that one. I guess if you solve it the right way you should be able to quickly claim your 1.6 mil.
RSA is offering this money to show that the RSA public key method IS secure, because we can't factor these numbers.
Someone coming out tommorow with the solution for *all* of these. For everyone. And having it verified.
I've thought about this before, but more from the perspective of "what if by some freak accident I was to stumble on the algorithm that makes factoring trivial? what would I do?"
Now, I don't believe everything I see in movies, but I also don't feel like putting my welfare or my sanity on the line by exposing something so momentous and dangerous. A lot of powerful people depend on the difficulty of factoring to keep their stuff secret.
Here's what I think I would do: Send an encrypted e-mail to Bruce Schneier describing the algorithm (he must have a public key posted somewhere), and forward it through a dozen anonymous remailers. Preface the explanation with this: The existence of the algorithm I am about to describe is terrifying to me, and I am not fit nor willing to take responsibility for it. I trust your judgement in how you feel is the best way to proceed.
--
Female Prison Rape in NY
Bruce Schneier wrote in Applied Cryptography (p. 258): "If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weigh so much that it would exceed the Chandrasekhar limit and collapse into a black hole..."
(Reality reasserts itself sooner or later.)
The first gradstudent to develop a serious quantum computer is gonna pick up a lot of cash.
Given one hour to live, the student replied: "I'd spend it with professor FP who can make an hour seem like a lifetime."
From earlier on in the FAQ:
Each number is the product of two large primes, similar to the modulus of an RSA key pair.
So, 4 factors,
1, unknown1, unkown2, and the test number itself.
Only need to submit the 2 primes from the middle pair.
----- LoboSoft specializes in Digital Language Lab
If you have enought cycles to factor the 2048 bit challenge any time in the near future one would assume that you could easily factor the lesser numbers as well.
An interview on CNet radio yesterday with the chief research guy @ RSA said that RSA expects to pay the first sum ($10,000) within a year.
RSA is in the encryption biz. They're funding (on the cheap, might I add) research into cryptography. This is like saying that Publishers Clearing House should be funding medical research instead of giving away money (and furthering their business).
Let's say, for sake of argument, that someone comes up with a new algorithm for finding the primes that generate a key, and six weeks from now, they manage to clean up and take every prize offered. For a total outlay of $635,000, we find out that encryption based on primes is vulnerable to cracking. I think anyone would be hard-pressed to find medical research that benefits from that same amount of money to the same degree that cryptography would from the revelation that the factors from a large key can be easily obtained.
The truth about Scientology, Xenu, and you: Operation Clambake
Someone coming out tommorow with the solution for *all* of these. For everyone. And having it verified.
While cool, and prestigious, and definitely worth money, the government would SURELY seek to either supress his findings, or acquire them.
If someone came up with an entirely new number theory solution that allowed easy factoring of huge numbers (ala Sneakers), the government would indeed be something to fear.
Not to mention, very few secrets would be safe.
Just an interesting thought for a boring day..
GPL'd web-based tradewars themed space game
sure, see http://www.cafepress.com/nsa1984.
Hope it helps.
Well let's see ...
... None are even ... nope.
... None of the digit sums is divisible by 3 ... nope.
... None end in 5 or 0 ... nope.
... Well, I'm out of ideas.
2
3
5
7
I'm giving up. Maybe I should have stayed in grad school.
Distributed computing power has become so abundant and easily reachable (seti, dist.net, etc), that the entities with interests in preserving and justifying there existance (seti folk, protein structure folk, encryption folk)have to survive by distracting us with a limitless abundance of distributable contests.
If you really want to volunteer your cpu cycles, you can look for the cure for cancer by using this client:
http://www.ud.com/home.htm
Or, you could keep file sharing freedom alive by running a Gnutella client!!!
http://www.bearshare.com
If you really want to volunteer your hardware, do it for something that will help people, please.
http://www.redpolygon.com
http://www.hyperpoem.net
hyperpoem.net
Similar things have been done. I've seen trojans that install the distributed net client under someone else's e-mail address. Mostly on lab type machines. Zip up your client with some program, put it on gnutella, and watch your stats go up.
Try google:
http://www.eff.org/Misc/Graphics/nsa_1984.gif
Now go to cafepress, and have one printed.
But there is no way for you to factor any of these numbers while you're still alive. Last year the RSA 512 bit number was factored. It required about 9 months on ~400 Alphas and Pentium IIs, plus (and this is the kicker), about 4 weeks on a really huge supercomputer (I think about 2 weeks at the start, and 2 and at the end). You need like 4 gigs of RAM (at least, more as the numbers get longer) to do this.
The supercomputer steps cannot be done in parrallel - it's a huge linear algebra problem. You would have to find a new factoring algorithm if you wanted to make it a distributed.net-style problem.
Here is the list:
* 576 bits - $10,000
* 640 bits - $20,000
* 704 bits - $30,000
* 768 bits - $50,000
* 896 bits - $75,000
* 1024 bits - $100,000
* 1536 bits - $150,000
* 2048 bits - $200,000
Yeah, I got up to 1024 bits but then I ran out of lifelines and regis goaded me into picking the wrong factor.
---
/bin/fortune | slashdotsig.sh
It'd be great to find some software that's able to work on these problems during my spare CPU cycles. Who knows the scoop on this? It's worth a shot, I'm sure the odds are at least slightly better than winning the lottery!
---
Josh Woodward
Josh Woodward
Create a internet worm that uses your idle clock cycles to find the number, and sends it back to me once it's found it. I would use anonymous Usenet for communication: requesting jobs, posting jobs and (hopefully) posting the current solution.
The reason for not making a large (voluntary) distributed project is because you'll probably have to split the money with the lucky dope that found the number, this way you get to keep the money.
-Jon
this is my sig.
While I am without the ability to actually check the number you've just provided, I know it should at least be odd, which your number isn't. The max # generated by 576 bits would be 2^576 -1.
2 times itself 576 times would be even. Subtracting 1 would then make it odd.
You are the weakest link, goodbye!
24733040147310453406050252101964719003513134910
so, say you wanted to solve it in a lunar month.You would need to try something on the order of
88332286240394476450179471792731139298261196107
factors per day or
36805159266831031854241446580304641374275498378
per hour or
61341865444718386423735744300507735623792497296
per minute or
10223644240786397737289290716751289270632082882
per second....
now distributed.net is getting 127Gkeys per second... or about 127000000000 keys per second... look at the difference in the number of digits... RSA won't have to pay on that for a LONG time about8 41 91243355002259457438595524172029124979552458558672 34341034133758742263188689327699355242471411637798 00504
61754295921048244341300860763463725504842696735
years at that rate if my calculations are right....
---
After all, ICFP is tommorow, and I can't work on both at the same time. Oh well, I guess I'll have to wait until sunday afternoon to start cranking on this one. Or I could just say screw ICFP since this one has potentially higher rewards :).
Things you think are in the Constitution, but are not.
Error: 'long long long' is too long for GCC
Is there any nice, easy way around this that will let me not rewrite division?
"Evil company X is threatening to restrict our rights! Let's all get together to stop--OOOH! SHINEY!!!" -- AC
Not only that, but I'm willing to bet if we could start effectively factoring such large numbers, somewhere -- somehow, a medical breakthrough would come from it!
42 of course. :)
The Economics of Website Security
lets not forget that computers do this many times a second
We've only just put their cancer cure on hold to help SETI look for lights in the sky. And now this??
Maybe they should have based the prize ammount on one of the factors, moving the decimal to a reasonable position of course.
So, if you just randomly pick factors what are your odds, and how does it compare to the lottery when computed on an average PC? Of course unlike lotto, you don't have to pay to play unless you really decide to go all out and purchase additional hardware, which would probably not be justified.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Makes me wish I had known about the NSA's recruitment programs in high school....
You can never go home again... but I guess you can shop there.
I really should read my posts for clarity before clicking Submit.
:: I need some Jolt.
I meant that the 2048-bit wouldn't be solved anytime soon.
::sigh
You can never go home again... but I guess you can shop there.
617 digits, and with the assumption that the factors are comparable length means they are in the 300 digit area. Which means that you could guess one with about a 1 in 10^300 chance.
In lotto terms, you are about 10^294 times more likely to win guessing lottery numbers than trying to guess here. However, the guesses here are free, so you're price/probability of winning ratio is infinite.
I demand a million helicopters and a DOLLAR!
Er... yeah. Zero. Sorry, the Probability/Price ratio is infinite. (My math track record on /. sucks.)
I demand a million helicopters and a DOLLAR!
What software should i use for this? They don't offer anywhere to download any, can i use the distributed.net client?
Didn't the mathematician guy (who got killed) use his solution of "factoring large primes" to break encryption?
Please explain how that is possible.
Just for the hell of it, I tried hitting "Submit" with a blank submission of factors. Mostly, I was curious to see if they were using SSL for submissions because what if someone was snooping and intercepted my submission and then submitted it themself. Hey, it could happen!
Anyways, no they don't use SSL, but more surprisingly, they care who your referrer was. And they say "slashdot not found in list of allowed referrers". Not sure if this would actually prevent a legitimate submission, but maybe you don't want to risk clicking thru Slashdot to RSA when you find the real factors. (Especially considering the lack of SSL.)
Error Message:
slashdot not found in list of allowed referrers.
Required Field: email has not been completed.
Required Field: Submitters has not been completed.
Required Field: challnum has not been completed.
Required Field: p has not been completed.
Required Field: q has not been completed.
Required Field: description has not been completed.
Please use your 'back' button to return to the Web form.
RSA have several different levels of prizes.
Here is the list:
Good luck on getting those anytime soon.
Actually, having only 2 factors is (part of) what makes it so difficult. The more factors there are, the smaller each individual factor will be (on average), and hence the smaller the amount of time needed to find them.
Just make sure you don't rig up all the computers at your workplace to win the prize.
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
Are you also tired of doing the same old job time and time again. HERE is your possibility for getting rich without leaving the comfort of your own home... etc.
/. doesn't allow me to fully mimick the capitalization, but you get the picture.
Too bad
Can't anybody do this in their head?
(Kidding)8 738750187350... 7 2306987308763087039476092834760298374609827346908. ..
Factor Submission Form
Submitter Nam(s): Joe Bob
Contact Email Address: joebob@fake.com
RSA Challenge Number:RSA-2048
First Factor: 3892759824679128370982357209837598327598735892759
Second Factor: 3749827873689724509760437602984760283476098273460
Description of Effort: Looked at the yellow post-its stuck to the competition organizer's monitor.
Is there anyone out there that's against cracking a 64bit encryption key?
I love the smell of Karma in the morning
Read the site! "A set of eight challenge numbers, ranging in size from 576 bits to 2048 bits is posted here. Each number is the product of two large primes, similar to the modulus of an RSA key pair."
Do you live in an enormous ant colony or something?!?
See the RSA Security FAQ, How Much Does It Cost?
That is incorrect.
There are numerous algorithms that are more efficient that dumb brute force. That doesn't mean that will find the answer quickly, but vastly quicker than naive brute force attempts.
See the RSA FAQ, What are the best factoring methods in use today?
For trying to use GNFS General Number Field Seive or NFS (Number Field Seive), you need more RAM per CPU (e.g. 4GB per CPU) if you want to factor numbers in the RSA-155+ range.
Since I've not used NFS, GNFS for any projects, I think the network bandwidth limitations are okay, except in the last stage which I think it a linear matrix reduction.
It is expected that the smallest challenge will be solved within 1 year or so. To break the high-end of the range in the next 2-3 years would require an advance in the state-of-the-art in knowledge about factoring.
I wouldn't expect a breakthrough because the problem is fairly old, and well understood, but a definate improvement is possible.
CWI has several source code license agreements with companies in The Netherlands, USA, Germany and France which allow them to use the Number Field Sieve factorization code as this was and is being developed by P.L. Montgomery, A.K. Lenstra, M. Elkenbracht-Huizing, S. Cavallar and B. Dodson. On a non-commercial basis, the NFS source code has also been made available for research purposes to other cooperating groups. A group of the Royal Institute of Technology in Stockholm (Hastad) has used this code as a basis for factoring a hard 512-bit challenge number in October 2000.
See the RSA Crypto FAQ.
The current record factorings were done with the GNFS (General Number Field Sieve).
GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.
The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.
Some pointers:
In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.
to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.
to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.
Good luck.
I'd rather trade $2048 for a 98-digit salary any day of the week...
No, none of those numbers are divisible by 42, because if they were, they would also be divisible by 2 and 21, and none of the numbers are divisible by 2.
I'm a loser baby, so why don't you kill me.
laughably easy?
For those who want some money but don't know how can start here.
Yes I am planning on using all my school labs computers to win this one. But I only ask one favor.
Can you raise the prized to $415,000 instead. I might need it.
Two Towers-Two Worlds.One seeks triumphs and freedom for man.The other deems man unworthy and wrecks them.
...someone (think rich, dumb and unethical) used (or even intended to use) those factorable numbers to encrypt some original content, then called the DOJ and screamed "DMCA" and that evil software pirates were trying to crack their encryption?
Stupid scenario? Really? In the context of the DMCA, nothing's beyond the pale. Remember the SDMI cracking challenge?
If you were blocking sigs, you wouldn't have to read this.
Yes, givin the climaye for system engineers these days $10,000 BUX might be a few years salary
* Carthago Delenda Est *
Actually, everyone is going about this wrong. The real problem is finding the multplicative inverse of an exponent modulus N where N is the product of 2 large primes. Currently, we have a simple way of calculating this inverse *if* we have the factors of N. But, we don't know if that is the only easy method of calculating this inverse. The chain of logic I'm seeing is like this.
1. We need to calculate d using e and N.
2. d is easy to calculate if we have the factors to N.
3. We need to calculate the factors of N
To my way of thinking, this reminds me of a similar logic chain that I saw someone do in the past.
1. I need to find the smallest number in this array.
2. If I sort the array, all I need to do is pick the 1st element of the array.
3. Now I need to figure out how to sort an array.
See the problem?
The link leads to a 6 years old posting. The shirt isn't avaliable there anymore. The link describes the shirt, and I am asking if people know where the shirt can be purchased today.
Lawrence Lessig is my personal hero.
For those of you who are not donating your clock cycles to seti@home, you might want to try distributed.net. Right now, they are working on cracking a 64bit encryption key, which is also a contest from RSA securities. They are also working on finding more Optimal Golomb Rulers, so it seems that trying to factor this really huge number would be a nice fit. Take a look at the RC5 stats here. They are nifty.
It may be problematic insomuch as they are already working on three projects, and spliting off into another project would be troublesome. But, there are no other serious efforts going on towards these types of projects, so I suppose us d.net fans will just have to wait and see.
Lawrence Lessig is my personal hero.
P=NP is in fact true...
I've found a remarkable proof of this fact, but there is not enough space in the slashdot comment field to write it.
A: None. The Universe spins the bulb, and the Zen master merely stays out of the way.
Can you imagine that? :-)
Kind thoughts do not change the world
No way, that's crap! They can't patent the idea of running a program on a bunch of computers, especially if it's all your code, can they? I guess I shouldn't act surprized by what can be patented now, but if any of us got in trouble for that it would be insane, that's like patenting the idea of using jet engines to break land speed records, it's just the only way to solve the problems, no one group can take that can they?
spacefem.com
With 1,000,000,000,000,000 or so of my closest friends, everybody take a chunk of integers, give out some factoring code, and start grinding away every night. It all in the organization, think seti@home.
spacefem.com
I wonder if there is any guessing algorithm that works on a reasonable hardware in a reasonable time and still has more chances than any regular lottery with similar prizes... Yes, I know that lotteries is a tax for those who don't know math, I just don't think that far.
Don't say No, say May be
I thought I had the money in the bag, but my calculator got an overflow error
I'll think of a funny sig later on
Ever since Broderick played a hacker who got chased around by "the government" in the hit 80's movie "Wargames", all us American geeks have this weird fantasy about "the government" wanting our brains and being willing to kill for our knowledge. Many movies since then have picked up on this fantasy and encouraged the same sort of thinking, "The Matrix", "Hackers", and "Yentl" being prime examples. In any event, I don't think it's so much a disassociation from being part of the bigger global picture so much as a simple, yet perverse desire to be stalked by men in dark suits, ties, and shades, sporting semiautomatic pistols with silencers. A desire to be James Bond with a PalmPilot running an home-brew OS while dot matrix printers at the homestead are printing out reams of secret government documents onto green-striped paper. "The government" isn't the US government, but rather the fictional organizations contrived in these movies, internalized into geek fantasy.
There are 0x40000000 types of people: those who understand 32-bit IEEE 754 floating point, and those who don't.
It's pretty sad really when you think about it. We have so many diseases that have no cure... but these companies are willing to put out this kind of money to make sure thier encryption is really secure... I'm sorry, I forgot I am not a medical researcher. What am I doing wasting my time posting this message, I'd better get cracking...
I already know the answer....
42!