trough@ihuxi.UUCP (Chris Scussel) (01/03/85)
Suppose an encryption algorithm encodes an n byte string as another n byte string, using an m byte key. Further, suppose that the 2**(8*m) encodings are distributed "uniformly" over the n byte output space (uniform as in "random uniform", since the algorithm is evidently too complicated to analyze). Now, how likely is it that two keys yield the same encoded text? The Birthday Paradox (you only need about 24 people to have a 50% chance of shared birthdays) applies here; I don't have the exact relation, but the 50% probability point is roughly proportional to the square root of the size of the space being sampled. Thus, there should be 50% chance of duplicate keys if the key length (m) is about half of the text length (n). I'd be interested if anyone can reproduce the math here accurately. Chris Scussel AT&T Bell Labs