On 5/18/06, Travis H. <[EMAIL PROTECTED]> wrote:
... There's 255 "other" permutations, so the chance that there is at least one k' such that f_k'(x)=y is 255/256 = 99.6%. The chance that there is exactly one such k' is sampling with replacement and if I am not mistaken P(|K|=1) = (255/256)^255 = 0.36. Along those same lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks like the expected number of equivocating keys is very small.
Oops, I left off a term in the recurrence. P(|K|=2) = (255/256)^253 * ((254*255)/2)/(256^2) = 0.18 So the expected number of equivocating keys, given one byte of known plaintext, is a bit under two. -- "Curiousity killed the cat, but for a while I was a suspect" -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -><- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]