[25684] in cryptography@c2.net mail archive
Re: the meaning of linearity, was Re: picking a hash function to
daemon@ATHENA.MIT.EDU (James Muir)
Mon May 15 20:57:47 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Mon, 15 May 2006 16:54:49 -0400
From: James Muir <jamuir@scs.carleton.ca>
To: "Travis H." <solinym@gmail.com>
Cc: Cryptography <cryptography@metzdowd.com>
In-Reply-To: <d4f1333a0605141739r110a2d99v87d75546cc99376@mail.gmail.com>
Travis H. wrote:
>> - 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.
If you have a linear algebra book handy, look up "linear transformation".
Briefly, a function T from a vector space V to another vector space W
(where V and W are defined over the same field) is called a
linear transformation if it satisfies
i) T(u +_V v) = T(u) +_W T(v)
ii) T(c *_V u) = c *_V T(u)
iii) T(0_V) = 0_W
CRC is a linear transformation because
CRC(u + v) = CRC(u)+CRC(v).
-James
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
