hi,
Using Transition Mappings to De-Skew
Randomness Recommendations for Security
RFC 1750
An extract from it.....
Another technique, originally due to von Neumann
[VON NEUMANN], is to
examine a bit stream as a sequence of
non-overlapping pair
| pair | probability
|
| 00 | (0.5 - e)^2 = 0.25 - e + e^2 |
| 01 | (0.5 - e)*(0.5 + e) = 0.25 - e^2 |
| 10 | (0.5 + e)*(0.5 - e) = 0.25 - e^2 |
| 11 | (0.5 + e)^2 = 0.25 + e + e^2 |
This technique will completely eliminate any bias but
at the expense
of taking an indeterminate number of input bits for
any particular
desired number of output bits. The probability of
any particular
pair being discarded is 0.5 + 2e^2 so the expected
number of input
bits to produce X output bits is X/(0.25 - e^2).
Eastlake, Crocker & Schiller
[Page 12]
RFC 1750 Randomness Recommendations for
Security December 1994
This technique assumes that the bits are from a
stream where each bit
has the same probability of being a 0 or 1 as any
other bit in the
stream and that bits are not correlated, i.e., that
the bits are
identical independent distributions. If alternate
bits were from two
correlated sources, for example, the above analysis
breaks down.
The above technique also provides another
illustration of how a
simple statistical analysis can mislead if one is
not always on the
lookout for patterns that could be exploited by an
adversary. If the
algorithm were mis-read slightly so that
overlapping successive bits
pairs were used instead of non-overlapping pairs,
the statistical
analysis given is the same; however, instead of
provided an unbiased
uncorrelated series of random 1's and 0's, it
instead produces a
totally predictable sequence of exactly alternating
1's and 0's.
A few doubts regarding the above.
Another technique, originally due to von Neumann [VON
NEUMANN], is to
examine a bit stream as a sequence of
non-overlapping pairs
What do they mean by bit stream as a sequence of
non-over lapping pairs?
Also isn't idea-1 of my earlier post "Two idea's for
random number generators" very similar to this?
www.neo.ircsuper.net
Wouldn't the problem in idea 1 be solved if I choose
a bit stream as a sequence of non-over lapping pairs?
If we choose bits that are from a stream where each
bit has the same probability of being a 0 or 1 as any
other bit in the stream and that bits are not
correlated, i.e., that the bits are identical
independent distributions.
Would n't idea 1 work?
Regards Data.
__________________________________________________
Do You Yahoo!?
Yahoo! Games - play chess, backgammon, pool and more
http://games.yahoo.com/
