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

 


Forgot your password?
Close
typodupeerror
×
Encryption Security Hardware

RSA-576 Factorization Officially Announced 141

Posted by timothy from the what-google-does-in-its-spare-time dept.
product byproduct writes "RSA Security finally has a news item about the December 2003 factorization of RSA-576. (See earlier Slashdot coverage). We now know what the computational cost was: the 174-digit number was factored "using approximately 100 workstations in a little more than three months"."
This discussion has been archived. No new comments can be posted.

RSA-576 Factorization Officially Announced More

RSA-576 Factorization Officially Announced

Comments Filter:

  • Lots of hardware... (Score:5, Insightful)

    by basil montreal ( 714771 ) on Wednesday April 28, 2004 @08:16AM (#8994982) Homepage
    That's a ton of computer hardware to use on factoring... I wonder why they didn't just use a distributed system (like seti@home) to do this... at least it's free.

    • Re:Lots of hardware... (Score:5, Interesting)

      by ezzzD55J ( 697465 ) <slashdot5@scum.org> on Wednesday April 28, 2004 @08:25AM (#8995023) Homepage
      Because it's difficult to efficiently parallelize (distribute) the factorisation algorithm, especially the final step which so far has always happened on 1 machine. In fact, if you can paralellize the final step of the GNFS (general number field sieve is generally used for these factorisations), you have yourself a PhD. thesis (in math and/or CS), I remember reading in sci.crypt.
    • You mean like the contribution of http://www.nfsnet.org/ ? And not everything can be done there - the final step (the matrix step after the sieving) isn't easily done in parallel. It was done on a Cray at the CWI for the previous challenge, and this one used a 16-computer high-speed LAN I think.

    • Re:Lots of hardware... (Score:4, Insightful)

      by Chilliwilli ( 114962 ) <tom.rathbone@NosPAm.gmail.com> on Wednesday April 28, 2004 @08:37AM (#8995074)
      I'm sorry but factorisation problems and SETI really infuriate me. Firstly we can calculate how long something will take to compute with ease using simple the simple CS complexity analysis we all learnt at university.. then theres the SETI people.. not that I don't want to know whether there's life on other planets but to be honest there is so much we don't understand on our own planet that could have far greater reward for us all. Things I'm talking about might be research into climate, new fuels, medicines. The only distributed task I contribute to is folding@home because all others don't seem worth the extra energy and heat my PC will put out.
      • I think that distributed computing is wonderful. It allows us to divide and conquer which is what the developed world should be about.

        I agree that the analysis could just as effectively be done using bif-O notation and all that, but I still dont think we should knock it.
        If you have a problem with people factoring RSA keys, then just dont take interest - go somewhere else.

        Personally, I would like to distributed computing used to find out more about the origins of our universe etc..
      • There are plenty of projects out there like that, you just have to search for them. I just posted a comment on the granparent about distributed.net, and I personally am working on a distributed computing project to debut in the summer looking for concatanated primes, The Catcon Project [sourceforge.net]
      • ... The only distributed task I contribute to is folding@home because all others don't seem worth the extra energy and heat my PC will put out.

        Tell you what, when you pay for my PC and my electricity bill, then you can decide what distributed tasks I contribute CPU time to.

        Yes, that's a bit of a rant, but it is up to the individual to make their own choices about which projects they contribute to. (Does this mean you also complained about all of those screensavers that burned CPU cycles displaying fly
        • Yes I am!! First off it's not a money issue what so ever but an enviromental one. Screensavers are the most pointless things in existance in this day and age of power saving monitors. People are free to spend their money on what they want but as long as we all have to share this miniscule world we should all do our part in seeing that our currently limited energy resources are put to good use.

          So Nah!
    • Go to distributed.net [distributed.net] and download their client. You can work on factoring RC5-74 (a 74 bit number from RSA). They've just finished up RC5-64 (A 64 bit number from RSA). If your computer finds the key, you get $1,000 and $8,000 goes to charity. They also have other distributed projects, like seti@home, including one to search for mathematical constructs known as Optimal Golumb Rulers. The best part is the client runs at the minimum priority, so you only give up cpu cycles if you don't need them. I've

      • Cracking RC5 has nothing to do with factorization.

        RC5 is a symetric crypto algorithm and winning the challenge is not a matter of smart algorithms like in the factorization case but of brute force, because one "just gave to" try all keys (statistically speaking you're likely to try about half of them, i.e. 2^71 keys) until one decipher the challenge in something meaningful. (in the case at hand recognizing something meaningful is easy as part of the text in the message is already known, in the real worl

      • The best part is the client runs at the minimum priority, so you only give up cpu cycles if you don't need them.

        This is something I don't understand: I have either Seti or Folding (not at the same time) running on my Linux box in real-time priority and I can still compile, listen to Shoucast and do everything I want (even launch mplayer if you wish). Of course it's more difficult if you want to play a DirectX game, but I don't see the use of these programs running only at 1% of the CPU when you can do mo
        • Well I start the distributed.net client at start up and turn it off at shutdown, with it set at the minimum priority. I can still play games and do CPU intensive things. If I do something moderately intensive, and the client were on normal priority, the kernel throttles back the CPU cycles the client can get. But if I do something that needs as much of the CPU as it can get, like a 3d accelerated game, the kernel will allocate time to both the game and the client, making the game slow and choppy. So, by
      • Correction: the RC5 contests are not factoring contests, they are brute-forcing contests.

  • Still safe for a while (Score:5, Interesting)

    by BuddieFox ( 771947 ) on Wednesday April 28, 2004 @08:19AM (#8995002)
    We should still be reasonably safe using the RSA-algorithm for a while more since the number is the equivalent of a 576-bit key. Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).

    Safe, that is unless someone invents quantum computers and makes them easy to produce.. :)

    • Re:Still safe for a while (Score:5, Interesting)

      by Ckwop ( 707653 ) * on Wednesday April 28, 2004 @08:25AM (#8995026) Homepage

      Also remember the moore's law doesn't apply to factoring algorithms.. This is because for the GNFS the *memory* speed is what's important and that isn't growing nearly as quickly..

      Not convinced? Look at the linear proportionality in this graph [inria.fr]

      Simon.

      • Re:Still safe for a while (Score:1, Informative)

        by Anonymous Coward
        You complete idiot. Linearity in the _length_ of the key vs. year means _exponentially_ faster-running factoring over time. But if you couldn't figure that out for yourself, you could at least look up your screen a couple of inches where they state:

        For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

        At any rate, time to go buy a G5 I think, they are supposed to have pretty fast memory.

        • For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

          Sorry for sounding like a dick, but Moore's Law states that the number of transistors per unit area doubles every eighteen months. This does not directly correspond to an increase in computer "speed".

          • no, but history has shown if you can get 2x the transistors you can solve more than 2x the problems at the same time.

            If my package limit only allows 16,000 transistors but in 4.5 years you get 128,000 transistors, you can solve far more problems and that can give you far more preformace than Moore's law by its self.
          • Sure it does.

            Even if one did not INCREASE the number of total transistors - the fact that they are closer together means the clock propogation delay is reduced thus MHz can increase without loss of synchronicity.

            electricity does not travel even as fast as the speed of light - that and heat dissapation are the primary barriors to Moore's law.

            AIK

        • Memory speed vs. CPU speed increases (Score:5, Interesting)

          by billstewart ( 78916 ) on Wednesday April 28, 2004 @12:20PM (#8997257) Journal
          You missed his point, though perhaps he could have expressed it more clearly. Many applications are CPU-bound, some are memory-size-bound, some are memory-speed-bound.
          • CPU speed has been doubling pretty fast, every 1.5-2 years.
          • Memory size (or at least, size/price ratio) has been growing pretty fast.
          • Disk capacity has been booming faster than CPU speed, though disk seek times have been changing much more slowly.
          • Memory speed has been lagging - I forget the exact numbers, but some of the hashcash folks did some research and found the speed doubled every N years, maybe 3-4. Certainly not the same curve as CPU speed.
          If the real constraint in GNFS is storing and retrieving data, not multiplication speed, then you could easily get an environment where memory speed increases are the gating factor for your Moore's Law growth, no CPU speed increases, so your K-bit key is good for 2-3 times as many years as you'd expect.

          On the other hand, factoring is a problem where the increases in Algorithm Speed have been just as critical as increases in Computer Speed. So maybe GNFS has reached the point where it's computer-speed-bound, but next year's Super-Duper-Number-Field-Sieve may be several times more efficient than GNFS, just like GNFS was several times more efficient than NFS in the ranges that are now interesting. Sometimes this happens just because mathematicians keep doing new work, and sometimes it happens because computer capacity (e.g. memory size) grows enough from Moore's Law that algorithms which weren't practical in the past become practical. There were factoring tools that weren't useful when most computers had 128MB of RAM, but work fine now, and there may be tools that aren't practical when most computers have less than 4GB of RAM, but five years from now your SonyNintendo box will have enough RAM to run Sieve@Home.

    • Unless someone comes up with a better factorization algorithm. In fact, if anyone knows of a software package that can solve a system of 640 boolean equations in 640 boolean unknowns, I can give you the factorization of the RSA-640 challenge number [rsasecurity.com]. :-)

      • As it happens, satisfiability [satlive.org] algorithms can solve systems of 640 variables quite easily. No, it's true they can't solve 640-bit factorisations yet, or they would have :). The difficulty of satisfiability systems for randomly generated problems lies much more in the ratio of clauses to variables than number of variables alone.
        • Thank you, the website you mention looks very interesting - I'll definitely check it out (particularly the pseudo-boolean solvers [uoregon.edu]). Actually, I already have the system of equations that would yield a factorization (it turns out they're quite easy to generate using Maple [maplesoft.com]). All I need is a way to solve them. Although the equations only involve the "^" and "&" (bitwise XOR and AND) operators, they are quite lengthy and occupy about 135 MB of hard drive space!!! Since the ratio of clauses to variables is HU

    • Safe from whom? (Score:2, Insightful)

      by dcavanaugh ( 248349 )
      OK, it took 1000 machines and 3 months for this particular example. The task is not impossible, and there are people who really can get their hands on 1000 machines.

      If the goal is personal security, I agree that the average credit card hacker is not going to make the investment. On the other hand, the NSA has the hardware resources to attack on a grand scale, with perhaps even better algorithms.

      It will be a while before RIAA and MPAA can hijack NSA resources to pursue P2P users, so I guess we ARE still
    • Yes, but more importantly, this shows the superiority of elliptic curve cryptography - compare this with the size of the recently cracked elliptic curve key.
      • Surperior in what sense? ECC is typically slower [though not by a wide margin] on desktop processors where multiplication is not that expensive.

        Sure ECC has the size thing beat and is better suited for smaller machines, oh and is neater math, but that's about it ;-)

        Tom
    • The rules are different for public key cryptography. You are correct in that every bit added to a symmetric crypto key doubles the keyspace. In public key crypto which RSA is one type of, it is necessary to add 10 bits to double the difficulty. That 10 bit number is somewhat fuzzy. It can be a little more or a little less depending on whether we are talking about elliptic curves or Diffie-Hellman and others.
    • >Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).

      First, adding one bit to the size of a number only doubles the range of possible numbers.

      Second, even that doesn't apply to RSA because not every number is a possible key (not even close!). A key is the product of two large primes. Numbers like that are thin on the ground.

      Third, there's no value in making your crypto harder to cra
      • First, adding one bit to the size of a number only doubles the range of possible numbers.

        Dear genius:

        That *is* exponential. It's 2 to the power of (number of bits). Add another bit, exponential growth. YMMV, HAND.

        -Mr. Big Fat Jerk

    • ANSI X9F1 -- the influential working group that develops US standards for the financial services industry on data security -- has reportedly decided, at least informally, that 2010 will be the year at which they will require an upgrade from 80-bit to 112-bit crypto security.

      NIST generally follows the lead of X9 in these matters.

      80-bit ciphers are generally understood, on the basis of equivalent resistance to brute force attacks -- the state of the art, as measured by the results in RSA Security's

  • Security (Score:5, Insightful)

    by nuclear305 ( 674185 ) * on Wednesday April 28, 2004 @08:27AM (#8995035)
    Of course, the whole idea behind key strength is rather moot if the user gets careless with his keys/passphrase.

    Unfortunately, crypto is only as strong as the user(weakest link)

    While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.

    Of course, unless you're the NSA and measure their servers by acres...

    • Re:Security (Score:4, Interesting)

      by CoolGopher ( 142933 ) on Wednesday April 28, 2004 @08:41AM (#8995093)
      we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.

      Of course, unless you're the NSA and measure their servers by acres...

      Or if you grabbed the source for the latest windoze worm and modded it to bruteforce keys in addition to spreading...

      I have a suspicion that doing that would give you a supercomputer that quite possibly ranked #1 on the supercomputer charts, and for free to boot*.

      *) Comes with complimentary government provided lodging and meals.

    • While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.
      While that may be true, there is still a significant chance that, with less hardware, the hacker can always get "lucky" and be able to use less computing power to "guess" the factorization. For instance, a hacker could just start with a prime number that is an arbitrary distance from
      • Actually, the chance is negligible if you try that algorithm. Guesswork just doesn't cut it, unless you like betting at odds of 10^170 to one against.

        Responding to the parent post: rather a lot of hackers have easy access to 100 node farms. It's not difficult any more to find 100 cpus, especially for an algorithm such as GNFS which doesn't need especially fast communications between them. The final stages are more of a bottleneck than the sieving, but far from impossible for reasonably clueful people

    • I think that RSA's weakest link is the "Euclidian algorithm" which has a few a few other options.
      RSA keys aren't 1:1 and while my math isn't good enough to prove it, they are 1:many as this code [abnormal.com] shows how it works.
    • I've always been amused by the people who boast about how their laptop (usually) drive is encrypted using some million-bit filesystem and is therefore `secure' even if someone steals the machine.

      Of course, they don't remember the million bits, oh no, they have a passphrase, which is something they can reliably type blind and remember, probably some few 10s of effective bits (as it's probably English).

      So how secure is this data, again?

      • Re:Security (Score:3, Informative)

        by ConsumedByTV ( 243497 )
        While I agree with the sentiment of this remark, I have to disagree with some implementations.

        Yes, it's not going to be difficult to attack the users passphrase if it's stupid. However you make an assumption that most people who encrypt their harddrive keep their keys on the laptop.

        I don't.

        With loop-aes, you have pretty good abstraction.

        So you can have a set of gpg keys, a file encrypted to a given public key, and the data to be decrypted, all in different places.

        In theory, it can be done over a netwo
    • I highly recommend Diceware [diceware.com] for advice on and tools for generating passphrases.
      A Diceware passphrase has 12.9 bits of entropy per word, assuming you can throw dice randomly.

  • More about distributed computing... (Score:4, Informative)

    by BillGodfrey ( 127667 ) on Wednesday April 28, 2004 @08:28AM (#8995037) Homepage
    Stuff to read...

    A primer on distributed computing [bacchae.co.uk]

  • The advantage of one way encryption... (Score:3, Funny)

    by MosesJones ( 55544 ) on Wednesday April 28, 2004 @08:28AM (#8995040) Homepage

    I encrypt everything on my hard-drive using one-way compact encryption, it only cost me $100 and converts every file into 0 bytes that can't be de-crypted by anyone... not even me. Now THAT is proper security.

    I previously used 2^(10e20) bit encryption which would have taken several universes to crack. Unfortunately it took one earth life to encrypt a 1 Mb file so I had to revert to the super-secure method above.

    And Yes I do have a tin-foil hat... why do you ask ? Oh and the application that does the one way encryption. Well I work on Windows but I get this Unix utility called Cygwin and the guy sold me a program that does the encryption. I had a look at what was in encrypt.sh and what it says is

    cat /dev/null > $1

    Amazing how simple UNIX makes encryption... but then I use Windows so its all beyond me.

  • Hundred computers * 3 months (Score:5, Interesting)

    by Gopal.V ( 532678 ) on Wednesday April 28, 2004 @08:29AM (#8995046) Homepage Journal
    That makes it 240000 computer hours ... too cheap .. Think about this :

    "Toy Story 2" had about 800,000 computer hours worth of rendering.
    "The Hulk" had 2.5 Million computer hours [nydailynews.com]
    My office has nearly 400 fast machines , imagine this running them makes it 25 days . Running that every weekend makes it 12 weeks or 3 months ... It's a weekend job if I can sneak this in as along with the next upgrade.

    DDoS time is over with all networks being careful about... the next big windows worm will be a distributed processing program :)

  • Factoring in advance (Score:1, Interesting)

    by Anonymous Coward
    If you knew that factoring big numbers was important to breaking encryption, and would be for quite a long time wouldn't you simply have started a huge factoring effort decades ago? I know I would have.

    • Re:Factoring in advance (Score:4, Insightful)

      by RupW ( 515653 ) * on Wednesday April 28, 2004 @08:42AM (#8995099)
      If you knew that factoring big numbers was important to breaking encryption, and would be for quite a long time wouldn't you simply have started a huge factoring effort decades ago? I know I would have.

      Factoring what? You won't know the number you need factored until you intercept or steal the encrypted data.

      You could, I suppose, start multiplying every pair of primes together and try and organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.
      • Factoring what? You won't know the number you need factored until you intercept or steal the encrypted data.
        Not true, because if you can factorise the modulus in the public key (which is generally easy to get), you can generate the private key.. That's the whole point to this factorisation business :)

        • Re:Factoring in advance (Score:3, Informative)

          by RupW ( 515653 ) *
          Not true, because if you can factorise the modulus in the public key (which is generally easy to get), you can generate the private key.

          Yeah, that was misleading - I was just trying to say you need a target for your arbitrary factor effort. In my mind I'd figured you'd have to have the encrypted message to know what private key it was encrypted for - although I realise now that's not necessarily true (and neither's the reverse). But it could be for real tinfoil-hat types :-)

          There's no good reason, either

      • Re:Factoring in advance (Score:5, Insightful)

        by tadmas ( 770287 ) <david&tadmas,com> on Wednesday April 28, 2004 @09:22AM (#8995379) Homepage

        You won't know the number you need factored until you intercept or steal the encrypted data.

        You don't have to steal anything. The number to factor (the modulus) is given away as part of the public key.

        organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

        For 1024-bit numbers, the factors will be on the order of 512-bits. The density of primes is rougly 1/ln(n), and ln(2^512) is about 355, so you should expect around every 355 numbers to be prime. That's only 3e151 numbers, not to mention that you'd have to figure every product of the two, which is 0.5*(3e151)^2, or 7e302 numbers.

        Staggering doesn't begin to describe how many of these things you'd have to store.

  • 40 Licks (Score:3, Funny)

    by thpdg ( 519053 ) on Wednesday April 28, 2004 @08:34AM (#8995063) Journal
    It begs the question, how many workstations, for how many months, would it take to find out
    How many licks does it take to get to the center of a Tootsie Pop?
    I'm afraid the world will never know.

  • If anyone wants... (Score:3, Informative)

    by Phidoux ( 705500 ) on Wednesday April 28, 2004 @08:42AM (#8995094) Homepage
    ... to waste 3 months and 100 computers trying to read my RSA-576 encrypted information, they are welcome

  • Virginia Tech (Score:1, Interesting)

    by artlu ( 265391 )
    If you think about it, this means that VA could do 1024 bit in 1month. Gotta love the G5 supercomputer!
    artlu [artlu.net]

    • Re:Virginia Tech (Score:4, Insightful)

      by Chexum ( 1498 ) on Wednesday April 28, 2004 @09:26AM (#8995418) Homepage

      Uh, oh, someone is bad at math...

      I don't think VA's unknown numbered G5 park is about 2^448th more powerful than 100 PC(?) nodes. I don't think it's possible.

      Or, I simply have been trolled :)

      On the other hand, let me check my sig again...

  • Why waste all the CPU power? (Score:5, Funny)

    by tangent3 ( 449222 ) on Wednesday April 28, 2004 @09:22AM (#8995380)
    There's a far easier [slashdot.org] way to crack the the key

  • Anyone know what the predicted strenght was? (Score:3, Interesting)

    by pmcevoy ( 10501 ) on Wednesday April 28, 2004 @09:34AM (#8995485) Homepage
    Does anyone know what the predicted lifetime of the 576 bit key was?

    I mean, when they say that we should be using 4096bit keys today, how long do they predict that it will take to crack that key? (taking into account Moores law and perhaps linear growth over time of the number of clients contributing CPU cycles). Is it possible to guestimate?
    • While I don't have the answer I can offer some perspective on the question. You see that the day the key was made, there was a certain state of the art in mflops or some such thing that would represent the speed of arithmetic operations that the fastest processor could do at that time. A determination was probably made that said "In order to perform all the factor tests on a machine running X mflops it will take Y days."

      But the universe refuses to maintain the 'state' in which it was in and several factor

  • Jens Franke (Score:5, Interesting)

    by greppling ( 601175 ) on Wednesday April 28, 2004 @09:36AM (#8995501)
    (As far as I understand, he and Thorsten Kleinjung wrote most of the software used, and did most of the work in the project, while the other institutions were rather donating computing time.)

    I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating. His office consists of 3 huge desks (plus a computer desk); on each of them there is huge bunch of completely unorganized papers lying around, mixed with empty yoghurt cans.

    His mathematical skill is enormous, he has done research in quite a lot of different areas of mathematics (analysis, algebraic geometry, algebraic topology, category theory), but he never bothers at all with making his results well-known. (In fact, at least one time he actually had to be persuaded to even publish his result, which got immediately accepted in Inventionaes, the most highly regarded journal in pure mathematics.) He even couldn't be bothered to apply for a much better-payed position at another university in Germany when he was almost urged to do so.

    Anyone who knows him will burst out laughing when he reads that he supposedly said "I'm very proud of all these individuals from around the world and their efforts to solve this first factoring challenge." and all this other stuff in that paragraph of the article. I bet the author of this press release desperately tried to get some phrases longer than 5 words out of his mouth, gave up, and then decided to just make up all the quotes.

    Now with his mathematical skills, number factoring is (in his own opinion) a rather dull activity. The reason he is doing this is that he expects an economic breakdown soon, and he thinks of his knowledge in number-factoring as an assurance against the coming job crisis. (Of course, his position is guaranteed by the German state until his retirement.)

    But if you manage to get along with him, he is actually quite nice and extremely helpful.

    • Re:Jens Franke (Score:2, Interesting)

      by Xilman ( 191715 )
      I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating.

      I also know Jens quite well (we are on first-name terms) and he seems sane enough to me. Perhaps I have hung around with mathematicians too

  • Next Time, Hire Google (Score:4, Interesting)

    by VernonNemitz ( 581327 ) on Wednesday April 28, 2004 @10:20AM (#8995929) Journal
    They say that Google is preparing an IPO, but sometimes I wonder what they need the money for. They already had enough money for 10,000-100,000 servers, after all. If they doubled or quintupled that acreage of computer-farm, would your search-results come to you down the Internet pipe so much faster that you'd be glad the did?

    And they had the money to hire the experts needed to manage that cluster like a single supercomputer. Sure, they probably got some of that initial funding from ordinary venture capitalists, but what if some Govt. outfit helped, on the grounds of requesting access for occasional factoring purposes? After that IPO gets invested in a bigger farm, not even 2048-bit keys may be safe.
  • Does the numeral posted here [rsasecurity.com] actually equal the product of the numerals posted here? [rsasecurity.com]

    The last digit looks OK, anyway. :-)

    No, don't bother to flame me for laziness... I already know...

    There was a time when I would have tried to do that on paper by hand, just to keep in practice. These days, not only am I too lazy to try that, but I don't currently have any software system at hand that implements indefinite-sized integer arithmetic... and I'm too lazy to implement one.
    • java does this. It works on most platforms. See java.math.BigInteger
    • with a little help from lisp I did this... It checked out... /. is adding some white space to the numbers that isnt reall there...

      i i i i i i i ooooo o ooooooo ooooo ooooo
      I I I I I I I 8 8 8 8 8 o 8 8
      I \ `+' / I 8 8 8 8 8 8
      \ `-+-' / 8 8 8 ooooo 8oooo
      `-__|__-' 8 8 8 8 8
      | 8 o 8 8 o 8 8
      ------+------ ooooo 8oooooo ooo8ooo ooooo 8

      Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
      Copyright (c) Bruno Haible, Marcus Daniels

    • http://www.google.com/search?sourceid=navclient&ie =UTF-8&oe=UTF-8&q=39807508642406493739712550055038 64911990643623425267084063851895759463889572617685 83317+%2A+4727721461074353025362230719730482246329 14695302097116459852171130520711256363590397527 And google confirms the first few numbers...
    • Yes. They are correct.

      BigInteger p1 = new BigInteger("3980750864240649373971255005503864911 9 9064362342526708406385189575946388957261768583317" );
      BigInteger p2 = new BigInteger("47277214610743530253622307197304822463 2914695302097116459852171130520711256363590397527" );
      BigInteger p = p1.multiply(p2);
      System.out.println(p);

      188198812920607963838697239461650439807163563379 41 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 2213051
    • Yes it does.

      Use Pari/GP [u-bordeaux.fr]. It's even GLP.

    • [txr@brasa txr]$ python2
      Python 2.2.3 (#1, Oct 15 2003, 23:33:35)
      [GCC 3.3.1 20030930 (Red Hat Linux 3.3.1-6)] on linux2
      Type "help", "copyright", "credits" or "license" for more information.
      >>> 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * 47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527
      18819881292 06079638386972394616504398071635633794173827007633 56422988859715234665485319060606504743045317388011 3033967

  • soooo.... (Score:2, Insightful)

    by MasTRE ( 588396 )
    It took longer for them to come up with the press release than it did for their code to be broken. Lookin' good, RSA!
  • There is very little info to the article.

    My summary: they used about 100 workstations and it took 3 months. General credits to those involved.

    That's it. Oh yeah, and a quote.

    My interest is in how an individual's effort would have compared to their's. 100 machines is a little too vague - and is only really useful in the initial sieving process anyway. The last stage hasn't been implemented in a distributed fashion yet, so it can only be done on one.

    Perhaps an estimate that can be roughly referenced by ot

    • Jeeze, what planet (or university) are you from? Someplace where Google or Copernic is outlawed?

      Mind you, this is a formal announcement, not an article. The technical details are for the researchers to announce, that's not RSA's reponsibility. And while the inital report of a factoring success -- and mention of any new technique -- usually spreads quickly over the Net (watch the Yahoo Prime Numbers [yahoo.com] group), academic papers take longer. And when you're dealing with experts at this level, they'll take their

      • First: considering that this site is supposed to be "News for Nerds" what news did the article provide? At a minimum it generated a forum to request further, more detailed information.

        Second: Not unlike countless others, you misread one of my posts. I honestly can't see where I asked for theory. I am looking for how hard it was to solve this problem.

        Wasn't that the point of the challenge? To quote the website [rsasecurity.com]: "to encourage research into computational number theory and the practical difficulty of factorin

        • "I honestly can't see where I asked for theory. I am looking for how hard it was to solve this problem," sez TB.

          I sympathize with your interest in some straightforward measure that would allow you to compare one factoring project with some previous project. I really do.

          Unfortunately, I think you are confusing your irritation with the tardy "formal announcement" of the joint project's success -- the basis for the /. "article" -- with your frustration that the prime researchers (Jens Franke and Thors

  • Goes to show (Score:3, Insightful)

    by BCW2 ( 168187 ) on Wednesday April 28, 2004 @01:02PM (#8997765) Journal
    That any key can be cracked if enough computing power is thrown at it. Remember NSA does this as their job, now how many keys have been cracked? All or real close to it.
  • We now know what the computational cost was...

    We also could have spared ourselves the computer-months of CPU time and just computed the computational cost using a few miliseconds of calculator time.

    The only time such an exercise is successful is when a new code-breaking technique is developed to solve the problem, not when brute force wins.

Slashdot Top Deals

I tell them to turn to the study of mathematics, for it is only there that they might escape the lusts of the flesh. -- Thomas Mann, "The Magic Mountain"

Close