source: Project Repository/trunk/NOTES.txt @ 31

Revision 31, 2.0 KB checked in by pchapin, 2 years ago (diff)

Some cosmetic updates to various informational files.

Line 
1
2On Testing Randomness
3---------------------
4
5+ RFC-1750
6
7+ Knuth, "The Art of Computer Programming" (volume 2)
8
9+ NIST publication 800-22
10
11+ FIPS publication 140-2
12
13
14Different Kinds of Randomness
15-----------------------------
16
17+ Chaitin-Kolmogorov randomness (Algorithmic randomness), defined in terms of computational
18  models. A string of bits is random iff it is shorter than any program that can produce it.
19
20+ Statistical randomness, defined as having no recognizable patterns or regularities (in the
21  long run).
22
23+ "True" randomness, defined as being unpredictable.
24
25How are these different definitions related?
26
27
28Bias Removal
29------------
30
31The output of the RNG will, most likely, contain bias (more 1s than 0s or visa-versa). The bias
32can be removed with hardware filtering or in software after the fact. Hardware bias removal
33methods include: feeding back the output to adjust the generator, using two generators with
34different mechanisms, beating the output against an uncorrelated clock, etc. Software bias
35removal methods include: von Neumann decorrelation, XOR with output of cryptographically strong
36PRNG, XOR two correlated bit streams together (see "piling-up" lemma), use a secure hash on the
37bits (little theoretical support?)
38
39von Neumann decorrelation:
40  00, 11 -> throw away
41  10     -> 1
42  01     -> 0
43
44This forces 50% occurance of 1 (and, of course, 0) bits , but it throws away 75% of the bits.
45Alternatively one might XOR adjacent bits together. This only throws away 50% of the bits.
46
47Both hardware and software "whitening" techniques should be used. Statistical tests on the
48device should probably be done before software bias removal so that the tests can better observe
49changes in the underlying hardware.
50
51
52Security Analysis
53-----------------
54
55Since this system will be used in security sensitive applications it may make sense to do a
56careful security review of the software and system design. It would be especially nice to use
57some formal methods in that review, but that may be too time consuming for the first version.
58
Note: See TracBrowser for help on using the repository browser.