[Cryptography] An interesting little pseudorandom number generator

[Ray Dillinger]

On 8/2/21 3:34 PM, John Kelsey wrote:
> The multiply step is non-invertible and so loses entropy.  Specifically, if the low k bits of either word are zero, the low k bits of the output are zero, which seems like a bad property for this generator.

You are right.  I took the advice of people who said to use
multiplication instead of just addition,
without checking the literature to discover the caveats.  And on
searching, I find: 

Use of multiplication means either

  1) odd numbers must be used to initialize that generator.
or
  2) the multiplication must be done modulo a prime.

The first produces an always-odd output, which is also a bad property
for this generator.  I could build the odd-sequence for that LFG into
the initializer without changing the generator code, but I don't want
the always-odd output.  But the always-odd output is nowhere near as bad
as if I'd remained ignorant and initialized the generator wrong so it
produced a 'zero sequence' output.

The second introduces an integer division by a prime, which is a
performance hit and would cause a very slight bias toward zero in the
top bit.  That's much less bad than always-odd.  In this case the
"obvious" prime would be 2^64-59, the highest prime representable in 64
bits.  The performance hit is serious, but has nearly perfect
information spread from all bits of both input to all bits of the result.

> I think you might want to put a rotate in there somewhere so high bits can affect low
> bits.  And maybe have your multiply be with an odd constant with balanced Hamming weight or something.  (Will integer multiply have constant time on most modern processors?)

Using an operation (multiply by a constant, rotate, etc) that hasn't
been studied in the context of LFGs would cause me to worry about
accidentally getting a function that causes the LFG to evolve into a
state that repeats on a very short period (like the all-zeros example
above) or gives a wrong distribution (like the always-odd example above).

Add, subtract, multiply, and XOR are all known to work.  The first two
have a "one of the initial sequence must be odd" requirement.  Multiply
has an "all of the initial sequence must be odd" requirement.  XOR has a
"For each bit at least one of the initial sequence must be nonzero in
that bit" requirement.

Any of the above, preceded or followed by a rotate or complement ... 
ought to work but I will have to expend sweat making sure of it.

I'm going to look into the stability of LFGs using some 'multiply and
complement' or 'shift and multiply' operations.


Next revision will use either
   multiplication modulo 2^64-59, or
   complemented multiplication (A=(~B) * C) or
   multiplication with rotate (A = B>>N * C>>N) or
    something like that.....

Depending on what effects these different operations have on CPU cost
and LFG period/stability.

                    Bear