Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

Win $200,000 In RSA's Factoring Challenge 152

Posted by timothy from the just-did-it-in-my-head dept.
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.
This discussion has been archived. No new comments can be posted.

Win $200,000 In RSA's Factoring Challenge More

Win $200,000 In RSA's Factoring Challenge

Comments Filter:

  • Re:Clustering.. (Score:1)

    by Anonymous Coward
    I think you need a Beowulf cluster to crack one of these.

    Fucking hell, that was almost relevant. Unlike this.

  • Of course (Score:1)

    by Anonymous Coward
    If you *do* crack it, you will be sued and go to jail under the DMCA

  • Re:Method of doing this? karma whore ... (Score:1)

    by Anonymous Coward
    Linux is an operating system with math emulation, operating on signed integers, rational numbers, and floating point numbers. It has a rich set of functions, and the functions have a regular interface
    home page for Linux [linux.com]

    Please mod me up too, I posted a link !!!!

  • Re:Imagine if you will.. (Score:1)

    by Anonymous Coward
    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

  • the answer is..... (Score:1)

    by Anonymous Coward
    ok. hold on, just let me click ok..... DAMN IT!! windows crashed... i guess i have to start over.

  • So Long and Thanx for all the Fish.... (Score:1)

    by Anonymous Coward
    I just showed the RSA numbers to my dolphin and he just laughed.... eeeeee eee eee

  • Re:Translation (Score:1)

    by Anonymous Coward
    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.

  • Stupid joke (Score:2)

    by Anonymous Coward
    I have a nice factorisation of the 617
    digits one, but it is too big to fit in this post...

  • Stupid windows calculator (Score:2)

    by Anonymous Coward
    Cut and paste the big number into windows calculator and watch the number pad go nuts.

  • ok... (Score:4)

    by Anonymous Coward on Wednesday July 25, 2001 @05:58AM (#62187)
    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 [rsasecurity.com]:

    As shown, to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM. These are estimates based on today's best factoring technology.

    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.

  • Re:Imagine if you will.. (Score:3)

    by bluGill ( 862 ) on Wednesday July 25, 2001 @06:34AM (#62191)

    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?

  • 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. :)

  • 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.
  • (Please excuse the spaces in the numbers, it's to counter the lameness filter).

    You are incorrect about the square root.

    First of all, just look at RSA 130. It's a 130 digit number with 2, 65 digit prime numbers. In fact the 2 factors are:

    45534498646 73597218840 36868972744 08864356301 26320506960 0999044599

    and

    39685999459 59745429016 11261628837 86067576449 11281006483 2555157243

    The product of those 2 numbers is:

    18070820886 87404805951 65616440590 55662781025 16769401349 17012702145 00566625402 44048387341 12759081230 33717818879 66563182013 214880557

    Which has the square root of (approx):

    42509788151 52346540745 26976625052 94703186899 16508643485 6734890373.3

    Which is LESS than one of the factors.

    This means that checking UP TO the square root was not effective in this case.

    The other point is that the big products appear to generally be 2x the number of digits of their factors. This means that to pick your starting point for the factors, you use the square root of the product. Fitting the numbers isn't something you can just easily brute force. In RSA130 the two factors had a difference of:

    58484991871 38517898242 56073439062 27967798521 50395004768 443887356

    That is a lot of comparisons.
  • 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!)
  • 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.
  • Not exactly...

    For n, there is at least one factor that is between 1 and sqrt(n).

    Thus, for 14, factors being 2 and 7, and sqrt(14) being ~3.741657, your statement is false.

    Although, once you know one factor, the other must fall into place.

    As a side note, if you're too lazy to figure out which numbers are prime before trying them, just try all numbers that end in 1,3,7, and 9. After 10, those are the only digits a prime can end in.
  • All those numbers are odd. I had an idea about dividing by 2 :)
  • 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.
  • 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".
  • It seems a lot of work, and not terribly interesting thing, to find the factors of some particular large number. Enough cycles and a reasonable algorithm, and someone will (eventually) get it.

    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.

  • But there is no way for you to factor any of these numbers while you're still alive.

    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 [claymath.org] for solving that one. I guess if you solve it the right way you should be able to quickly claim your 1.6 mil.

  • Re:Translation (Score:4)

    by gorilla ( 36491 ) on Wednesday July 25, 2001 @07:26AM (#62209)
    You're wrong - we do not have a generalizable method of factorization. This means that if you factor the RSA-576 number then there is nothing which will make it any easier to factor another random 174 digit.

    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.

    --
  • Surely the efficient algorithms mentioned above would be more efficient than guessing?

  • Actually, there are many better ways. (First of all, you only have to iterate from 2 to sqrt(n) in your algorithm :) ). The current best way is a Number Field Sieve [studentenweb.org], at least for large numbers. Search around to see what it is.
    The second volume of Knuth's Art of Computer Programming series [amazon.com] has a good discussion of different factoring algorithms, and their applicability at different times.
  • Ah, all you have to do is factor that 704 bit number and there you go.

    Or, alternatively, you could go factor the 704 bit number in the RSA challenge, take the $30,000, go buy Knuth a beer and just ask him what the answer is. :)
  • 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..."

  • Translation (Score:3)

    by First Person ( 51018 ) on Wednesday July 25, 2001 @05:59AM (#62215)

    The first gradstudent to develop a serious quantum computer is gonna pick up a lot of cash.

  • Hmmm, I have the original edition. I don't see a question 47. Question 16, the last one, is the only one rated 50 that I see: 'Are there infinitely many Mersenne primes?'

    Intuitively, I would say yes. I can't prove it. I don't know that anyone has.

    Knuth does say, in the 'Notes on the Exercises', that a 50 is a research problem that hasn't been solved yet. As his example he uses Fermat's last theorem. Of course, the book is copyright 1969. Don't know if he's corrected that in the latest edition. No reason to buy the new one, I'm not finished with this one yet!
    --
    Alex Johns

  • 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.

  • 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.

  • Imagine if you will.. (Score:3)

    by iamsure ( 66666 ) on Wednesday July 25, 2001 @06:11AM (#62221) Homepage
    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..
  • The prime number theorem approximates the number of primes < 10^617 as approx. 7*10^612

    pi(x) ~ x/(log x - 1) where x = 10^617 and log is the natrual log

    See http://www.utm.edu/research/primes/howmany.shtml#1 [utm.edu]

  • Just to get us started ... (Score:5)

    by James Ezick ( 71815 ) on Wednesday July 25, 2001 @06:47AM (#62224)
    Well let's see ...
    2 ... None are even ... nope.
    3 ... None of the digit sums is divisible by 3 ... nope.
    5 ... None end in 5 or 0 ... nope.
    7 ... Well, I'm out of ideas.
  • 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.

  • Problem with just releasing the algorithm is that you take down the world's encryption systems in a single blow. That's a pretty mean thing to do.

    I'd recommend giving the world a chance to update its mathematics first: apply the algorithm a few times to prove that you've got it, and then let the world know that you have a dead-man-switch in some random location, just waiting to release the algorithm should something happen to you.
  • 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 [redpolygon.com]
    http://www.hyperpoem.net

  • Re:Translation (Score:3)

    by anacron ( 85469 ) on Wednesday July 25, 2001 @07:08AM (#62229)
    Yes, the grad student will. But has anyone figured out why these numbers were picked? Isn't it true that for every number we factor the set of available "secure" keys shrinks by 1?

    Isn't this almost like turning the community against itself "Here, factor this number and win 200k", but by doing so we're actually breaking a number that's important to us in some way we just don't know how? I mean, for someone to pay 200k for a SINGLE number to be factored, the payoff on their side must be enormous. What's their ROI for the 200k they've spent? More importantly, WHY are they asking us to do this?

    .anacron
  • 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.
  • Okay, let's say I'm bored, and I am not familiar with the details of these challenges. I just have to pick two prime numbers that, when multiplied, equal the result?

    I'm serious here. I know it is one shot in a trillion or 10, but simply as an exercise, is that all there is to it?
  • Try google:

    http://www.eff.org/Misc/Graphics/nsa_1984.gif

    Now go to cafepress, and have one printed.
  • Okay, this is a serious question. I'm not much on math...

    Let's say I had a list of primes (which, I suppose, I would have to find first). I pick two, and want to multiply them. Can I use a computer? Is this one of the problems? I tried some large number operations with bc, and it core dumped on me.

    Call it a shot in the dark, call it boring, but it would be nice to have a list of prime numbers, pick a couple, check them, and see if I hit it. Not that I expect to, but I'm always looking for a way to alleviate the boredom of confernece calls...
  • 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.
  • RSA have several different levels of prizes.

    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.

    ---

  • 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
  • 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
  • ok, so the max number represented by 576 bits is 24733040147310453406050252101964719003513134910121 18399140630560928972251065318671703164010612430449 89597671426016139339351365034306751209967546155101 893167916606772148699136

    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!

  • ok, so the max number represented by 576 bits is
    247330401473104534060502521019647190035131349101 21 18399140630560928972251065318671703164010612430449 89597671426016139339351365034306751209967546155101 893167916606772148699136
    so, say you wanted to solve it in a lunar month.You would need to try something on the order of
    883322862403944764501794717927311392982611961075 75 65711216537717603472325233280970368442895044394463 91420255092914783354826303693952682892741236268221 0470282735956148167826
    factors per day or
    368051592668310318542414465803046413742754983781 56 52379673557382334780135513867070986851206268497693 29758439622047826397844293205813617871975515111758 769595113998172840326
    per hour or
    613418654447183864237357443005077356237924972969 27 53966122595637224633559189778451644752010447496155 49597399370079710663073822009689363119959191852931 2826585233302880672
    per minute or
    102236442407863977372892907167512892706320828828 21 25661020432606204105593198296408607458668407916025 91599566561679951777178970334948227186659865308821 880443087221714677
    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 about
    617542959210482443413008607634637255048426967358 41 91243355002259457438595524172029124979552458558672 34341034133758742263188689327699355242471411637798 00504
    years at that rate if my calculations are right....

    ---

  • Uhhhh ... no I'm not. One of the factors is guaranteed to be less than or equal to the square root. We're only trying to find that one -- once you've found that number, you've found both of them. The other one is the quotient of the division, and the fact that it is an integer shows you that you've just found the factors. *No shit* one of the numbers will be bigger than the square root -- given that the number will never be a perfect square (since we choose two different primes) this is absolutely guaranteed.

    Did you actually read my message? If you did, please read it again. My whole point was how dumb a brute force algorithm was -- I sincerely hope you didn't think that I was suggesting that taking far longer than the lifespan of the universe to solve the problem was reasonable.

  • Re:Answered my own question: see URL (Score:3)

    by egomaniac ( 105476 ) on Wednesday July 25, 2001 @09:10AM (#62241) Homepage
    Please define "trivial", 'cause I don't think we're using the same definition of it.

    I don't know how many primes there are below 10^617, but here's a hint: it's a LOT. A lot a lot. I don't know what the ratio of primes to nonprimes if, but let's just assume that 1 in 1 trillion numbers up to that level is prime (and I imagine that's conservative). 1 trillion is 1,000,000,000,000, or 10^12. So that reduces our number of primes down to 10^605. That's still a 605-digit number of them. Say it's only 1 in 100 quadrillion numbers -- still 10^600 primes.

    So in order to solve the problem, you just attempt to divide the big number by each of the primes, and when you get an integral result, you stop. In fact, you only have use primes up to the square root of the number. The square root of 10^600 is 10^300. Assume you have a super-duper fast machine which can divide such an insanely huge number in just, say, 10 clock cycles, and it runs at 10GHz. That's a billion checks per second (10^9) -- really fast, huh?

    So let's figure out how long our super-fast machine would take to crack this code using your method. 10^300 checks, divided by 10^9 checks per second, gives you 10^291 seconds. There are approximately 31,557,600 seconds in a year, or 3.15 * 10^7. 10^291 / (3.15 * 10^7) = 3.17 * 10^283. That's 31.7 million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million years.

    I'm glad to know, however, that I can now file this problem away in my "trivial" category.
  • After all, ICFP [inria.fr] 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 :).
  • No...all numerals are lowercase. Uppercase 1 is !, and uppercase 2 is @...etc. The reason you rarely see uppercase numerals on computers is because of the binary issues. !))!)! is much harder to read than 100101.
  • I would be doing this now, but I have one slight miniature problem:

    Error: 'long long long' is too long for GCC

    Is there any nice, easy way around this that will let me not rewrite division?

  • 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!
  • I don't know how to help you with 7, but I did just save you a millisecond with 5.

    Yeah? How long did it take to read your post?

  • lets not forget that computers do this many times a second
  • Not at cafepress. Perhaps that why it was mentioned in the parent post. WOW!
  • We've only just put their cancer cure on hold to help SETI look for lights in the sky. And now this??
  • Wouldn't it be quicker to stop once n is greater than or equal to the square root of the number to be factored?

    You already have the "j", which will cover all numbers above the square root.

    This is similar to brute force prime finding...

    Also, why recurse? At this number of digits, the number of recursions is gonna give your system a headache. Just do a linear scan from 2 to square root of n equals x

  • Which you found out using FactorPad [32768.com] for your Palm, right?

  • 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.

  • Wouldn't it be quicker to stop once n is greater than or equal to the square root of the number to be factored?

    Only in an abstract kind of sense. Given that the numbers are composite (and the RSA could be lying here) - the alogrithm will be sure to have finished before your optimization comes into play. Hence the calculation as to what the square root was will slightly slow down the overall run time.

  • Didn't the mathematician guy (who got killed) use his solution of "factoring large primes" to break encryption?

    Please explain how that is possible.

  • Warning to Slashdot users workin on this! (Score:5)

    by dstone ( 191334 ) on Wednesday July 25, 2001 @07:23AM (#62263) Homepage
    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.

  • Re:Translation (Score:3)

    by ichimunki ( 194887 ) on Wednesday July 25, 2001 @07:34AM (#62265)
    If you read their FAQ, you will get most of your answers. They estimate that in order to get the factors for a 760 bit key in a year or less it would take 215,000 Pentium class machines, each with 4gb of RAM (although they say a 430 bit key is trivial to factor). That's a lot of horsepower for a single set of factors. You'd need to rerun all that for each key you wanted to crack. Their purpose seems to be twofold: to prove how hard it is to get around the longer key security, and to encourage people to seek better algorithms related to factoring.

  • RSA have several different levels of prizes.

    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

    Good luck on getting those anytime soon.

  • Yes, the number of secure keys decreases by one, but there are (by my calculations) 1.89e151 512bit prime numbers. We will have quantum computers before we run out of numbers.

    They are doing this to continually prove how difficult it is to factor numbers. Even with everybody's new 1.7GHz P4's it still takes forever.

  • Generate one recursively... for n, all possible factors are between 1 and sqr(n)

    Sig: Tell all your friends NOT to download the Advanced Ebook Processor:
  • From: http://dbs.cwi.nl:8080/cwwwi/owa/cwwwi.print_proje cts?ID=12 [dbs.cwi.nl]

    CWI [www.cwi.nl] 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 [codebook.org].

  • What do you think the General in General Number Field Seive (GNFS) stands for?

    See the RSA Crypto FAQ [rsasecurity.com].

  • techniques to factor big numbers (Score:5)

    by plcurechax ( 247883 ) on Wednesday July 25, 2001 @07:15AM (#62285) Homepage
    If you want to actually try this, there are several things to realise, first you need a lot of computing power, including at least one very large multiprocessor machine with several (>4) GB of RAM. Think high-end Alphas, slightly dusty Crays, think big.

    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.

  • Re:Stupid joke (Score:3)

    by Kraft ( 253059 ) on Wednesday July 25, 2001 @06:54AM (#62290) Homepage
    LOL.... no this is a cool joke!! I presume you are referring to Fermat's comment in the margin on his notebook about having the solution to his own theorem.

    I just read Fermat's Last Theorem [amazon.co.uk] by Simon Singh a month ago and I loved it.

    -Kraft
  • laughably easy? [rsasecurity.com]
  • For those who want some money but don't know how can start here [okstate.edu].
  • GNU MP is a library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. It has a rich set of functions, and the functions have a regular interface.
    home page for GNU MP [gnu.org]

  • Raise the Prize amount please. (Score:5)

    by egommer ( 303441 ) on Wednesday July 25, 2001 @06:01AM (#62297) Homepage
    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. [slashdot.org]

  • ...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?

    • SDMI: Go ahead, crack the encryption.
    • Researcher: Done it. That was easy. Want to know how?
    • SDMI: Sure, if you want to go to jail.
    • Researcher: Say what?
    • SDMI: No, say nothing, trusting fool.

  • Wonder if Distributed.net will pick this up? (Score:3)

    by pgpckt ( 312866 ) on Wednesday July 25, 2001 @06:03AM (#62304) Homepage Journal
    For those of you who are not donating your clock cycles to seti@home, you might want to try distributed.net [distributed.net]. Right now, they are working on cracking a 64bit encryption key [distributed.net], which is also a contest from RSA securities. They are also working on finding more Optimal Golomb Rulers [distributed.net], so it seems that trying to factor this really huge number would be a nice fit. Take a look at the RC5 stats here [distributed.net]. 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.

  • Re:techniques to factor big numbers (Score:3)

    by Eryq ( 313869 ) on Wednesday July 25, 2001 @07:27AM (#62305) Homepage
    You forgot the massively-parallel BINOMIAL algorithm: By Infinite Number Of Monkeys In A Laboratory.

    I started the task at 8:00 this morning, and by 9:32 a shrill schreeching sound told me that one of the monkeys had solved the 1620-bit number.

    Now if I could just figure out which one...

    Plus, an infinite number of bananas costs more than my prize money. :-( And don't get me started about the mess they've made...

  • okay, a slightly more detailed number than '1 in a trillion or 10' can be made.

    first of all, you need to know all the prime numbers less than the square root of the number you're trying to factor (up to appr 85 decimal digits). Now, due to the prime number theorem (see Riemann for outline, Hadamard & Vallee Poussin for proof) you can know that the number of prime numbers less than 'n' is on the order of n/log(n). Now, the odds you'll pick the correct pair are 2 out of that number, or:

    2/[(sqr_root(RSA-576)/log(sqr_root(RSA_576))^2]

    now, i just don't care enough to work that out, but i think you'd have a better shot if you started buying superball lotto tickets...

  • Clustering.. (Score:3)

    by roguerez ( 319598 ) on Wednesday July 25, 2001 @06:01AM (#62312) Homepage
    I think you need a Beowulf cluster to crack one of these.

    Can you imagine that? :-)

  • 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.
  • I bet they all turn out to be primes :)

  • Re:Oh come on, I could to it... (Score:3)

    by Unknown Bovine Group ( 462144 ) on Wednesday July 25, 2001 @06:46AM (#62327) Homepage
    You work for the US Patent office don't you?

Slashdot Top Deals

Some people claim that the UNIX learning curve is steep, but at least you only have to climb it once.

Close