Decrypting Alice's Message: An In-depth Analysis of LFSR Cipher

This assignment solution delves into the analysis of a Linear Feedback Shift Register (LFSR) based synchronous stream cipher. It involves determining the initialization vector, feedback coefficients, and recurrence relation used in the cipher. The solution utilizes the Berlekamp-Massey algorithm and ...Read More

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 +-------> ...
| | | | | | | | | | | |
| | | |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
+-----+ +-----+

where a b c d e f g are constants set to 0 or 1 to determine whether a bit influence the next
result.
Thus you can see the LFSR as following parallel formulas:
out←x7out←x7
x7←x6x7←x6
x6←x5x6←x5
x5←x4x5←x4
x4←x3x4←x3
x3←x2x3←x2
x2←x1x2←x1
x1←x0x1←x0
x0←f(x0,x1,x2,x3,x4,x5,x6,x7)x0←f(x0,x1,x2,x3,x4,x5,x6,x7)
where
f(x0,x1,x2,x3,x4,x5,x6,x7)=(x0∧a)⊕(x1∧b)⊕(x2∧c)⊕(x3∧d)⊕(x4∧e)⊕(x5
∧f)⊕(x6∧g)⊕x7f(x0,x1,x2,x3,x4,x5,x6,x7)=(x0∧a)⊕(x1∧b)⊕(x2∧c)⊕(x3∧d)⊕(x
4∧e)⊕(x5∧f)⊕(x6∧g)⊕x7
From this you can deduce:
f(1,0,0,0,1,0,1,0)=0f(1,0,0,0,1,0,1,0)=0 and the LFSR returned 00
f(0,1,0,0,0,1,0,1)=1f(0,1,0,0,0,1,0,1)=1 and the LFSR returned 11
f(1,0,1,0,0,0,1,0)=1f(1,0,1,0,0,0,1,0)=1 and the LFSR returned 00
……
and finally:
f(0,1,0,0,1,1,0,1)=1f(0,1,0,0,1,1,0,1)=1 and the LFSR returned 11
Notice that the first column is the second part of the stream : 011…1011…1 and the
second column (LFSR returned) is your first part of the stream: 010…1010…1
(e) Write a program in your favorite programming language to generate the whole key stream
and find out the complete message sent by Alice. (25 Pts.)
Answer
Given in zip file

Answer 2
p(x)=p(x|y),∀x∈P∧y∈C.
The p(x)p(x) is whatever the original distribution says it is. Now p(x|y)p(x|y) cannot be the same
as p(x)p(x) for this
p(x|y)=p(y|x)p(x) /p(y)
p(y)=∑p(k)p(dk(y))
so probability that key used was k∈K times the probability of decrypted message being dk(y)
I would think p(dk(y)) is same as p(x) as x is y encrypted and as we sum over all the keys, for
any key there is some y∈C which maps back to a given x∈P this is same as p(x).p(x).
Thus p(x|y)=p(y|x) We know x, and every key maps every plaintext to different cryptotext, they
would have same distribution, so p(x|y)=p(y|x)=p(x)p(x|y)=p(y|x)=p(x).
Answer 3
Suppose S1and S2 are Vigenere Ciphers with keyword lengths m1, m2 respectively, where m1>
m2. If m2| m1, then S2× S1= S1 .If mod m2, then the number of keys in the product
cryptosystem S2× S1 is than the number of keys in S3.