From: Bill Stewart <stewarts@ix.netcom.com>
Date: Fri, 6 Oct 95 00:35:14 PDT
To: cypherpunks@toad.com
Subject: Re: subjective names and MITM
Message-ID: <199510060735.AAA22195@ix4.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 10:24 PM 10/5/95 -0400, Adam Shostack <adam@homeport.org> wrote:
>	The key does indeed have a high likelihood of being unique,
>but dealing with 1024 bit identifiers could strain database systems,
>especially when 100 well chosen bits would be than enough.

If everybody in the world has a 1024-bit key, that's 750 GB;
that's not bad at all by the time everybody in the world would have one,
and you could do MD5s in about 100 GB, which is a little more convenient.
Today, for 750 GB, you'd probably have tape in your system, or optical jukebox.
But not everybody has one; on the other hand, I suppose individuals
in well-heeled countries might end up with dozens of their own.

On the other hand, the number of 1024-bit primes is something like
2^1023/log(2^1024) (if I remember right), or roughly 2^1013.
The probability of two independent uniformly distributed primes
matching is about 2^1023/2^32, which is still an astoundingly
mindbogglingly LARGE number.  If you've got 1024 bits of entropy
in your input process, there will not _be_ any matches.
(If people insist on using sources of randomness like clocks or
user names, the chances are a lot higher....)

Now, for 128-bit hashes, whether it's MD5 or just the near-bottom 128 key bits,
by the time you get 2^64 of them together, you've got a 50% chance of a match.
Not a problem, since you'll not likely need that many, even for the 2^33 people
in the world.  Still not a problem.
#---
#                                       Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---