From: iagoldbe@csclub.uwaterloo.ca (Ian Goldberg)
Date: Thu, 4 Jan 96 08:30:45 PST
To: cypherpunks@toad.com
Subject: Re: 2047 bit keys in PGP
In-Reply-To: <v02130503ad119cbfdece@[205.231.67.43]>
Message-ID: <4cgva5$qe6@calum.csclub.uwaterloo.ca>
MIME-Version: 1.0
Content-Type: text/plain


In article <v02130503ad119cbfdece@[205.231.67.43]>,
netdog <netdog@dog.net> wrote:
>nobody will ever need more than 640K or RAM?  i wouldn't underestimate the
>ability of technology to grow at a pace that is beyond our wildest
>dreams-especially with this network serving as a virtual office/lab.  of
>course, ymmv.

Order of magnitude check:

There is a very well-defined limit to the size of key that can be broken by
brute force, independent of your "wildest dreams" as to the growth of
technology.  It's the Laws of Thermodynamics.

For a symmetric algorithm for which any value of the appropriate length n
is a possibly valid (and equally likely) key, there are 2^n keys to try
in a brute-force search.  From Applied Crypto, 2nd ed, pp157-158,
setting or clearing one bit takes at _least_ 4.4*10^-16 erg of energy.
For symmetric keys of size 256, then, you would need more than 10^61 erg
(that's 10^45 GJ) of energy just to _enumerate_ the states.  For comparison,
this about 10 billion times larger than the output of a typical supernova.
(Ibid.)

From the same source:

"These numbers have nothing to do with the technology of the devices;
they are the maximums that thermodynamics will allow.  And they strongly
imply that brute-force attacks against 256-bit keys will be infeasible
until computers are built from something other than matter and occupy
something other than space."

Thus this situation is quite different from the 640K of RAM scenario.
It's more like "who would ever need more RAM than you could get by
storing a bit on every subatomic particle in the universe".  It's
not a matter of what resources you can imagine using, but rather,
what resources are in the universe, able to be used.

   - Ian "First post of the morning; it shows, doesn't it..."