# Secure Systems

### Contributed by Bear Giles

Secure systems are systems that could survive intense
radiation levels, broken hardware, etc.
Here's a simple example: assume you need a "fair coin toss"
for a nondeterministic algorithm, but your hardware random
generator is on the fritz and is no longer statistically
random. You considered testing the RNG hardware and correcting
for the bias, but the bias "drifts" too much for that approach
(but too slowly for you to treat the results as random.)

Can you get a good "fair coin toss" from this hardware RNG?
The answer is **yes**. Instead of reading each bit as it
comes from the RNG, you look at pairs of bits:

00 --> discard and retry
01 --> 1
10 --> 0
11 --> discard and retry

If the odds of getting a "0" are p and the events are
independent, you can quickly see that the relative odds
of each possibility are p^2, p(1-p), (1-p)p and (1-p)^2.
No matter what "p" is, the odds of getting a "0" or "1"
out of the system is the same!

Likewise it's possible to create a fair three-sided coin
given an unfair two-sided coin:

000 --> discard and retry
111 --> discard and retry
100 --> 0 (1-p)p^2
011 p(1-p)^2
010 --> 1
101
001 --> 2
110

The idea is you collect triplets of bits until you get a
set where there is an "oddball". The position of the
oddball gives you the result. The figures to the right
show that the odds of the three choices are identical,
if the coin tosses are independent.

Return to the Library