The birdhouse principle says that if one is trying to put n+1 birds in n bird-houses, then you must put 2 birds in at least one bird-house. Since there is a limited number of key IDs and supposedly a greater number of circulating keys, then there must be two keys which share the same ID.
First, I'll nitpick a little - you must put at least two pigeons in at least one hole, you don't necessarily have a hole with exactly two pigeons :-)
Now, to something a bit more interesting. It is true that if the keyspace is bigger than the id-space then you will necessarily have several keys sharing the same key-id, *but* in practice you can make it so that the id-space is much, much bigger than the actual number of keys out there making it statistically unlikely for two existing keys to have the same key-id. This is the case with, for example, good cryptographic hashes - although there obviously exist two (much more than two) messages with the same md5 hash, not only it is highly unlikely to happen for any two given messages, but it is also infeasible (with current mathematical/algorithmical knowledge) to find two such messages.
Disclaimer: I don't actually understand anything in cryptology - these are just things I read (or worse, thought of myself), so if I'm wrong, please educate, but don't flame :-)
Alexander (aka Sasha) Maryanovsky.
At 21:50 01.08.2003 +0300, Shlomi Fish wrote:
On Fri, 1 Aug 2003, Shaul Karl wrote:
> On Fri, Aug 01, 2003 at 08:17:53PM +0300, Orna Agmon wrote: > > > > The KEY ID cannot be unique. It can be well distributed, such thatkeys > > that vary a little have a very different KEY ID, but since it holds a lot > > less information than the actual key, there is no way of it being uniqe. > > Bird house principle (? - SHOVACH YONIM). > > > > > What is the birdhouse principle and how it gets demonstrated in the > KEY ID space?
The birdhouse principle says that if one is trying to put n+1 birds in n bird-houses, then you must put 2 birds in at least one bird-house. Since there is a limited number of key IDs and supposedly a greater number of circulating keys, then there must be two keys which share the same ID.
Regards,
Shlomi Fish
> -- > > Shaul Karl, shaul @ actcom . net . il >
---------------------------------------------------------------------- Shlomi Fish [EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/
There's no point in keeping an idea to yourself since there's a 10 to 1 chance that somebody already has it and will share it before you.
================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
