[25656] in cryptography@c2.net mail archive
Re: the meaning of linearity, was Re: picking a hash function to
daemon@ATHENA.MIT.EDU (leichter_jerrold@emc.com)
Mon May 15 17:34:11 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: leichter_jerrold@emc.com
To: solinym@gmail.com
Cc: cryptography@metzdowd.com
Date: Mon, 15 May 2006 15:12:47 -0400
| > - Stream ciphers (additive)
|
| This reminds me, when people talk about linearity with regard to a
| function, for example CRCs, exactly what sense of the word do they
| mean? I can understand f(x) = ax + b being linear, but how exactly
| does XOR get involved, and are there +-linear functions and xor-linear
| functions? Are they disjoint? etc.
XOR is the same as addition mod 2. The integers mod 2 form a field
with XOR as the addition operation and integer multiplication (mod 2,
though that has no effect in this case) as the multiplication.
If you think of a stream of n bits as a member of the vector space
of dimension n over the integers mod 2 treated as a field, then
adding two of these - the fundamental linear operation - is XOR'ing
them bit by bit.
The thing I've always wondered about stream ciphers is why we only
talk about linear ones. A stream cipher is fundamentally constructed
of two things: A stream of bits (alleged to be unpredictable) as
long as the plaintext; and a combining function that takes one
plaintext bit and one stream bit and produces a ciphertext bit.
The combining function has to conserve information. If you only
combine single bits, there are only two possible functions: XOR
and the complement of XOR. But consider RC4: It actually generates
a byte at a time. We just choose to use that byte as a vector of
8 bits. For plaintexts that are multiples of 8 bits long - just
about everything these days - there are many possible combining
functions. Most aren't even close to linear.
Other than post by a guy - Terry someone or another - on sci.crypt
a number of years ago - I've never seen any work in this direction.
Is there stuff I'm not aware of?
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
