Stream Ciphers - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

okay today we will start with the topic
of stream ciphers so as as we we are
discussing in a lab last days class we
were discussing about block ciphers and
also we finished with the modes of block
ciphers okay so what we saw I mean
typically is that we saw certain we know
what is the definition of block ciphers
and we know how to use block ciphers
okay so therefore there were certain
modes that we defined out of them if we
remember that the last few modes which
were design which were defined we're
essentially slightly different from the
definition of block ciphers okay so they
were applied more something like a
stream cipher okay so anyway so we will
take up the topic of stream cipher more
formally and try to understand the
principles we are in the constructions
okay so so the first we will discuss
with the classifications that exists in
the stream cipher world okay and then we
will start with a very interesting topic
and important also that is about
feedback based stream ciphers okay so we
will talk about lfsr's linear feedback
shift registers and also define
something which is called M sequences
which are very much used to generate
something which is called pseudo
randomness in cryptography okay so we
will try to understand the basic
principles but since we know what these
are rather we have studied block ciphers
let's start with the difference between
block and stream ciphers okay so the
differences are not very much definitive
so it means that exactly clearly
differentiating between the two is
slightly tricky but we can say in this
in this way that block ciphers
essentially process the plaintext which
operates on large blocks of data okay
but as opposed to that stream ciphers
will operate on small blocks of data so
this is very sort of we can say we are
not very perfect or not very accurate
the difference but this is this can be
used to essentially differentiate
between block ciphers and stream ciphers
okay another important difference which
we can say is that the block ciphers
okay so if you remember the block
cyphers the block ciphers are
essentially the pure block ciphers are
essentially memoryless so what does it
mean it means that the output at
particular time say time T does not
depend upon what happened at time t
minus 1 okay
so therefore all the operations of your
encryption functions are independent of
your previous operation okay so this was
so when I say it's a pure block cipher
mode we remembered about the ECB mode
okay so in such kind of scenario block
ciphers we're memoryless okay but by
definition we will see that our stream
ciphers are are essentially having a
component of memory okay so that means
that it does not in case of stream
ciphers the ciphers that you produce are
not a resultant of only the plaintext or
the key but also something which we call
as a state okay so that is as something
is called a state or a state variable
which gets updated as a time goes by
okay and your output depends not only
upon your plaintext and your key but
also depends upon the current state okay
so these are the broad differences but
as we remember that in case of block
ciphers like the modes that we had like
the mode like ofp mode and CFP mode and
so on they were essentially more like
stream ciphers okay so keeping this
difference in mind and also the kv8 what
we will do is we'll go ahead with this
definition of stream ciphers okay so let
us start with a something which we have
already seen which we call as a one-time
pad okay so one-time pad is a first
extracting example of stream ciphers
okay so therefore if you remember the
idea was very simple that for I varying
from 1 to 3 and so on your ciphertext CI
is obtained by the XOR message and your
corresponding key value okay so this we
call also at the Varnum cipher and this
was defined over the binary alphabet
right so we say that it was
unconditionally secured and we also
prove this result okay that we saw this
where that HK
is greater than equal to hm so what does
it mean that is the entropy of your key
should be at least equal to that of your
message entropy okay so that means that
you have got a large key value so what
is the problem that we saw with this the
problem was that we had a large key to
handle okay so we want so in case of
practical scenario you what we would
typically want is that we will try to
ensure that HK value is actually less
than nature
the moment we see that we know that we
are not getting something which is
called as unconditional security right
so what we strive for is computational
security that is we are striving for the
fact that suppose an adversary has got a
bounded power there is a Kong is
computationally bounded we are trying to
guarantee that we guarantee security
against such kind of adversary okay so
that is the model so therefore so
therefore that is the intent so
therefore the intent is protection
against a computationally bounded
adversary okay so what we will see in
all the studies that we do about stream
ciphers is that we will try to again
produce this key stream ki so if you see
the one-time pad we will try to produce
this ki but with a smaller key okay so
in case a one-time pad
we had the size of the key at least
equal to that of the message size rays
but in case of practical stream ciphers
we will try to produce this key stream
and make it look as much random as we
can okay but we will start with a
smaller key okay that is the initial key
should be much lesser than that of the
message size right
only there it becomes practical correct
so the first class of stream ciphers
that we will see is something which is
called a synchronous stream cipher so
what is the synchronous stream cipher a
synchronous stream cipher is such kind
of stream ciphers for which your key
stream is generated independent of your
plaintext or cipher text okay so that
means it does not depend upon when the
plaintext comes or when the cipher text
comes okay nobody takes take it proceeds
quite independent
okay so the encryption process which we
can we can essentially do differentiate
or divide this into three basic parts
the first part will update a state
variable okay so therefore as I told you
that this kind of stream ciphers has got
a state variable so there is a state
variable which we denote by Sigma and
this value of the state variable gets
updated during the encryption procedure
okay so there is a function f which
takes in Sigma I and also the secret key
value so you see that we start with a
smaller key okay
and using this smaller key we actually
carry on iterations to generate a large
key stream okay so we start with the
smaller key and we keep on iterating
sudden proceeded processes or procedures
to get us to get a larger key okay to
our or to get a larger key stream so
what we do is that we take this Sigma I
and we take this key stopping key and we
operate this function f and we obtain
Sigma I plus 1 okay so remember that
this function f G and H are all known in
the public domain okay so what is secret
only this key value is secret that is
this K value is secret okay so we start
with an initial vector so you
immediately you can understand that in
order to start you require a Sigma 0
right so this Sigma 0 is commonly known
as the IV or the initialization vector
okay so we start with an IV and we keep
on operating this process and we obtain
something we keep on updating the state
variables ok so then what we see is that
whenever so therefore then what we do is
that based upon this Sigma I and this K
value we generate Zi which is used to
denote the keystream okay now the moment
we see that the cipher text I mean the
message comes like mi comes in we
operate mi and Zi
and obtain the corresponding cipher text
C I so here you see that this Zi or this
key stream Zi can be generated ahead of
time right it does not depend when the
corresponding plaintext comes in right
and that is why it is called a
synchronous stream cipher it does not
depend or it
we generated independent of the
plaintext or of the ciphertext okay
plaintext during encryption and
ciphertext during decryption right so
therefore an example of this could be a
binary additive stream cipher so in that
case what we do is that this
corresponding H function is nothing but
the eggs or that is you take Zi and you
exert that with mi so you see that when
we do that the definition or rather the
description is quite similar to the
one-time pad right so only in this in
this case in what is the difference in
this case this corresponding key string
is generated actually from a smaller key
using a deterministic algorithm right so
therefore that is the basic difference
between these class of stream ciphers
which are practical from a one-time pad
okay
and that's why this is not
unconditionally secured but what we are
only guaranteeing is that we are trying
to make it secure against her
computation only bounded adversary so
that is the definition of synchronous
stream ciphers so this is a pictographic
description so you can see that it is
the same thing like we take Sigma I
which is the state variable and there is
a corresponding K value using both this
things but we are doing essentially is
that we are keeping on using a function
if we are keeping on updating this state
variable function the moment we have
this corresponding state variable we
take the state variable operate upon the
key also and we obtain the key stream
which we act upon the corresponding
message to get the cipher text right so
depletion is quite simple you can see
easily that what you do is that you
again take the cake and you can do this
same operation here also because it does
not depend upon your plaintext right you
take this Sigma you take G you can
obtain this key stream ahead of time
again and in this case you require the
inverse operation of H right so if this
was a modular exhort then this would
have been the same operation right
because modular inverse is I mean
modular XR is self invertible right so
therefore you can see that you can make
quite simple cipher structures using
that right
these kind of things and they are quite
fast right and that is the why that is
the reason why stream ciphers are quite
popular so they were very much popular
and still are quite popular okay so the
properties of so let's study some
properties of these ciphers so we will
essentially try to first of all
understand one important difference that
we will see with another type of ciphers
that we will see next it's something we
just call the requirement for
synchronization that is you can see one
thing that is when you are encrypting
and you are sending the data to the
corresponding decrypted then this what
what can happen in between is that this
cipher text can get damaged right
because of maybe of your accidental
reasons or due to malicious reasons okay
so for example even due to communication
errors there can be errors introduced in
this ciphertext okay so the moment you
see that for example so there can be two
kind of different two kind of damages
one in which you can drop some CI values
okay that is you can delete some CI
values and also insert and the other
when you when you modify some serious
okay so in both thus both the cases in
the decryption end at the decryption in
there will be two types of events that
occur okay so can you see that like for
example let us consider first blood I
take CI I have got the stream of sea-ice
coming in right and I just changed say
for example R 1 to 0 so imagine a binary
alphabet okay I just change a 1 to 0
what will happen only that particular M
I would get changed right rest of the
things will work fine alright so you see
that if there is a corresponding change
in the corresponding ciphertext then the
decrypt art won't be able to figure out
except the fact that only one particular
bit has got changed rest of the things
will take place fine
okay so this can be a problem in certain
kind of applications of these ciphers
like for example if I want to also
ensure that my integrity of data is
maintained okay so there can be a
problem in such kind of scenarios okay
so consider another case where I drop
some packets like I take CI for example
and I start dropping some values of
sea-ice then what will happen then there
will be a disaster actually at the
decryption end you see that if I start
doing that then there will be a total
loss of synchronization okay so you see
that if I start dropping or deleting
some values of CI or inserting some
extra values of CI into the stream then
there will be a complete D
synchronization between the encryption
and the decryption parts portions okay
so how do you recover the only way to
recover would be to reset right to start
again from the scratch or what we can do
is like what we do in typical examples
of networks we can actually have some D
markers right we can have some markets
okay but you see that this is adding to
the complexity of your job okay so you
would actually want would have wanted
another kind I mean a class of stream
ciphers where we can alleviate this
problem right so so therefore that is
the thing which we have mentioned here
so let us again read out this properties
so it says that the sender and the
receiver must be synchronized that is
using the same key and operating at the
same state with that key okay within
that key so insertion or deletion may
cause loss of synchronization
okay resynchronization may need
initialization and or special marks in
the stream at regular intervals okay
similarly you see that there are no
error propagation so if I just modify
one digit only that corresponding digit
gets modified okay so this essentially
leads to certain kinds of active attacks
can lead to active attacks like for
example if I insert delete or replay
okay then this cause laws of loss of
synchronization okay and immediately you
see that this is detected by the
Decrypter because in such kind of things
there is a complete havoc taking place
at the decryption name right so I can
possibly figure out that these kind of
things have taken place like there has
been some ciphertext being
inserted or deleted okay so therefore
you see that I can ensure this kind of
that I am a built at the decryption end
I am able to figure out that such such
kind of malice has taken place okay but
if you just for example change a
particular cipher text value then I'm
not so easy then it's not so easy to
figure it out okay because in that case
the rest of the decryption takes place
fine and only few changes occur okay so
if you see that at the decryption end if
large number of changes occurred then it
will be easy for me to understand right
so therefore if you actually delete or
insert some ciphertext values that
becomes easy okay but if you change some
values then you are not able to figure
out right so in therefore in this class
of stream ciphers what we see is that if
we change some ciphertext values okay
then it becomes easier to capture at the
decryption but if we insert or delete I
mean sorry another way down if you
insert or delete it becomes easy to
capture but if you actually just change
or modify some ciphertext values say one
ciphertext value then it is not so easy
to capture okay so this is actually
quite different from another class of
stream ciphers which we called a self
esteem self synchronization stream
ciphers okay so what is your self
synchronization stream cipher you will
just see so it's an a synchronous stream
cipher as opposed to the previous one it
is one in which the key stream is
generated as a function of the key and a
fixed number of previous ciphertext
digits okay so therefore in this case I
think what we can see like this that is
if you for example consider a window of
cipher texts okay so let us consider a
window of size T okay and therefore what
we see is that if the corresponding
state variable Sigma I depends only upon
this window of size T okay and therefore
this is an essential difference between
the previous class of stream ciphers and
this why now because if the error occurs
anywhere outside this window then
there is no problem in the decryption
okay the problem occurs only if there is
an error inside this window okay so that
means this helps this property helps to
automatically recover okay so I think it
will be clear with this diagram and with
this description that is for example you
consider this window of toys ice-t like
CI minus one whose CI minus T so you
considered CI minus T CI minus t plus 1
and so on till CI minus one so this
determines your Sigma I value and then
just like in the previous case you
operate take Sigma I take key K and
operate G and obtain the screens Zi and
then again operate upon Jedi and mi to
obtain your corresponding ciphertext
value okay so in this case the initial
state will look like this okay so if you
just consider the diagram you see that
it will look like this so you have got
this I window of ciphertexts okay this
operates up on your G value and gives
you I mean your G value takes the
ciphertext values takes the key K and
obtains the stream ciphers a die
okay now this Zi and your message mi
gets operated with the function H it
could be a simple exert and you operate
the value of CI okay what do you what do
you do at the decryption in is exactly
the opposite right so you take again
these ciphertexts
and again take this function H okay and
take this function G up to obtain the
key stream they act upon the inverse of
H and obtain back the plaintext okay so
what is the difference you see in this
case synchronization becomes easy why
it's simple right because because you
see that in this particular diagram if
there are errors only in the insa in
this window then then you have a problem
okay otherwise it's fine so suppose
there has been some divisions that take
place some modification that plague pace
okay
as long as the effect of this persists
you will find that the corresponding
decryptions will be faulty but after the
problem vanishes then actually this then
actually your decryption works fine okay
so therefore if there is an even if
there is a problem you can eventually
get out of that problem right so
therefore you see that I'm actually we
have seen such kind of scenario in a
particular mode of block cipher can you
tell me what in a cipher feedback block
okay if you remember we had an art bit
left shift there okay so I will come to
that but I mean we have already seen
that example okay so so in this case you
see that self synchronization is
possible okay so if there are in
insertions and deletions then at most T
digits may be lost okay so if we if
there are most T digits which are lost I
can still get out of this problem
okay so limited error propagation that
is one digit modification or insertion
or deletion may cause encoded decryption
of up to T digits this is also another
difference from the previous one in case
of previous synchronous stream ciphers
what we have seen is that if you modify
only a particular cipher text CI then
only that particular digit in your
plaintext gets modified okay but here a
particular cipher text has got a control
over T decryptions okay
so therefore T even if there is a
modification in only one single bit okay
or in one single digit then you will
find that there will be corresponding or
problems in the decryption forty T
number of times okay so in this case you
see that just the opposite like if there
is an insertion or a deletion
okay then it's hard to catch because you
are finally getting out of that problem
okay
after tea such kind of size decryptions
you will finally eventually end up with
so I mean when I say easier are hard I
am comparing with the with the
synchronous stream cyphers okay see in
case of synchronous stream cyphers if
there was an insertion or a deletion
then there was a total problem
subsequently all the decryptions would
have been faulting okay in this case
after T such kind of decryptions finally
the problem is solved it's finally again
synchronized okay so that way it's I
mean harder to catch in I mean if there
is an insertion or deletion in case of
self-synchronizing stream cyphers it's
harder to catch
compared with us synchronous stream
cipher okay but whereas if there is a
say modification that is a one bit error
or something like that then in case of
these class of stream ciphers okay what
happens is that you find that T
decryptions are faulty but in case of
your synchronous stream ciphers only one
digit was faulty okay so so therefore
these are the basic differences between
this class of stream ciphers and the
previous stream ciphers okay so what we
I mean just as a note you can note that
the diffusion on the plaintext a
distance is better in case of this kind
of self-synchronizing stream ciphers but
even then there then there are attacks
okay like I mean you can see that in the
previous case it was easier you can just
reflect upon this fact it was easier to
mount a a known plaintext attack okay
but in this case it's easier to mount in
a known ciphertext attack chosen
ciphertext returned and there are
attacks actually even on quite
contemporary stream ciphers of this
class
so now I mean this is just a recap of
what we have remain what we have already
seen so in case of CFP I've just
replaced this R by one okay so this is
one bit CFP so you remember that this is
what this was the diagram right so you
see that after so how I mean we already
say that if there is an error then the
error at the decryption will remain will
remain as long as this corresponding
error remains in this register I write
after that after the effect is very is
after the effect disappears you again
get correct decryption okay so you see
that this is this is an example of
self-synchronizing stream cipher so then
we come to something which is quite
interesting it's called feedback shift
register and quite involved also so they
are essentially basic blocks of many key
stream ciphers k key streams generators
and we will essentially study a very
important class of feedback shift
registers it is called lfsr or linear
feedback shift register okay so it is
very well suited for hardware
implementations and it can also produce
sequences a very large period okay so
therefore this property is very much
required for stream ciphers that is be
what we want is that we want a large
period in the stream ciphers okay so we
don't want small cycles we want that the
repetitions will take place after a
large number of times okay and it should
also have good statistical properties
now what are good statistical properties
have actually not defined okay but we
will take up this issue in our
subsequent class on pseudo randomness
okay so at this point of time just
imagine that good statistical properties
mean that it should look as much random
as possible okay so and this can be
actually analyzed by algebraic
techniques also so therefore this
analysis or this amenability to analysis
helps us to understand the security of
these kind of ciphers okay
so you will see that there will be
problems okay and in order to solve this
problems we will actually start
incorporating small amount of
non-linearity into the stream
diverse but that actually makes it
harder to analyze okay and therefore it
becomes not very popular so therefore
you have to make stream ciphers I mean
whatever ciphers you make on one hand
you have to make it secure and on the
and at the same time you have to also
make it amenable to analysis because if
it becomes harder to analyze then you
can leave it neither say it's strong not
say it's weak right so you have to show
how you can actually analyze your cipher
okay so we will take up this issue of
this topic of linear feedback shift
registers so I think broadly we can
describe an lfsr of length L as an L
stage
so therefore when I say delay raiments
in terms of hardware I can just think in
as a D flip-flop okay so you can imagine
that there are L Li flip-flops which are
capable of storing one bit each okay and
there is a clock which controls the
movement of the data okay
so you can understand that this is a
shift register so what does it mean that
is there is essentially a shifting in
these arrays okay
apart from that there is a term which is
called a feedback okay so that is there
has to be some feedback at some place
right so therefore you will see that and
in case of an lfsr you have this like
you have this structure like you have
got this area of I mean array of cells
okay so you can so there are L stages so
which means that I can write like this
is say for example s L minus 1 this is
SL minus 2 and so on this is say s 0
okay so what happens is that if you this
is essentially also a shift register so
therefore there is a shifting among
these flip-flops and there is also a
feedback right so this input is actually
a feedback of the output of your
previously previous flops
okay so customarily what we do is that
we can think in terms of an get here and
you can imagine that
whether this connection exists or not
that is being denoted by a by some
controlling values okay so for this for
example we can say like c1 and we can
continue like C 1 C 2 and so on till CL
okay and these outputs are essentially
exhort here okay
okay so this is an example of therefore
this is your feedback Porsche - this is
your feedback okay and you can now
understand that probably also say or
appreciate why it's called linear
feedback because of these absorbs okay
so if I had replaced these exerts might
say an Gates or some other gates then
this wouldn't have been called a linear
feedback shift register okay and there
are actually examples of something is
called a non linear feedback shift
registers also okay so but we will
essentially study with linear study
linear feedback shift registers and this
is how the diagram looks like and this
feedback is also sometimes it's called a
connection okay and this is sometimes
denoted by something is called a
connection polynomial okay so I can
represent or denote this feedback by a
polynomial we is called a connection
polynomial okay and it is like this it
works like the C 1 plus C 1 D plus so on
till CL okay so I call it CL + d ^ say L
where L is your length okay so if I want
an L I mean if I want that the degree of
this polynomial will be L okay then I
have to ensure that the value of CL
should be 1 so therefore that means that
always this value of CL should be equal
to 1 okay and what is that I mean and
there are some merits Phi it's really
skeptical to 1 okay because we also want
periodic sequences okay so this is how
it looks like and this is again our
diagram in a better diagram for the same
thing okay and this is denoted as L
comma C D okay so therefore L is the
length and C D is your connection
polynomial okay and CDs as I told you is
look works out like this and what is
that what is Ln is a length of the lfsr
okay and this topple essentially you
know I mean defines a corresponding lfsr
so we can consider a very simple example
like you can take a four stage lfsr or
for which the connection polynomial is 1
plus D plus D power 4 so the moment I
say D that means that this particular
thing is connected the rest of the
things are not connected right so you
can take this polynomial and you can try
to see how the sequences work okay so
for example you can just start giving
some inputs like some arbitrary values
like 0 1 1 0 okay and you can start
clocking the lfsr okay so you can
observe that if you see the diagram then
this particular thing is a feedback or
rather is the wind back is an excerpt of
this output and this output that is d 3
n d0 the rest of the things are only
shifts okay
so you see that zero gets shifted here 1
gets shifted here again 1 gets shifted
here and what about this value
it is a xor of this value and this word
right so what about this value it is a
xor of this value and this word ok so on
you can work it out right and the rest
of the things are only shifts like 0
comes here again comes here again comes
here 1 comes here comes here comes to
here right so what is the output of your
lfsr so if you see the output of your
lfsr we have taken the output from d0 ok
so that means that last column d 0 gives
you the corresponding sequence right so
so if you see if you workout with this
particular example you will see that at
15 so if I start with 0 at the 15th
point you see that you again get back 0
1 1 0 so 0 1 1 0 is the particular value
with which you started with so which
means that you have got a periodicity
but you have got a periodicity of 15
right why not 16 because there is one
missing state and what is that the all 0
values okay so in case of all 0 values
it will just get stuck up at its own
point right so therefore it will not
actually go to the network go to another
state okay
so therefore you see that you have got a
periodicity but your period periodicity
in this case it's something which I
called as a maximal okay with two power
of I mean with four stage the four stage
lfsr there are totally sixteenth values
but out of them there are fifteen
nonzero values okay so you can that is a
maximum size of cycle that you can
obtain so so therefore you see that this
lfsr sequences are quite attractive
because of this periodicity property
okay and that led to the lot lots are
not so study of its periodicity okay and
people try to figure out why it's
periodic or what are the properties that
controls its periodicity okay so for
example like if we if you see that if
your CD is a connection polynomial of
degree L and is irreducible over z2 then
each of the two to the power of L minus
one nonzero state initial state of the
lfsr produces an output sequence which
is periodic okay and what is the size of
the what is the periodicity the
periodicity will be the minimum value
okay for which the connection polynomial
minimum integer value for which the
connection polynomial divides one plus D
power of him okay so therefore that is
the minimum such value for which it
divides okay so this n will be actually
a capital n okay so there's a mistake
this integer n and this is that Indian
okay so in this case you will see that
this I mean so therefore used if you
take irreducible polynomials for your
connection polynomial okay then you will
find that it will be periodic okay and
your periodicity will be actually the
minimum value of n for which one plus D
power of n will be divisible by C D okay
there is that small smallest value of n
and you will see that in all cases this
value in will actually divide 2 power L
minus 1 to power L minus 1 so n will
always divide 2 power L minus 1 okay so
so if I brief what I am trying to say is
this that is CD
is irreducible so this implies that your
periodicity or period will be equal to a
value of n or rather if I call it an N
and in will actually divide two part of
L minus one okay and in certain cases it
will be actually equal to 2 power of L
minus 1 okay in thought in those types
of cases in those cases when n is equal
to 2 power of L minus 1 CD is actually
called a primitive polynomial
okay so what is a primitive polynomial
we can define it in this fashion fashion
there are some other definitions of
primitive polynomial also so you can
immediately figured out that one way one
definition of primitive polynomial would
be like what I said you that CD divides
X ^ in my I mean D to the power of n
minus 1 right so therefore you know I
mean in case of irreducible polynomial I
mean so if you come to this particular
thing that is the minimum value of n for
which 1 plus D power of n is divisible
by CD okay and when this n is actually
equal to 2 power of L minus 1 then that
is called a primitive polynomial okay
another easy I mean another definition
of basic definition of primitive
polynomial is that you remember the
finite fields right so therefore if you
take for example the finite field Z okay
I mean Zn star okay and you just start
with any of the primitive elements say
you start with X okay and you keep on
taking its power like you take X X
square X cube X power 4 and so on and
whenever there is an overflow you do a
modulo with the corresponding polynomial
and if you find that you are able to
generate all distinct values in the
field then that particular polynomial
that that particular reduction
polynomial is also primitive okay so do
you understand what I am saying so what
I'm saying is that if you start with a
polynomial okay and you take the
primitive element okay and you take its
power and you also take the modulo
operation using that if you are able to
generate all the elements in your field
okay when I'm thinking I'm talking about
the multiplicative part okay I'm not
talking about zero okay so therefore if
you are able to generate all the
elements then that polynomial in that
particular reduction polynomial is also
primitive at the same time okay so in
this case luckily 1 plus D power 1 plus
D plus D power of 4 was actually a
primitive polymer for finite field over
I mean so if you in terms of final in in
terms of the galilean notation it is GF
2 power 4 okay so so therefore
if one plus D power plus D power of four
he's actually a primitive polynomial of
GF 2 power of four and therefore
actually the periodicity of the
corresponding lfsr was equal to 15 which
was equal to 2 power 4 minus 1 okay so
then the next question that we will take
up and he's actually quite a non-trivial
question that is can i reconstruct the
lfsr that is given a sequence can I
actually reconstruct back the lfsr so
therefore if I give you a sequence and
the question is can we reconstruct the
lfsr with generates a sequence you
understand the problem ok then now the
problem that I'm talking about is that
if I give you the corresponding output
sequence and I want back the lfsr so
there are two things that is important
one is the length of the lfsr and the
second thing is that the feedback of the
value Fitzer ok so I think I need to
compute both the things so there is a
term which is called linear complexity
and this problem is essentially
something defined by something which is
called a linear complexity ok so so
therefore in life assad is said to
generate a sequence s if there is some
initial state for which the output
sequence of an lfsr is s so this is a
quite simple definition so this is just
to define what you mean by generating
the sequence and if the sequence has got
a finite length in then we will use s n
to denote that ok so what is the linear
complexity so linear complexity of an
infinite binary sequences is denoted as
follows if s is a zero sequence so zero
sequence means all zeros then I define
LS to be equal to zero if no lfsr can
generate s then LS is actually equal to
infinity okay that means it says it's LS
is equal to infinity I mean all these
things will make sense with this third
point okay it says that otherwise LS is
the length of the shortest lfsr that
generates s ok so this is this L is
something which is called the linear
complexity ok so what I'm interested is
in finding out the smallest lfsr which
will generate a given sequence
okay so therefore there are two things
that I'm interested in you understand
one is the length of the lfsr what is
the smallest length which generates it
and the other thing is that what is the
corresponding connection polynomial
right so how do I understand that okay
so let us start with a simple example
okay and that is I mean it's better to
start with the example because there is
a quite involved algorithm you know I
mean I mean we'll just decide whether
we'll go into in depth or not but at
least we will try to appreciate what is
meant by a linear complexity okay so so
therefore let us try with this simple
example so let us try to reconstruct an
NFS R whose sequence is a 0 0 1 1 1 0 1
1
ok so so let us start with only these 2
0 0 hmm so you immediately you can
understand that if you have got two
corresponding next to next zeros
subsequent zeros then your lfsr length
cannot be 2 right because if I elevator
length is 2 then you are getting
starting sucked up at that point right
so it has to be more than 2 right so
therefore what is the what is the size
that you can start with next it is 3
right so let us take three such d
flip-flops okay and try to work out ok
so we we take like s so I call that say
s 2 s 1 and s 0 okay and let us try to
generate 0 0 1 so you can see that it
will be 0 0 1 then the first thing comes
out is 0 then you again 0 and then you
have got one here ok and what you need
to figure out is whether this particular
thing is connected or not right so
therefore what is the corresponding
value of C 1 what is the corresponding
value it is a NAND gate ok so therefore
this is a there is an XOR here there is
an XOR
there is an and here so you have AC 2
here and I am connecting this value
because I'm taking this to be 1 okay so
right so this is how your diagram looks
like right so what I'm interested in is
in finding out what is the value of c1
and c2 right so you see that if I take
this one zero zero then what is the
corresponding next sequence it is one
comes here zero comes here okay then
again this one comes here and this is my
and this is the output which is being
regenerated right so therefore you have
got 0 0 1 and so on
so what is the next sequence it is 1
here so you can take this one and put it
here and this one will come here so
therefore the I can write some equations
like I can I know that the next thing
which is to be fed back is 1 right so
immediately I know that 1 is equal to c1
so what is the corresponding value here
is this one here C 1 XOR with 0 and this
is 0 so this is 0 right
so that means C 1 is equal to 1 what
about the next thing the next thing in
the sequence is also 1 so that means
this is a 1 which is again to be fed
back so you know that 1 is equal to so
you know that 1 is to be fed back yeah
yeah so if we it's ones or C 1 no c2
right yeah any other thing
that's fine so that means what is the
value of C 2 it is zero okay what about
the next sequence it is zero so you
should get back here zero are you able
to get back zero so you see that the
next thing that you get back here zero
is suppose suppose this is 1 and this is
0 okay then you are actually getting
back 0 right so therefore you are see
that you see that you are getting back
you are getting 0 0 1 1 1 and 0 ok but
what about the next thing that you will
get you will actually not get up you
will get 1 you will get 1 next you're
getting back 1 also you see that but
there will be a problem with this one so
here instead of 1 you will have 0 so
that means that this particular lfsr
configuration cannot generate beyond
this right so you see that that is so
yawn you start to understand that there
is something which is called a smallest
possible length okay and therefore we
need a bigger lfsr to do the thing ok
and you can actually work out this
example with a 4 stage lfsr and you will
find out that there will be a some
inconsistencies in the equations for
which you can understand that a 4 stage
lfsr will actually not give you this
sequence also ok so actually it will be
a 5 stage lfsr which will give you this
output ok and the equations will become
only a little bit more complex okay so
what do you understand that
if you if you write in in such kind of
in such a fashion and you obtain a
linear system of equations then you can
actually solve them right you actually
require to n number of bits to solve
these equations ok but the thing is that
the solving becomes easier by a certain
approach okay and that approach is known
as the ball like a messy algorithm ok
but this essentially gives you an idea
so what we today discussed is about and
basic idea that there is something which
is called a smallest possible length of
an lfsr
with generates a given sequence okay so
that means that you start to understand
that you need a bigger lfsr to generate
the corresponding subsequent sequences
okay so you can ponder about this
particular point and you can just think
of this point that what we have
discussed is the about NFS R which we
just got no all 0 values that can you
modify the lfsr with connection
polynomial primitive to include the all
0 state ok so some other ridi I mean
references
you know that's testing I followed a
little bit of Stinson's book but mainly
I've followed manases handbook of
applied cryptography this book is
actually available online okay so you
can actually download this chapter
chapter 6 of this book and you can study
this chapter also so we will continue
with streams offers
you
you