 |
|
| Science Forum Index » Cryptography Forum » Rendering prediction of congruential random number... |
|
Page 1 of 1 |
|
| Author |
Message |
| Mok-Kong Shen... |
 Posted: Fri Oct 16, 2009 4:22 pm |
|
|
|
Guest
|
[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 |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Tue Nov 03, 2009 7:43 am |
|
|
|
Guest
|
[Addendum]
I suggested years ago a scheme to employ a compound PRNG, consisting
of a large number of constituent PRNGs that are pseudo-randomly
activated to provide the output. This should also render the
prediction hard, since the analyst doesn't know from which constituent
PRNG each segment of the output stream stems. In that scheme, each
constituent PRNG, when it is its turn to work, generates two numbers,
one serves as the output of the compound PRNG, while the other
is used to determine the index of the successor constituent PRNG
in the pool. Since this second number is only partly used (e.g. only
8 bits, if there are 256 constituent PRNGs), the rest of the bits could
be used for rotation of the compound PRNG output and also for rotation
of the plaintext word when doing XOR-ing in the encryption process.
(A convienient way to obtain a compound PRNG is to employ a
master PRNG that generates the constituent PRNGs. The master PRNG
could e.g. be a high degree polynomial congruential PRNG, whose
coefficients consitute the (arbitrarily long) key, while the
constituent PRNGs could be low degree (e.g. 2nd degree) congruential
PRNGs in order to obtain better computing efficiency.)
If one has two bit streams from two sources, then XOR-ing these
(preferably after random rotation of one of them in unit of words)
evidently should substantially reduce the predictability by the analyst.
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Dec 07, 2009 2:15 am
|
|