Understanding Stream Cipher: Initialization Vector, Feedback Coefficients, and LFSR Implementation

ANSWERS
1)
(a) What is the initialization vector used? (5 Pts.)
Answer
Let A1 represents the new initial of SRr after one shift, s.t.
A1=A0M=(a-1,a-2,...,a-r)
( c1 1 ⋯ 0
c2 0 ⋯ 0
⋮ ⋮ ⋮ ⋮
cr 0 ⋯ 0 )=(∑
j=1
r
a− j c j
,a-1,...,a1-r).
In general,
Ai=Ai-1M, i=0,1,2,... ...(2)
Equation (2) can be considered as a recurrence relation, so we have:
Ai=Ai-1M=Ai-2M2=...=A0Mi ...(3)
The matrix Mi represents the phase i of SRr, equations (2,3) can be considered as a
Markov Process s.t. A0 is the initial probability distribution, Ai represents probability distribution
and M be the transition matrix (Golomb, 1982).
Notice that:
M2=[C1C0|Irr-2] and so on until get Mi=[Ci-1...C0|Irr-i], where 1i<r.
When CP=C0 then MP+1=M.
Assuming as you specified that X1X1 is 8181 and X2X2 is 6565.
X1||...||XnX1||...||Xn is your key stream in bits.
(b) What are the feedback coefficients of the LFSR? (10 Pts.)
Answer The Berlekamp-Massey algorithm is an iterative algorithm that solves the
following problem. Given a sequence s0,s1,s2,...s0,s1,s2,... of elements of a field,
find the shortest linear feedback shift register (LFSR) that generates this sequence.

Here, LFSR is a linear array of nn elements with initial value $$(s_0, \quad s_1,\quad \
ldots, \quad s_{n-2}, .. Berlekamp-Massey can be used if you do not know the feedback
polynomial and you do not know the initial fill. If you do know the feedback polynomial
but do not know the initial fill, you can use other simpler methods. F
(b) Write down the recurrence relation used. (5 Pts.)
Answer
Solution The data of a LFSR diagram, of a linear recurrences relation, and of a connection
polynomial are equivalent — they express the same information. The connection polynomial
g(x) = P encodes the wiring of a LFSR which implements a recurrence relation. Thinking of x j
as a shift operator acting on the sequence s0, s1, s2, . . . , the behaviour of g(x) in the product
g(x)s(x) (below) is
(c) (d) Draw the LFSR that implements the given stream cipher. (5 Pts.)
Answer
The diagram of such LFSR is:
Io;{
{}p/1300
3+-------------+-----------+-----------+-----------+------------+-----------
+-----------+------------+
| | | | | | |
| |
| *a *b *c *d *e *f
*g |
| | | | | | |
| |
| +-----+ | +-----+ | +-----+ | +-----+ | +-----+ | +-----+ |
+-----+ | +-----+ |
| | | | | | | | | | | | | | | | | | |
| | | | | |
+--->+ x0 +---->| x1 +---->| x2 +---->| x3 +---->| x4 +-----> x5 +----
>| x6 +---->| x7 +-------> ...
| | | | | | | | | | | |
| | | |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+-----+ +-----+