Re: Nonlinear combination of streams

On Mar 13, 12:23 am, Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:
Terry Ritter favours to use orthogonal Latin squares (see his webpage for combination. However, in my
humble view, that scheme is designed to be "practically" used for
combining streams in units of 8 bits. For operating on larger units,
there would be implementation difficulties/inconveniences.

Not really, it can be done using something like this
X ^= Y; Y ^= f(X)
f(X) = (X<<1) ^ ((X>>31) & C)
where ">>" denotes a signed shift and C is a suitable constant, so you
need about 8 machine instructions. Sure, it's linear, but...

On Mar 13, 2:18 pm, Tom St Denis <t...@xxxxxxx> wrote:
On Mar 12, 6:23 pm, Mok-Kong Shen <mok-kong.s...@xxxxxxxxxxx> wrote:

Sometime ago, I suggested to combine two computer words X and Y by the
formula Z = X*Y + X + Y (mod 2^32 for 32-bit words). In discussions

The problem is that's not really non-linear,

Could you pls elaborate on this? I suppose he means to multiply two
data words, so it can't be linear.

nor is multiplication modulo 2^32 a BBM function.

Moreover, it's not bijective (in either argument), so he looses
entropy. The function
(X, Y) -> (2*X*Y + X + Y, Y)
is bijective, but obviously not BBM (and I don't believe it could be
made to BBM).

You could do something multiplication in
a field with a prime of the form 2^k + 1 [e.g. p=257] then just
promote all values into 1..256, then multiplication is a BBM,

How? The multiplication returns one result, but you need two, don't
you? Ritter writes:
"Balanced Block Mixing: An orthogonal pair of Latin squares which
reversibly mix two input blocks or values of some power-of-2 size into
two output blocks of the original size.".
Or do you mean computing
(X, Y) -> (a*X+b*Y, c*X+d*Y)
in a GF where a, b, c, d, and a*d-b*c are all co-prime to the
characteristic of the field? In the latter case, it's clear.

but it's still linear.

BTW nonlinear combiners exist, for example the stop-gap generator.
They're also weak.  Of course you'd know this if you did even remedial
reading on the subject....

I haven't found anything about the stop-gap generator, could you
provide me a pointer or some better keywords for google?