> -----Original Message-----
> From: Todd [mailto:[EMAIL PROTECTED]]
> Sent: Friday, 1 December 2000 3:44
> To: '[EMAIL PROTECTED]'
> Subject: Re: Ben's Big Crypto Flamefest
>
>
> folx,
>
> On Thu, 30 Nov 2000, Ben Nagy wrote:
>
> > No. You couldn't. Brute forcing a 4kb key is not possible
> without a trapdoor
> > or flaw in the algorithm. IOW - even taking factoring as an
> example...
> > Quantum computing may become real. This effectively square roots the
> > complexity of an arbitrary calculation. That makes a 4096
> bit number as hard
> > to factor as a 2048 bit one. Big deal. 2048 bits is well
> outside the realms
> > of possibility with an amazing new algorithm for factoring.
>
> careful here. unless i'm misunderstanding your calculation, quantum
> algorithms (when running on quantum computing devices that don't exist
> yet) reduce complexity to the square root, but srt(4096) = 64, not
> 2048. 64 bits is quite tolerable (not easy, but tolerable),
> especially if
> there are any entropy-reducing errors in the algorithm already.
>
> am i missing something?
Yeah - you're misunderstanding. If you square root the complexity of an
exponential calculation then you halve the exponent. It does not sqrt the
keyspace.
Check out some links or mail archives that talk about "Grover's Algorithm"
if you're interested. Grover's alg is the funky search-space one that allows
those sort of speedups for "general" searching (like keyspace brute
forcing). Shor's is the factoring one.
As an interesting aside - I'm trying really hard to find some hard
information on the effect of Shor's factoring algorithm on large
factorisation problems. We know that it brings the complexity back to
poly-time but I'm yet to find a hard reference about what that means for
work times in real situations (assuming that it's possible to build a QC
that big in the first place).
>
> =========================================================
> Todd Underwood, [EMAIL PROTECTED]
>
Cheers,
--
Ben Nagy
Marconi Services
Network Integration Specialist
Mb: +61 414 411 520 PGP Key ID: 0x1A86E304
-
[To unsubscribe, send mail to [EMAIL PROTECTED] with
"unsubscribe firewalls" in the body of the message.]
