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 :-)
The exact phrase of the pigeonhole principle is that if n pigeons try to enter a pigeonhouse with m holes, there will be at least one hole with at least n/m pigeons. This means that if 1000 pigeons try to enter a pigeonhouse with 30 holes, there will be at least one hole with at least 34 (1000/30=33 1/3) pigeons. Hence, whenever the mapped space is bigger than the mapee space, a colision is inevitable.
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 relevant to hash arrays. The ratio between the size of the mapping (how many elements need to be mapped) and the size of the has is called alpha, and an optimal value is considered 0.8. It is totally irrelevant to this problem, as our problem is not the O(1) retrival, but identity verification.
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.
The point about cryptographic hashes is that, while it is possible, and in fact inevitable, that two messages will have the same hash, it is very very difficult to actually find such two messages. If any two messages are fine, then the birthday paradox applies, and I can lessen the difficulty.
In this case, the fingerprints are used to authenticate the key. As such, the system only breaks when both fingerprint AND name are the same. If Orna's key has the same fingerprint as my key, that does not break the system. Noone is likely to think that a key labled "Orna Agmon" belongs to me.
This means that the system only breaks when someone DELIBERITLY generates a key with the same fingerprint. Cryptographic hashes mean that this is extremely unlikely to happen (and the birthday paradox doesn't apply, as Melica is aiming for a static target).
I'll just add that while the keyspace is 1024 bits, the actual keys in that space are rather sparse. This is also the reason that a 1024 asymetrical key is considered about as secure as a 128bit symmetrical key (all 128 bits are valid symetrical keys). This also reduces the chances of collisions considerably. I find it hard to believe that there are no collisions at all, but if you generate all possible 1024 bit asymetrical bits, you are still unlikely to have more than a few collisions all told.
Shachar
-- Shachar Shemesh Open Source integration consultant Home page & resume - http://www.shemesh.biz/
================================================================= 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]
