L10 Stream cipher systems

3.8 MEASURE OF RUNDOMNESS:
3.9.1 DEFINITION:
Run: sequence of identical bits (0 or 1) Ex.01110000111
Runs are 0,111, 0000, 111
Gap: runs of zeroes
1000011 contain the gap 0000
Block: runs of ones
1111001110 contain blocks 1111,111 For with period P , Sm + p = Sm
Auto correlation function:
For any constant d, if we compare the sequence of S with Sd (after shifting d displacement), then Auto correlation function C(t) = (A - D) / P Where :
A = no. Of identical bits.
P = period of the sequence
D = period of different bits
d = displacement 0 <= d < p
? RANDOMNESS CHARACTERISTICS:
1. If p is even then ones equal zeros, other wise they differ by one only.
2. 1/2 of runs with length of 1 , 1/4 of runs with length of 2 , generally l / 2i = i.
3. Auto correlation function (for d < > 0 out of phase) has constant value. Where d is the displacement.
1. FREQUENCY TEST:
used to ensure that there is roughly the same number of O s and 1 s using the following formula:
X2 =(n0 – n1)2 / n
X2 = 0 if n0 = n1
For good sequence 0 < X2 < 3.84
Lec 10 : Data Security Stream Cipher Systems
2
2. SERIAL TEST:
The serial test is used to ensure that the transition probabilities are reasonable. This will give as some level of confidence that each bit is independent of its predecessor suppose .01 occurs n 01, 10 occurs n0, 00 occurs n00…and 11 occurs n11 times.
N01+n10=n0 or n0-1 , n10+n11 = n01 or n1-1 and
N10 + N01 + N00 + N11 = N-1 AND
X2 = 4/n - 1 ?(nij)2 - 2/n ?(ni)2 + 1 For good sequence X2 <= 5.99.
Ideally we wont:
n01 = n10 = n00 = n11 ? n-1/4
3. POKER TEST:
For any binary sequence of length m, there are 2^ different possibilities. In this test we partition our sequence into blocks of size m (sequence of ones), and then we count the frequency of each type of sections of length m in the sequence. If the frequencies are f0, f1,.. fm-1 We compute:
X2 = 2m / F ? (Xi)2 / mi) – F
Where F = ? fi = n/m
4. AUTO CORRELATION TEST:
For a given sequence of n bits S1,..Sn then
A (d) = ?ai ai+d 0 <= d <= n-1
A (o) =?ai = ni
If the sequence has ni of zeros and n1 of ones then
?= n12 (n-d) / n2
The test will pass if
X2 = (A(d)- ?)2 /?
X2 <=3.841 for all values of d
Lec 10 : Data Security Stream Cipher Systems
3
5. RUNS TEST:
Devide the sequence into blocks and gaps, let r0i be the number of gaps of length i
and r1i be the number of blocks of length i. If r0 and r1 are number of gaps and blocks respectively then:
r0 =