# Re: Nonlinear combination of streams

*From*: Maaartin <grajcar1@xxxxxxxxx>*Date*: Sat, 13 Mar 2010 12:16:52 -0800 (PST)

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?

.

**Follow-Ups**:**Re: Nonlinear combination of streams***From:*Maaartin

**References**:**Nonlinear combination of streams***From:*Mok-Kong Shen

**Re: Nonlinear combination of streams***From:*Tom St Denis

- Prev by Date:
**Re: Enormous speed difference between C and ASM implementations of crypto algorithm** - Next by Date:
**Re: What do I need to know to design a cryptosystem?** - Previous by thread:
**Re: Nonlinear combination of streams** - Next by thread:
**Re: Nonlinear combination of streams** - Index(es):