the meaning of linearity, was Re: picking a hash function to be encrypted

On 5/18/06, Travis H. <solinymgmail.com> 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.li
ghtconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098
0C55 1484

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com