Robert J. Hansen
rjh at sixdemonbag.org
Wed Apr 18 16:05:22 CEST 2007
-----BEGIN PGP SIGNED MESSAGE-----
> On 200704172359, Robert J. Hansen wrote:
>> 1. We are unlikely to ever be able to brute-force a 256-bit
>> keyspace. Ever. Not until computers are made of something other
>> than matter, occupy something other than space, run on something
>> other than energy, according to rules other than physics.
> I was under the impression that quantum computers were about to
> a break in factorization. From quick grep on Wikipedia, I find that:
They've been "about to provide" a break in factorization for the last
> However, I assume you know what you talk about, when you say that we
> aren't likely to factor 256-bit-numbers ever. So please restate
> that --
> even in the face of quantum computers -- we won't ever factor 256 bit
We're already factoring 256-bit numbers. Fortunately, I didn't claim
256-bit composites would forever be secure. I claimed 256-bit
keyspace searches would be secure.
Keyspace search is a different set of problems than factorization.
For a brute-force search the best we can do is Grover's quantum
database algorithm, which reduces it down to an equivalent 128-bit
keyspace. From there we use quantum thermodynamics--namely the
Margolus-Levitin theorem--to get some reasonable bounds on how much
time, energy, etc., are required to do it.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
-----END PGP SIGNATURE-----
More information about the Gnupg-users