Re: Help me sort though some complex math

On Apr 10, 1:54 pm, Ilmari Karonen <usen...@xxxxxxxxxxxxxx> wrote:
On 10.04.2008, grocery_stocker <cdal...@xxxxxxxxx> wrote:





The questions stem from the following URL

http://64.233.167.104/search?q=cache:R1ERKgiy5L8J:www.phrack.org/issu....

 [snip]

Such an operation on bytes is called linear mixing and its goal is
to provide the diffusion of information (according to the well known
Shannon theory). Mathematically, it's no more than a linear map
between two GF(2) vector spaces of dimension 128. Indeed, if U and V
are vectors over GF(2) representing respectively the input and the
output of rbytechain() then V = M.U where M is a 128x128 matrix over
GF(2) of the linear map where coefficients of the matrix are trivial
to find.

What is a liner map between two GF(2) vector spaces of 128 dimensions?
Actually, I also don't see how they get 128 dimensions.

Perhaps some clarification of more basic concepts first is in order:

The elements of GF(2) are single bits, with addition corresponding to
the XOR operation (and multiplication to AND).  Another way of looking
at it is to say that all arithmetic in GF(2) is done modulo 2.

A 128-dimensional vector over GF(2) is simply a 128-bit bitstring,
again with addition corresponding to (bitwise) XOR.

A linear map g: GF(2)^128 -> GF(2)^128 is a function mapping 128-bit
bitstrings to other 128-bit bitstrings which is compatible with vector
addition (i.e. g(x) XOR g(y) = g(x XOR y)) and scalar multiplication
(which, for vectors over GF(2), simply requires that g(0) = 0 where 0
is a string of 128 zero bits and is trivially true if the additivity
condition is satisfied).  It turns out that all such functions can be
represented by multiplication with some 128x128-bit matrix, using the
ordinary definition of matrix multiplication and the GF(2) definitions
of scalar arithmetic (i.e. addition = XOR, multiplication = AND).

More concretely: Let x = <x_1, x_2, ..., x_k> be a k-bit bitstring,
and let M = [M_1, M_2, ..., M_k] be a matrix consisting of k n-bit
bitstrings.  Then y = M * x is an n-bit bitstring given by XORing
together all those bitstrings M_i (where 1 <= i <= k) for which the
corresponding bit x_i is one.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.- Hide quoted text -

- Show quoted text -


Okay, let's try this one more time.

What would be the matrix consisting of k n-bit bitstrings in chise
case?
.

Relevant Pages

  • Re: Help me sort though some complex math
    ... GFof the linear map where coefficients of the matrix are trivial ... again with addition corresponding to XOR. ... bitstrings to other 128-bit bitstrings which is compatible with vector ... 2)How is the GFvector space different than a regular vector space? ...
    (sci.math)
  • Re: Help me sort though some complex math
    ... GFof the linear map where coefficients of the matrix are trivial ... again with addition corresponding to XOR. ... bitstrings to other 128-bit bitstrings which is compatible with vector ... 2)How is the GFvector space different than a regular vector space? ...
    (sci.math)
  • Re: Help me sort though some complex math
    ... Such an operation on bytes is called linear mixing and its goal is ... What is a liner map between two GFvector spaces of 128 dimensions? ... again with addition corresponding to XOR. ... bitstrings to other 128-bit bitstrings which is compatible with vector ...
    (sci.math)
  • Re: Help me sort though some complex math
    ... bitstrings to other 128-bit bitstrings which is compatible with vector ... You mean the one for the function described in your original post? ...
    (sci.math)
  • Re: Understanding the quotient ring nomenclature
    ... addition and multiplication operations on bitstrings? ... will be component-wise XOR; i.e. we find the XOR of two bitstrings by ... The partial products work out as ...
    (sci.math)
Loading