Subject: Re: [stella] I can't find it From: Julian Squires <tek@xxxxxxx> Date: Sun, 17 Sep 2000 14:34:01 0230 
Sorry I didn't get to responding to this sooner, I hadn't been checking my mail in the last week. On Mon, Sep 11, 2000 at 11:10:21PM 0500, Russ Perry Jr wrote: > Sadly, there's no way to assume that the numbers used for the 7800 were > of Mersenne form, is there? Or can we, just because they were able to > make primes of a sufficient size to begin with? It is extremely doubtful they were Mersenne primes. > Up to 200 digits sounds right up our alley, but I guess it's the > supercomputer that stops us? It would take quite a while, even with the supercomputer. 200 digits is ~664 bits, right? 768bits has been done before, iirc. It takes a long time and a lot of hardware, however. > This is a bit of what I feared... My post was slightly tongue in cheek, > as you might have noticed. Suggesting that we could cut out certain > combinations isn't trivial though... It does cut down the space quite > a bit, but just not in a big enough way. If it cuts it down to 10% of > a really large space, it's still a really large space. :( See below. > I'm not sure I understand George here... I didn't mean to imply that > there was this list out there that Atari used, but if there were lists > of all primes up to certain point, it could be used to cut down the > key space quicker. Generating primes is trivial  there are infinitely many primes, and a hell of a lot of the size we want. Using a list offers no benefit for this size of number  the list would be /massive/. > His answer kind of implies one thing that I was asking if we knew about > the number to be factored  if they found two huge primes to multiply > together, doesn't that imply that they're "special" primes in some way? No. > Another thing... Not that it'll cut down the key space any, but if > you're looking for factors in a brute force way, you start at the square > root of the number and go down, right? Modern factorization methods are extremely sophisticated  much more than naive brute force, but they're still brute force. (Starting at the square root and working down is considered the slowest possible way, O(n**(1/2))  even Pollard's rho method is much better (O(n**(1/4)*log**3(n)))) Pick up a good book on crypto which covers the factoring problem  for example, Neal Koblitz's ``A Course in Number Theory and Cryptography'' published by SpringerVerlag. > Also, is there anything about how "robust" a number is that suggest we > needn't even bother checking numbers less than, say 100 digits, or might > they have thrown in a 50digit number just to be coy? Working heuristically would tend not to pay off, as it is likely they just generated two large random primes of the appropriate size, which is the usual way of doing these things. Setting a wellestablished algorithm against it would be better. > >> Well, it took a distributed team a couple weeks last year to crack a > >> 128bit key, so if we got the same size team together, it would only take > >> 2^(960128) weeks to crack this one.... right? > > Heh, I don't know if your math or method is right, but that's the kind of > number that was scaring me about this whole thing. > > On the other hand, if it's going to take decades to crack, the sooner we > get started the better. ;) 128bit symmetric keys are not the same as 128bit asymmetric keys. Have you ever noticed how people talk about 1024bit public keys (for RSA, or DSA, or a similar asymmetric algorithm) and such, as well as 256bit cipher algorithms (like the AES candidates) or lower? There are completely different principles behind symmetric and asymmetric systems. You can't generalize the time taken to attack one into the time to attack another. Also, do you know how long 2^832 weeks is? I'll give you a hint, you won't be finishing anytime during the lifespan of the earth. > And if they come up with a better method in the meantime, then we only > wasted CPU cycles that were being wasted anyway, right? And hell, keep > in mind that some of the DES challenges took less time than they should > have because they lucked out and hit the correct combos early in the key > space. We might be so lucky as well. A distributed effort for this would definitely be neat, but realize it's a huge effort, and probably isn't accessable at the moment. Perhaps there is a possibility with TWINKLE, Shamir's neat optical factoring box? (I don't know anything about it, except that it hasn't actually been constructed yet, so I don't know if it fits  although I believe it is still impractical for keys larger than 512 bits)  / / Julian Squires <tek@xxxxxxx> /  Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread 


< Previous  Index  Next > 

Re: [stella] I can't find it, Russ Perry Jr  Thread  Re: [stella] I can't find it, Russ Perry Jr 
[stella] RE: Thrust illegal opcodes, Thomas Jentzsch  Date  Re: [stella] I can't find it, Russ Perry Jr 
Month 