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? 768-bits 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 Springer-Verlag.
> 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 50-digit 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 well-established
algorithm against it would be better.
> >> Well, it took a distributed team a couple weeks last year to crack a
> >> 128-bit key, so if we got the same size team together, it would only take
> >> 2^(960-128) 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. ;-)
128-bit symmetric keys are not the same as 128-bit asymmetric keys.
Have you ever noticed how people talk about 1024-bit public keys (for RSA,
or DSA, or a similar asymmetric algorithm) and
such, as well as 256-bit 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/
