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 webpagehttp://www.ciphersbyritter.com/#BBMTech) 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)
with
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?
.