[25917] in cryptography@c2.net mail archive
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
daemon@ATHENA.MIT.EDU (Travis H.)
Thu May 18 09:20:12 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 18 May 2006 04:14:31 -0500
From: "Travis H." <solinym@gmail.com>
To: "Kuehn, Ulrich" <Ulrich.Kuehn@telekom.de>
Cc: leichter_jerrold@emc.com, cryptography@metzdowd.com
In-Reply-To: <490A625B3DFD8A45B4A7F1ABA8DEA8B401C308C1@S4DE9JSAAMU.ost.t-com.de>
On 5/17/06, Kuehn, Ulrich <Ulrich.Kuehn@telekom.de> wrote:
> Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case.
I'm a little rusty but I'll give it a shot.
Well we have a byte x and a mapping f_k(x) = y, with f selected at
random (for now I'll assume with replacement since 256 << 256!) from
the set of all permutations, x and y from 0..255. The questions is
what fraction of permutations have f_k(x) = y, I think the answer is
1/256. 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.
I suspect that's why Terry Ritter's "Dynamic Substitution" algorithms,
which are meant to replace XOR combiner in stream ciphers, maintain
state.
--
"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 majordomo@metzdowd.com
