Prev: Looking for Participnts
Next: Newton-Raphson division vs. Montgomery reduction
From: Mok-Kong Shen on 16 Oct 2009 18:22
[also posted to sci.crypt.random-numbers]

Hi,

Linear congruential generators were first broken by J. Boyar. She
published an algorithm for inferring sequences produced by a
linear congruential generator missing low-order bits. Later she
also broke quadratic and cubic generators. Other researchers
continued work in this direction to cover more general cases.

However, common in such work is the (natural) assumption that
the higher order bits (in a computer word) that form the basis
for prediction are available as such as they are sequentially
generated by the generator under investigation. If this assumption
is violated, then it will logically evidently follow that the
said prediction would no longer succeed.

There is in my humble view a rather simple way to cause the said
assumption not to hold in practice, though at some cost. Consider
the sequence x_i generated by the congruential generator

x_i = f( x_(i-1) ) mod 232

Denote by S(w,b) the result of circular rotation of the bits of
the computer word w by a 5 bit value b. Let now, for example,

b_k = value of lower order 5 bits of x_k

y_j = S( x_(2*j), b_(2j-1) )

as the final output of the generator, i.e. emitting only the even
numbered elements of X_i to the outside world after it has been
circularly rotated by the value of the lower order 5 bits of
the immediately preceding odd numbered element of the sequence. Now
the analyst has in hand the sequence y_j, but the higher order bits
of y_j are in general not the higher order bits that are generated
by the given congruential generator due to the random circular
rotation of the computer word we have effected.

Of course, with the scheme described above the computing cost for
the same volume of output is doubled. Some economy could however
be achieved e.g. by using one element of the x sequence to circularly
rotate 6 following elements to be output (6*5 = 30 < 32).

We could even do something more, if the output is to xor with
the plaintext given in computer words to do stream encryption. We
could namely use 5 additional bits (from the element that provides
the rotation of x) to circularly rotate the plaintext word before
xoring. This would evidently render the anylyst's work even harder.

I should be grateful for comments and critiques.

Thanks,

M. K. Shen
 | 
Pages: 1
Prev: Looking for Participnts
Next: Newton-Raphson division vs. Montgomery reduction