W2 Flashcards
(18 cards)
What is the purpose of Feedback Shift Registers (FSRs)?
What happens to the bits in the registers when feedback comes in from one side?
When do FSRs repeat themselves?
If the state has length n, after how many steps does the sequence HAVE to repeat?
Generating a pseudo-random stream of binary for use in the XOR cipher
All bits are shifted to the opposite side and the bit most on the other side is outputted.
When we’ve reached the same state again
2^n
When is a sequence periodic?
What are the first i_0 steps called?
What is the minimal r called?
When there exist r>0, i0 such that s_i = s_i+r for all i >= i0
The pre-period
The period
What is l if S_i = S_i+l for all i?
What is the largest period we can get for an LSFR of state length n?
A multiple of the period
2^n - 1
How can S_i+1 be represented in terms of S_i and a n by n matrix C?
How is the structure of C?
What is the order of C?
What is the order equivalent to in terms of C?
In what case does the order always exist?
S_i+1 = S_i * C
First n-1 columns cover the shift, and the last column covers the computation of the new bit.
The smallest l > 0 such that C^l = I, if such an l exists
Longest period that the LFSR can produce
If c_0 = 1
What is a primitive feedback polynomial?
What two conditions does it have?
A polynomial that ensures the LFSR generates a maximal-length sequence
Cannot be factored (irreducible), and produces a sequence with maximal period of 2^(n-1)
What is the relation between the period of all sequences and the order of C, l?
Is this relation dependent on the starting state?
Period of all sequences divides the order of C
Nope
How is the characteristic polynomial defined?
x^n - c_n-1 * x^n-1 - c_n-2 * x^n-2 - … - c_1 * x - c_0
What is a limitation of LFSRs as a standalone cipher?
What is their main advantage?
The state of an LFSR can be determined entirely by the feedback polynomial and the initial state (IV).
Thus, if the attacker knows the IV and can observe just n-1 additional output bits, it can reconstruct the entire state of the LFSR.
Valuable in larger constructions due to well-understood periodic properties
For what starting state is the longest period of an LFSR (ord(c)) be reached?
S_0 = (0,0,0,…,0,1) for n-1 zeros
How does Rabin’s irreducibility test work?
A poly f(x) of degree n in F_q[x] is irreducible if and only if:
- x^(q^n) is equivalent to x mod f(x)
- gcd( x^(q^d) - x , f) = 1 for all divisors d of n
where n = deg(f)
What is the order of a polynomial q(x)?
Smallest r>0 with x^r equivalent to 1 (mod q(x))
What is the relation between C and P(x) if P(x) is irreducible?
ord(C) = ord(P)
When is polynomial f called primitive?
When it is irreducible and has order 2^(deg(f)) - 1
How can P(x) be written in terms of C?
What is P(C) equal to?
P(x) = det(xI - C)
0
If P(x) is primitive, what are the possible periods?
If P(x) is irreducible but not primitive what periods do we get?
2^n-1 and 1
2^(n-1) / ord(P) disjoint sequences of periods ord(P) and 1
If you add two LFSRs of max periods p and r, what will the period of this addition be?
If the first LFSR has periods p=2^(m)-1 and 1, and the second LFSR has periods r = 2^(n)-1 and 1, then:
lcm(p,r)
Their sum has gcd(p,r) sequences of period lcm(p,r) and sequences of period p,r and 1.
These add up to gcd(p,r) * lcm(p,r) + p + r + 1 = p* r + p + r+ 1 = (p+1)(r+1) = 2^m ^2 *n, accounting for all 2^(m+n) steps
Is it useful to combine identical LFSRs?
No
If one or both LFSRs being combined do not have maximal periods we expect, i.e., p=2^m - 1 and r = 2^n - 1, then there will be the following sequences:
gcd(p,r) sequences of lcm(p,r)
sequences of period p,r, 1
sequences from combinations of the other parts
