From: Derek Atkins <warlord@MIT.EDU>
Date: Fri, 2 Aug 1996 08:29:11 +0800
To: cypherpunks@toad.com
Subject: Re: Is 1024-bit PGP key enough?
In-Reply-To: <199608012016.WAA00739@basement.replay.com>
Message-ID: <9608012108.AA17627@bart-savagewood.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Hi,

> Is security provided by 1024-bit PGP key sufficient against most powerful
> computers that are available today? Say if smoe organization spent 10
> billions of dollars on a cracking machine, would it be possible to crack 
> the keys in reasonable time?

Well, this depends on a couple of definitions.  For example, how do
you define "reasonable time"?  The most concise answer I can give you
is "we don't know".  An answer that would make you feel more
comfortable is that we believe that factoring a 1024-bit key using
GNFS is about 300,000 times harder than factoring a 512-bit key using
GNFS.

This doesn't take into account increase in computer power.  If you
take into account increase in technology at the current rate, doubling
every 18 months, then a 1024-bit key should be breakable in about 100
years.

However this doesn't take into account increases in algorithms.  There
is no way to predict the discovery of a new factoring algorithm.  In
addition, there is no way to predict a computational discovery which
might increase the base technology faster than the current trend.

To get back to your question: If smoe [sic] organization spent 10
billions [sic] of dollars on a cracking machine, would it be possible
to crack the keys in a reasonable time?

Well, lets assume a P100 is 50 MIPS and costs $500.  Then the $10B
would purchase 20 million machines.  Discounting the storage
requirements (factoring a number this large will probably require on
the order of hundreds of GBs of storage) and end-time processing power
(unknown) required to factor a 1024-bit number, this set of machines
would provide "enough" relations for a 1024-bit number in about 1.5
years per key.

- -derek

PS: These are napkin-style numbers, and I'm making a lot of
assumptions here...  I assume no responsibility if you use these
numbers and they are wrong.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface

iQBuAwUBMgEcrTh0K1zBsGrxAQGNaALEDEtO8/pXZPp134SBcjUqD3NO2P3siirR
8a4pA6S15fwtVDrl2ZWeZb2XL65hbhcWpZ2s6Q3eaQOvFPOiytLtfcujUFV7ef+i
9zJKgUlUFMkOP9fmhZdjZXA=
=gPv4
-----END PGP SIGNATURE-----