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

Revision 26, 2.1 KB checked in by pchapin, 6 years ago (diff)

This is a demonstration commit done in class.

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