Shannons Theory - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

okay so welcome to this class on
Shannon's theory so as I told you in my
previous classes that Shannon's theory
is a very fundamental theory in the art
or science of cryptology so essentially
it was the seminal paper in 1948 and 49
which essentially postulated certain
theories okay
so they essentially form a cornerstone
of what we known as today's ciphers okay
so for you will find that whatever we
whatever the basic formulations or basic
properties we find in today's ciphers
you can essentially go back and find
that those things existed in an old
paper in 1948 and 49 okay so we will try
to understand some of the concepts in
those papers so in today's class the
objectives will be as follows so we will
try to understand the definition of what
is meant by perfect secrecy okay and
prove that a given crypto system is
perfectly secured so that is our
objective that is a given a crypto
system we should be able to essentially
find out whether it is perfectly secured
or not okay and then we will see that
how to construct or realize certain kind
of perfectly secure ciphers so we call
them one-time pads or OTPs okay so after
that we will go into a very fundamental
instrument that we use for our these
kind of proof proofs so it is called
entropy so we will try to understand
what is entropy and its computations
okay and then we will follow that up
with the definition of ideal ciphers and
conclude with some a topic called equal
vocation of keys yes I will gradually
progress and we will try to understand
these concepts but these concepts form a
part of Shannon's theory and we will
actually conclude with something but
maybe not in today's class so first of
all what I would like to define what is
meant by unconditional security okay so
essentially the idea is that we are
essentially considering an adversary who
is powerful powerful enough means he has
got unbounded computational power so the
idea is that given a cipher and given
and versa you who has got unbounded
computational power then whether he or
she is able to break a given crypto
system okay so that means when we when
we talk about unconditional security it
concerns the security of crypto systems
when the adversary has unbounded
computational power so unbounded
computational power means it has got
infinite resources okay so in final
resource this means what it has got
infinite time it has got in finite space
and the question is whether even then
whether it can break a given crypto
system so what do we mean when you say
break a crypto system obtain the value
of the key right so so essentially we
have seen various kinds of attacks we
have seen like various classes of
attacks so we will be considering that
we will considering as hypertext only
attack that means the adversary has got
access to the only the ciphertext okay
and given an unbounded unbounded
computational power whether that
virtually is able to ascertain the value
of the key okay so the question
obviously which comes to our mind is
when is a given cipher unconditionally
secured okay so in order to understand
that we will use some theory of
probability and we will try to
understand how what what is the model of
an unconditional adversary and is an
unbounded adversary and try to
understand what is the definition of
unconditional unconditional security we
also call that perfect security okay
yeah yeah that is the basic basically we
have as we have said that the car scoffs
principle essentially said that the
algorithm is open right so the security
lies only in the value of the key so the
value of the key is not known to the
adversary so the adversary knows the
algorithm everybody knows the algorithm
the algorithm is in the public domain
okay so what you do not know is the
value of the key and the question is
whether you can ascertain the value of
data all right so so therefore we will
use certain terms in probability I call
them as a priori probability and a
posterior probability okay so the idea
is as follows
so whatever encryption you considered it
is basically a function right it is a
function
from the domain of a plaintext to
ciphertext okay so therefore as we have
seen in our old classical ciphers they
essentially comprised of what they
considered for example let us consider
the just the alphabet alphabets
making up the plaintext right so
therefore how many possible letters or
symbols are there there are 26 letters
or symbols all right so these 26 letters
or symbols are being somehow transformed
and converted into a ciphertext right so
for all of these letters like ABCD is
soren so on 2 Z has got some
probabilities right as we have said like
in English language is the most
according most frequently occurring
later right so therefore they have got
some probability distribution initially
before the ciphertext starts right and
that is what we call as the a priori
probability right and that is getting
essentially so therefore we denote by
the term PPX so as if you can see here
we denote by the term PPX a priori
probability of a plaintext
okay and therefore this is the
probability that is assigned to every
letter or symbol of the plaintext before
the encryption has started okay so so
essentially the key also has got a
probability distribution and therefore
now the in the encryption function takes
place okay
so therefore what happens is that the
plaintext gets converted into the
ciphertext so if we consider a crypto
system where the plaintext and the
cipher text both comprised of Singlish
letters then the initial frequency or
probability distribution of the
plaintext is getting transformed into a
different probability right so so
therefore that so there is a probability
transformation right so therefore let us
consider like for example by as we have
said that p PX denotes the a priori
probability of the plaintext right
similarly we have got PKK which denotes
the a priori probability of the key
right so the cipher takes is generated
by applying the encryption function so
therefore if we consider that plaintext
the plaintext by X or denote the
plaintext by X and there is an
encryption functions e ok and based upon
the value of the key
we know that Y X is getting transformed
into y okay so so what we note out here
is that the both the probability
distributions that the plane that is the
plain text and the key are independent
right because when we are choosing the
key in general we do not think about
what is the value of the plaintext right
so therefore the two distributions that
is a plaintext distribution and the key
distribution they are independent okay
this observation is actually very
important so please commit your memory
that the plaintext distribution and the
key distributions are independent you
will use that in our future calculations
okay then we obtain the ciphertext by
applying the value of the plaintext and
also the chosen value of the key and we
obtain a ciphertext probability of this
distribution okay so now what the
attacker wants to do is that it wants to
compute the a posterior probability of
the plaintext
so the idea is as follows before going
into the complications the idea is as
follows so the idea is like this that is
when you obtain the ciphertext what you
do is that you have got certain values
of the symbols right so what you do is
that you guess the value of the key and
then you try to decrypt the ciphertext
okay I mean so the moment you decrypt
the ciphertext what you obtain is the
plaintext right so this plaintext right
what you obtain this also has got our
distribution right and that is called
the a posterior probability okay now if
your a posterior probability matches
with your a priori probability then
probably our guess of the key was
correct right but what if you obtained
for example like if you if your guess is
wrong then maybe when you go back then
the plaintext that you obtain does not
make any sense
okay so let us I mean if you are not
really clear we can make it clear by the
example of maybe a shift cipher
okay so consider a shift cipher so in
shift cipher what did we do every letter
was transformed by some other letter
right so for example it could be a shift
right may be a fixed shift or maybe are
not a fixed sheet but we can we had
basically done some transformations
right so therefore for example
there is a legible or other meaningful
english-language text contact consider a
paragraph of meaningful english-language
okay so then we apply ship cipher which
gets transformed into another set of
alphabets which essentially does not
make any sense right so what did we do
for our cryptanalysis we essentially
guessed the value of the key and then
decrypt it back right so when we decrypt
that we can what we can do is that we
can check what is the original plaintext
right that is the one objective also
right so when we go back we guess the
value of the key we go back and obtain
the plaintext right so now these
plaintext or this paragraph that we
obtain which is probably the plaintext
has got a probability distribution right
but that is actually based upon the
value of the key right after the
ciphering after the value of the
ciphertext that is given the value of
the ciphertext what is the probability
distribution of the corresponding
plaintext so this probability
distribution is defined as the a
posterior probability now if your guess
of the key was correct for a shift
cipher then that paragraph would have
definitely made a sense right would have
been a meaningful text nobody encrypts a
meaningless text right that is the basic
assumption so if somebody encrypts a
meaningless test then I am really not
bothered right so so therefore the idea
is that if that makes sense that means
essentially the probability distribution
that we obtain in the corresponding text
should essentially match with our non
normal English language right so
therefore in that case my approach
steady probability matches with the a
priori probability right and if that is
so then the value of the key is correct
right so do you understand the idea
behind this so therefore there is a
definite idea while Shimon postulated
this right so therefore essentially it
tries to explain mathematically what we
did for our crypt analysis right yeah
for example English language plaintext
all of us know right so the adversary
also has a fair amount of idea of that
right so the idea is that access to that
I mean the adversary has an access to
that as well it has also access to the
encryption function
okay so I'm repeating this because it
should go into our mind right so for
example now consider that the
probability distribution on P and K K
induce a probability so this we have
understood right that the probability is
distributions on P and K that is a
plaintext and the K induce a probability
distribution on C which is the
ciphertext right and what is the
ciphertext we can denote as follows like
for a given K C KX is equal to e K X
where X belongs to the corresponding
plaintext right so this is symbol so the
question is that so this is a
fundamental question does the ciphertext
leak information about the plaintext
right
so therefore given the ciphertext Y now
what we shall do is that we shall
compute the a posterior probability of
the plain text okay we denote that by PP
x given y so you understand this so what
is this symbol called this is
conditional probability right so
therefore we apply the principles of
conditional probability and we can
actually compute this value right so PPX
given Y and see whether it matches with
that of the a priori probability of the
plaintext right so if this matches with
the a priori probability of the
plaintext then probably my key is
correct right so therefore if we would
have wanted a proper amount of security
or what we would say as a perfect
security then we can actually denote
this as follows
you would have written like PP x given Y
okay that is equal to P P X so what does
it mean so this is the basic idea of a
perfect secrecy or perfect security what
does it mean
yes okay okay so therefore I really do
not know what to do so the idea is that
I don't know why this is not shown there
okay so let us continue I will try it I
mean what I am trying to say to you is
that PP x given Y is equal to P P X okay
so therefore probably I had written out
here somewhere so PPX given Y is equal
to P P X okay so which means that for
all X given Y given belongs to P and for
all Y which belongs to C okay this
result holds that is a cryptosystem has
got perfect secrecy if this is the case
okay
and what does it mean it means that the
a post it means that essentially given
the value of Y okay
the probabilities distribution of X is
indistinguishable from the probability
distribution of X when you are not given
any value of y so which means what which
means that a ciphertext Y is not giving
you any additional information right so
you see that slowly we are trying to
understand the meaning of information
right or the meaning of uncertainty so
information and uncertainty are quite
related right so we are trying to see
how those things are formally described
mathematically described yeah the owner
and understood okay so they will see so
what I am trying to say is that suppose
consider in size simple shift cipher and
consider that this is the probability
distribution of X okay so that is I have
described by P P X that is a normal
English language description right so
now you consider that you have done a
shift cipher so which means what you
have got a Y ciphertext so now I am
saying to you that given this
distribution of Y whether the now what
you can do is that you can guess the
value of the key and obtain back the
plaintext right that is nothing but so
the probability situation now that you
obtain is
v X given Y so if these two things so
that is what I was trying to say if
these two things match right then
essentially the means that this Y is not
leaving you any extra information
because even then it is still the same
right it is not giving you any
additional information right so let us
talk let us I think get I mean we I
think this will get clear with the help
of an example so therefore let's see one
example so therefore consider this is
the crypto system this is just a sort of
diagrammatic representation of a crypto
system so you see that these are very
simple transformation which says that
your plain text comprises of the letters
A and B okay and your cipher text
comprises of the letters or symbols 1 2
3 & 4
ok so what is the transformation the
transformation says that you can start
with a and if your K is K 1 then you go
to 1 if your K is K 2 then you go to 2
ok if your K is K 3 you go to 3 right
similarly the other transformations so
what you see is that if your plaintext
is B then also you get some other
mappings like 2 3 & 4
okay so therefore this is the
corresponding mapping that we are
concerned with so now let us try to
understand certain things about what we
have just described okay so so for
example considered that your plain text
which forms the set of P equal to a B
okay has got a probability distribution
so which means your a has a probability
distribution your B has a probability
distribution right say essentially
follows a probability distribution right
so therefore a has a probability of
occurring and B also has a probability
of occurring so what is the probability
of occurring of a it is say 1 by 4 so
this is given okay so what is the
probability of occurrence of B it is 3
by 4 note that of course I mean the
priority of occurrence of a plus the
probability of occurrence of B is equal
to unity okay so this is obvious because
a and B are the only possible texts
right take symbols so what is the value
of K the K could be K 1 K 2 and probably
K 3 also okay so this is a mistake here
so therefore so consider that suppose
there is
a key called k1 and the probability
distribution of k1 is half okay and the
probability distribution of K and then
the priority of occurrence of k2 and k3
are same so what is that it is equal to
1 by 4 so what is the ciphertext aquatex
is 1 2 3 and 4 so now the question is
what is the apostate a probabilities of
the plaintext given the ciphertext from
C so it means that you have been
provided the corresponding ciphertext
and the question is what is the Apostoli
probability of the plain text so which
means what is the probability of
occurrence of say a or b once you have
been given say the ciphertext is one or
two or maybe three or four okay so we
will consider one such case now this
encryption function is open represented
by this table also okay so you see that
a is the plaintext k1 is the e then your
cipher text is 1 similarly you can also
check other such mappings okay is this
clear so I will keep this figure and I
will try to compute the value of the the
opposite e probability as follows okay
so therefore first of all let us try to
understand what is the probability that
one occurs are the ciphertext so what is
the probability so you see that one
could have occurred only from a in this
mapping right so that means we would
like to multiply because you because I
already told you that the plaintext
distribution and the key distribution
are independent distributions ok so in
order to obtain the probability of one
we can simply multiply the probability
that a occurrence of a multiplied with
the probability of the key k1 so what is
the probability of a it is equal to 1 by
4 and the probability of occurrence of
k1 is 1/2 so we multiply 1 by 4 with 1/2
and obtain 1 by 8 X that is the
probability of occurrence of 1 similarly
we can also obtain the probability of
occurrence of 3 right it is slightly
more complicated because 3 can occur
from a as well as B okay but in this
case you see that this a and this B are
two exclusive cases right so therefore
we can apply the theory of our theorem
of
total probability and what we can do is
that we can multiply the probability of
occurrence of a with the probability of
occurrence of k3 and add that with the
probability of occurrence of B
multiplied with the probability of
occurrence of k2 right so this is simple
right so what we can do is that we can
just simply multiply 1 by 4 with 1 by 4
ad that means the product of 3 by 4 and
1 by 4 and this works to 1 1 by 4 right
so this is actually 1 by 16 plus 3 by 16
not 1 by 1 so it is equal to 1 by 4 so
likewise I can also compute the other
probabilities right so you see that we
can obtain the probability of the
ciphertexts right as follows but our
question is what our question is to find
out the probe as appro Apostoli
probability which means say given the
ciphertext is 2 I would like to compute
what is the probability of occurrence of
a right so this is quite simple right so
if I say you for example that the
ciphertext is 1 and ask you what is the
priority of occurrence of B what is
answer it is 0 you can easily compute so
you see that does it match with the
probability of occurrence of B no so
which means that this is not a perfect
cipher right so here is a simple check
but we will try to compute a little bit
complex situation which says that what
is the Apostoli probability of a given
that ciphertext is - okay we just try to
understand this complicated thing
although we have easily understood that
this is not a perfect cipher why because
we have to essentially go to the
generalization right so generalizations
are always complex equations so in order
to understand that it is interesting to
what with a simple example ok so let us
consider this for example that suppose
your PP a given 1 is 1 and your PP be
given 1 is 0 right so this we have
already understood I guess right
that is your if your plaintext is one
your ciphertext can be a and that
occurrence probability is actually 1 and
if your plaintext is 1 then the
occurrence of B as a plaintext is
actually 0 okay so you would like to
compute this also that is what is the
appositive probability that
of course as a plain text given to as a
ciphertext okay so you know that these
two can actually come from to blend text
it can come from a as well as it can
come from B okay so the two can come
when the plain text was a and the key
was k2 or when the plain text was B and
the key was k1 okay so another question
is given two we need to compute the
probability that it came from a right so
is it that of choosing k2 is the
probability same as that of choosing K
to know because we see that there are
other mappings where k2 has been chosen
where two is not the result right for
example this one you see this mapping
the k2 is chosen but actually I've ended
up with three as a ciphertext right so
it is not equal to that of choosing of
the k2 right so so therefore how do we
compute that so therefore let us see I
mean for example these two can appear
with the probability as which key which
we can work out as follows by having a
as a plaintext and k2 as the key right
so therefore a is a corresponding
plaintext and k2 is the value of the key
so what is our probability so we know
that we have to we can multiply the
probability of the plain text and the
key because they are independent so it
is the product of 1 by 4 and 1 by 4 and
it walks to 1 by 16 you understand that
because the priority of occurrence of a
is 1 by 4 and K 2 as the key is also 1
by 4 so you multiply them it is 1 by 16
okay the other case could be by having B
as the plaintext
okay and k1 as the key you see that the
other operation the other chance could
be that B was the plaintext and k1 was
the key right because k1 is chosen so
what is the probability of occurrence of
B it is 3 by 4 and what is the priority
of occurrence of k1 it is half so we
multiply them and we obtain 6 by 16 so
what is the total probability that 2 can
occur it is 7 by 16 right so we are
basically broken up the possibilities
into two cases right so what is our
desirable case now our desirable case is
that 2 has occurred as a ciphertext and
it has occurred from a so which is the
first
and you see that by having a as a
plaintext and k2 as a key what we have
done is that we have obtained two from
the plaintext a and that is precisely
what we want right we want what is the
priority distribution of a given that
two is your ciphertext okay so what we
do is that we divide 1 by 16 by 7 by 16
and we obtain the value of 1 by 7 right
so so I guess you understand that we can
now generalize this also like consider
any set of plaintext
and any corresponding set of ciphertext
and any set of keys of course so we
would like to generalize this idea of a
posterity probability okay and this we
can do by the help of this equation ok
so do you understand this equation so
you see that what it says as follows so
it basically tries to compute the value
of PPX given Y so this is what exactly
we are doing in your motto example right
so the denominator is all possible ways
how you can actually obtain Y because Y
is the ciphertext okay so you remember
in the previous case what did we do we
essentially took that corresponding
ciphertext and decrypted them by all
possible key value of values of the key
and went back to the corresponding
plaintext right and then multiplied with
the probability of that plaintext okay
so you see what I am saying what I am
saying is that in order to compute this
total probability that is of occurrence
of 2 what we did is that we took for
example any key like for example choose
k1 okay and decrypted these two with k1
when back to the corresponding plaintext
and multiplied with the probability of
the plain text okay and again choose K
to multiply main obvious the probability
of K 2 and then decrypt it and go back
to a and multiply with the probability
of a right similarly we can do it for
all possible keys right so that is
exactly done here so in this case you
see that you take you take the
corresponding ciphertext Y you decrypt
them by all possible keys multiplied
with the probability of the size I mean
corresponding plaintext and of course
multiplied with the probability of the
key right and then do a sigma over all
possible search keys right and your
interesting case is that is the fact
that you have that your
excess occurred as the plaintext and you
essentially multiply them with all
possible keys which essentially takes
you from the value of x to the value of
y right so essentially it's so therefore
this is exactly what we have seen in the
previous example okay
is this generalization clear to us yes
okay so therefore so that so now
essentially we know how to compute the
value of PPX given Y and we essentially
do I think I'm already defined but I
mean given given you the idea but this
is a formal definition it says that a
cryptosystem has got perfect secrecy if
the value of PPX given Y is equal to the
value of PPX for all x given belongs to
P and all for all Y belongs to C now the
value of PPX we already know we can
engage this previous equation to
calculate the value of PPX given Y
because you see that on the right hand
side everything is known to us we know
the value of the key we know the value
of the I mean the probability
distribution of the plaintext as well as
the plaintext I mean the probability
distribution of the key and therefore we
can use this equation okay because we
also know the mapping that is we know
the decryption function so we can use
this formula to calculate the value of
PPX given Y okay and check whether this
value of PPX given Y matches with the
probability of PPX if PPX given Y
matches with VX then we have got perfect
security okay so that is the idea so
that informally it means that a
posterior probability that the plaintext
is X given that Y the ciphertext Y is
observed is identical to the a priori
probability now the plaintext is X okay
so that is the definition of perfect
security okay so now let's see when one
in some examples where we can have
perfect secrecy okay so consider a
simple example of a shift cipher so in a
shift cipher what we did you know in a
more I mean what we have seen in our do
it not so simple shift cipher if you
remember we had taken a a and we have
mapped them to any other possible
outputs right so there are 26
possibilities for
first letter the second letter B maps to
any of the symbols except what a has
been transformed to so there were 25
such possibilities so if we multiply
keep on multiplying in such a fashion
then the size of the key is equal to 26
factorial we have seen that right so in
so what we will try to see here is that
if each possible mapping is chosen
randomly then shift cipher achieves
perfect secrecy okay so we will try to
use our previous formulation and we will
try to establish this fact okay so
suppose the 26 keys in the shift cipher
are used with equal probability so what
means that that means that each
plaintext I mean rather each key
occurrence of each key has got a
probability of 1 by 26 right so then for
any plaintext distribution the shift
cipher has got perfect secrecy so which
means that actually we are not bothered
also what is the plaintext distribution
okay and we can still achieve perfect
secrecy right so do you see how so you
see that your P K and C can be set to
form the set Z 26 ok so Z 26 we have
seen that it is a set of integers from 0
to 25 right so so your K therefore you
immediately understand lies between 0
and 25 and your function is very simple
it is just X plus K mod 26 so idea is
that if for each symbol of the plaintext
if you choose the value of the key at
random that is any mapping you can just
choose okay arbitrarily then essentially
and if you obtain the corresponding
value of the ciphertext okay so then the
question is whether this gives you
perfect secrecy right so which means
that when you choose so it means that it
means you should try to understand this
fact that what we are saying is not such
a scenario in which for all the
plaintext we are using the same key it
means that for each symbol okay that is
each symbol which you want to transmit
secretly
you have to essentially choose the value
of the key also at random right so for
example there is a
later like say abracadabra and if you
have to encrypt say ABC like so on then
for a you have to choose the
corresponding key at random for B also
you have to choose the key at random for
C also you have to choose the key at
random okay so it does not mean that for
the entire trend that we are using the
same key right so for each symbol we are
choosing a value of key at random so
what is the what you see is the
practical implication the practical
implication is you see the practical
problem the practical problem is that
for each symbol you are choosing a key
at random so in order to decrypt also
you require the same key right so you
immediately understand that you have to
transmit lots of keys okay and it is
actually in this case the same as the
number of the plain text that you want
to transmit right so if you know how to
transmit the key secretly right then why
not do the same for the plaintext also
right so the even though you obtain a
perfect secrecy a notion of perfect
secrecy but that is not practical right
so so we will try to first establish why
it is a perfectly secured cipher and
later on go into a another case where we
actually obtain a perfect secrecy it's
called a one-time pad and then talk
about its practical problems so this is
the mathematical formulation it says
that PPX given Y we have already seen
this is equal to P px multiplied with PC
y given x divided by PC Y okay it is the
same thing as what we have seen in the
previous equation right so it is a so
the denominator is the probability that
Y is occurred as a ciphertext and the
numerator says that X has occurred as a
plaintext and that has been multiplied
with the probability that Y has occurred
given X is the plaintext right right so
can we understand what is the value of
this PC Y given X it is the same as the
probability that the key has been chosen
and that key is equal to Y minus X mod
26 right so you see that when we had
computed the value of PPX given Y that
was not equal to the value of the
probability of the key we discussed that
right
but in this case it is equal because if
we choose the value of the key to be Y
minus X and if your plaintext is X then
obviously your cipher text is y all
right
so therefore this probability you can
denote by these symbols it says that you
can actually multiply with the
corresponding value of the key okay so
you see that PC Y given X is equal to
the value that is equal to the
probability that I mean you have to
basically choose the fact that the key
is equal to Y minus X mod 26 what is the
probability that the key is equal to Y
minus X mod 26 and what is the
probability that is 1 by 26 because we
have assumed that each key is being
chosen at random right
similarly we obtain the value of the
corresponding value of the Y according
as the ciphertext so what is the
probability that Y of words in the
ciphertext so you choose all possible
keys and you decrypt your Y okay by
using your decryption function multiply
that with the corresponding I mean
corresponding value of the key being
chosen right so what is the value of the
key 1 by 26 okay and what is the value I
mean what is DK DK y I mean what is some
probability right so you can keep it p
py minus k but when you take the Sigma 1
by 26 comes out and you have got a
summation over probabilities so what is
that equal to it is equal to 1 so you
have got 1 by 26 so now you see that the
result is established because pCY given
X cancels with P CY both of them are
equal to 1 by 26 right so if these two
things cancel then you have got PPX
given Y is equal to P P X so what does I
mean you have got perfect secrecy why
and because you have passed any
probability of x given the value of y
matches with your a priori probability
of X right so if we can do this part
shift cipher we can do it for any given
cipher we can basically what we have to
do is that way to compute these values
of probabilities and try to see whether
we get a match right so this was
necessary
example okay so you can if you see your
Stinson's book there are several
exercises given and I will also give you
one as an exercise so you can just
practice and if you can do it for one
probably you can do it for the others as
well so basically now let us try to
think of of a theorem or let us try to
establish a theorem it says that any
encryption function okay you can or any
crypto system essentially can be denoted
by a five tuple right you have got PC K
so what is that plaintext ciphertext and
the key and your encryption function and
your decryption function right if these
five things are defined then you have
defined a crypto system right so let us
consider the case that the size of the K
size of the C and the size of the
plaintext are all the same that is your
cardinality of your key and your
cardinality of the ciphertext and
cardinality of the plaintext are the
same okay so the crypto system offers
perfect secrecy if and only if every key
is used with probability of one by
module okay okay so in your previous
example and there were how many keys
there were 26 keys and the occurrence of
each key was 1 by 26 and that led to the
fact that we had a perfect secret system
right perfectly secret system so and for
every X which belongs to P and for every
Y belongs to C there is a unique key so
that means that given an x and y there
is a unique key which takes X and maps
it to Y right so we have to establish
this fact that is for every x and y you
choose or every couple that you form
with x and y that is a given plaintext
and a given ciphertext you have a unique
value of key which defines this mapping
okay so we will try to establish this
fact ok so I will although I will not
prove but you can easily understand that
an equivalent definition of perfect
secrecy will be PC Y given X is equal to
PC why I leave it to you as an exercise
you can actually prove it by by theorems
of conditional probability okay it is
very simple straightforward so therefore
it says that the ciphertext probability
of Y is the same as the probability of
Y given X as the corresponding plaintext
okay so the SIF perfectly secret a
scheme as to following the above two
equations okay and both of them are
equivalent if you can prove any one of
them the other one is proved equivalent
Li right so so we observe one fact so we
see that since PC Y given X is equal to
PC Y ok that is if you see this equation
it means that if you fix the value of x
for example as a plaintext then your PC
Y given X is equal to PC Y right and
your PC Y is greater than 0 because if
that why I mean the occurrence of Y the
probability of occurrence of Y would
have been 0 then why we would not have
kept in the ciphertext set right so that
means for some ciphertext at least for
some plaintext at least we have that
corresponding ciphertext right so
immediately which means that this leads
to the fact that PC Y given X is also
greater than 0 right so what I am trying
to say that since PC Y is greater than 0
and if we have a perfectly secured
cipher then PC Y given X being equal to
PC Y this is also greater than 0 right
so therefore PC Y given X is greater
than 0 okay so which means that for
every ciphertext there is a key K such
that Y is equal to ek X right so which
means that for every ciphertext there is
a key such that Y is equal to ek X ok so
if you think in the terms of a diagram
ok you could have understood that in
this in the corresponding ciphertext
said there is no single point which is
not being mapped ok there is not any
isolated point which is not mapped to
any plaintext okay so therefore your
plaintext comprises of what X 1 X 2 and
so on symbols right your ciphertext also
comprises of y 1 y 2 and so on symbols
right so there is not a scenario where
there is a ciphertext symbol okay say
some sales corresponding consider any
why why I for example which is not
mapped to any plaintext X I okay you
understand that
so that means that for every ciphertext
there is a key there is one key at least
which will take it to that X B that any
X okay so what does it mean it means
that the size of the key set is
obviously at least equal to the value
size of the sub ciphertext okay it can
be greater than that also but it is at
least equal so therefore what I am
trying to say is that for perfect
secured ciphers the size of the K or the
cardinality of K is more than the
cardinality of the ciphertext
okay right so you can understand again I
mean again reading this the fact what I
am trying to say is that for every
cipher text Y there is a key K which
define this this mapping okay so that
means there has to be the number of the
keys has to be at least equal to the
numbers of the cipher text right for
every ciphertext symbol you have a
separate key you will define this
mapping so number of keys is obviously
equal to the size of the Y of size of Y
it can be more than that also but at
least equal right
so therefore the size of a key is
greater than the size of the C in our
case consider the size of K and the size
of C are the same okay
so thus there is no ciphertext so
therefore now we can actually understand
from here also that there is no
ciphertext Y for which there are two
keys which take them to the same
plaintext Y now because your what is
your size what is how can we define your
ciphertext set see you can define your
ciphertext set C by the set that you
basically choose any plaintext X and you
transform that by E K X and you obtain
the ciphertext right so basically that
suppose if I fix the value of x I could
have chosen all the possible values of
keys and I would have obtained the
entire cybertek set right so that we
know that if we say that so this is your
size of the cardinality of this set is
the same as that of your ciphertext
right now if this is equal to the size
of the value of the set of
kay that is it is the same as a side of
K it means that there are no two keys
which are distinct like K 1 and K 2 such
that e K 1 X is equal to e K 2 X because
in that case 1 cardinality would have
been less right one sets one of the sets
cardinality would have been lesser than
the cardinality of K right and what we
have said is that if we assume that the
size of K and the size of C are same
then essentially there is no two keys
which are distinct which will take them
to the same plaintext okay thus there is
exactly one key which defines the
mapping from x and y ok so so therefore
I mean this is the basic definition so
we see certain definitions proper crop
out of the idea of a perfect secured
cipher ok so what are those those
definitions one one important point was
that your Apostoli probability of your
plain text matches with the apriority
probability ok the second definition was
that equivalent definition was that PC Y
given X was equal to PC Y so that is
also the same thing that the a priori
probability of your cipher text is the
same as the a posterior probability of
your cipher text ok and the third
important thing which we see is that if
your size of plaintext key and the
cipher text are the same okay
then essentially for every plaintext X
and for every ciphertext Y for any
ordered pair like this there is a unique
key which defines this mapping right so
there are no to such keys like k1 and k2
which will take X for example as a
plaintext and we will map it to the same
ciphertext ok EK 1 where K 1 is not
equal to K 2 we cannot have a scenario
where ek 1 X is equal to ek to X because
if that be the case then your size of
ciphertext would have been lesser than
that of the size of the key right but
what we have said is the size of the
ciphertext is equal to the size of that
right is this part clear so we will stop
at this point and essentially break for
few minutes and come back with it with
the definition of something which we
call
as the one line that's