Application of Elliptic Curves to Cryptography - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

so in the last class we have studied
about elliptic curves and their
definitions so in today's class we shall
concentrate on how to apply elliptic
curves to cryptographic operations so in
today's class we shall essentially cover
these areas like what is the relation
between elective elliptic curves and
cryptography discuss about an El Gamal
type of encryption algorithm in context
to elliptic curves so the other
important thing that is needed is how
essentially do we take a message and
encode that into the elliptic curve so
we will see a very simple algorithm to
do so and also the corresponding
decoding that means given a the
corresponding point how do we get back
the message then we shall discuss about
the diffie-hellman key exchange in
context to elliptic curves and then we
shall address like why do we at all use
elliptic curves because we have studied
RSA and public key ciphers which are
based on discrete logarithm problems so
what is the purpose of elliptic curves
and what is the underlying hard problem
behind little curves so we shall just
discuss certain issues in this context
so first of all to start with public key
ciphers as we have seen there are two
important requirements in public key
ciphers one is secrecy and other one is
authentication of information so as we
know that in any public key cryptosystem
these are provided by a pair of keys
right so if you know that if you want a
if you want to apply your public key
cipher for giving you secrecy then also
you use a pair of public key and private
keys and similarly if you want to use it
for authentication you use another pair
of public key and private keys yeah the
only difference when you are using it in
context to security and when you are
using it in context to authentication is
that how do you use I mean which key do
you use for what reasons like for
example when you are interested in the
motivated in the security of the the
secrecy of the information then you use
the public key for encrypting right the
sender you
the public but the receiver decrypts it
using the private key similarly when you
are using it for authentication the I
mean you can use the same public key but
you have to use it in the other way that
is if you want authentication then you
have to use the private key for sending
the data and use the public key for
verifying right so similar to that we
can also use so that is basically shown
in this diagram that there is a source a
and there is a destination B and the
message source wants to send X which is
a message and it wants to send it to the
destination ensuring that both secrecy
of the information and the
authentication of the information is
maintained so for that source a chooses
a pair of messages
I mean prepared of keys and for
encryption algorithm there are two
stages of the algorithm one is the
encryption algorithm pollution and the
public key encryption has been used for
secrecy the other one is used for
authentication
okay so when you are using it for in
encryption then you are using the public
because you have to encrypt the data so
you you you essentially choose the
public key and you encrypt the data and
send it to the receiver but for the
author for authentication you do just
the opposite that is you essentially
choose the public and then the private
key for saving and similarly you want to
verify so you in order to verify you use
the corresponding private key so
therefore for if you want to send it for
authentication then you see that
you have essentially chosen the public
key for performing your authentication
right that means that sort of the
private key for performing or signing
the data and for verifying you use the
corresponding public key but if you want
to use it for secrecy of the information
then you use just out the keys but in
the same keys or the same similar pair
of keys but in the other way that is
what you do is that you choose the you
choose the secret you choose the public
key for performing your encryption
operation and you decrypt the
corresponding ciphertext by using the
corresponding private key right because
anybody should not be able to decrypt
so therefore the secrecy of the data is
in short because you know that the
secret key is only that is assumption
right there is a secret key only B has
the corresponding secret key
so therefore the private key and
therefore it can only decrypt and
similarly the authentication is ensured
because the very the verification if the
verification is successful it shows that
and based on the assumption that only a
has the corresponding private key so he
knows that this particular message
digest can be only generated by the
source a that is since the no I mean
apart from source a nobody has the
corresponding private key therefore only
a can sign this message right so
therefore the authentication is also
ensured in this fashion so this is a
very customary operation of how you
basically so there are two important
parts one is the encryption and the
other one is authentication so what we
understand from here is that what we
have studied previously is that you can
use any encryption or any public key
encryption algorithm and you can
actually achieve these goals of
encryption as well as authentication
okay so for encryption you know that
there is a public key that is there is a
public key ring so if you want to
communicate with anybody for example if
you want to communicate with Alice then
from the public key ring you choose the
corresponding you choose the
corresponding key that is for the
corresponding public key for Alice and
you generate the ciphertext and the
receiver since it has the corresponding
private key decrypts the message and
obtains the corresponding plaintext when
you are doing when you are doing the
authentication then what basically you
are generating the signature so you take
an input and you sign it by your own
private key and you send it and you see
and if this receive what is expecting
the message from Bob then it chooses the
corresponding public key from the public
keyring and decrypts it and obtains the
plaintext message so you see that both
this essentially uses the same public
key cryptography ring but the point to
be noted here is that when you are using
it for encryption and when you are using
it for authentication the public key
ring is in the first case present in the
receiver I mean the sender's part and in
the second case it is present in the
receiver spot
that is a small thing which is to be
kept in mind now there are various
arguments about whether you should do
the encryption first or whether you
should do the authentication first okay
so so that essentially is a matter of we
can argue on that but this is the basic
way how you can actually choose the
public key and you can actually perform
either if you want to use one want to
use it for the secrecy or you want to
use it for the authentication of the
information
so therefore what is elliptic curves we
have studied the elliptic curves is
essentially I mean elliptic curves is
basically a certain set of curves that
is essentially what we have studied in
the last class so now the question is
what is elliptic curve cryptography so
elliptic curve cryptography is nothing
but a public key cryptosystem just like
we have studied RSA we have studied El
Gamal so it also has a public and a
private key okay and the public key is
used either for encryption or the
signature verification and the private
key is used for decryption or for
signature generation so elliptic curves
are used as an extension to other
current crypto systems so therefore you
can also have elliptic curve
diffie-hellman key exchange you can have
elliptic curve digital signature
algorithms so wherever you have seen the
prints the previous applications of
public key ciphers you can have similar
applications here also but these are
actually based on certain curves which
are known as elliptic curve so they are
having cubic curves which we have
studied in the last class ok so now we
shall study that how do we apply these
elliptic curves to generate a crypto
public key cipher so the central part of
any crypto system which involves
elliptic curves is the elliptic group
okay so we have studied that if you want
to generate elliptic groups then for
that you know in order to do that we
actually define certain operations so
the operations means those we take two
points on the elliptic curve and we
define what is meant by addition on
these two points right so we define what
is meant by point addition and what is
meant by point doubling okay so all
public key cryptosystems have some
underlying mathematical operations like
if you want for example choose RSA then
you have exponentiation
right you know that you basically do a
modular exponentiation and all public
key ciphers essentially relies upon
certain things which are assumed to be
one-way function
we are easy to compute what which are
difficult to invert okay so in context
to RSA we have seen that the heart
problem of the one-way from problem was
essentially what essentially was the
factorization problem that is if I can
take two if there is a large product or
if there is a large composite number
which is which can be factored into two
large prime numbers then it was believed
that it is difficult to factorize these
modelling right so that was the
Assumption on which the RSA security was
relying on so when we studied about the
the el-gamal cryptosystem which are
based upon the finite field for example
FP or any other finite field for that
matter then it was based on the
something we just called as a discrete
log problem so it was known believed
that it is easier to easy to compute
given a public Manu DG and given a
secret modulo X right it is easy to
compute G power of X modulo P but from G
power of X modulo P it is actually
believed to be difficult to compute the
value of the exponent X that was the
Assumption on which the el-gamal
cryptosystem was based on so similarly
here also in elliptic curve cryptography
we also have something which is then
similar or analogous to the discrete log
problem and which is called as the
elliptic curve discrete log problem so
this essentially is again realized
relies on how do we do the point
addition and how do we do the point
doubling okay so the underlying
mathematical operation on which these
public crypto systems on based on
elliptic curves are based on are
actually something which is called as
point multiplication so what we do is
that we take a elliptic curve and say
for example consider any lip T curve for
that matter okay suppose this is 1 and
if T curve so what we do is that we take
a point P on this curve and we take
another point Q on this point and we do
a point addition so that is what we have
studied in the last class right so
therefore this essentially intersects
the curve at a third point and the
corresponding reflection of that point
is a sum P plus Q ok so this is known as
the sum P plus Q similarly if there is
these P and Q points converge and there
is only once
single-point then what we do is that we
draw a tangent at that point and we
reflect that point so that was called
the doubling operation so before if this
P and Q converges at a point say call it
say W then this is nothing but twice of
W because that is W plus W okay so this
is basically that operation of point
addition and point doubling okay now in
elliptic curve cryptography what we
essentially do is that we choose a
scalar quantity say call it lambda and
there is a base point which we call as
say point P okay so the whole point is
how do we compute lambda into P so that
is a basic operation on which will take
curve cryptography realize that is how
do we compute this value of lambda
multiplied by P so one obvious way of
computing lambda into P is by taking P
and by adding it lambda times right so
we take P and we keep on adding them
lambda number of times so what we can do
is that we can take a point P and P plus
P means it's a doubling operation on P
then whatever upper output we get again
we add that with P and we keep on doing
that lambda a number of times so that is
essentially something which is called as
the scalar multiplication which is
central to what is known as elliptic
curve cryptography so whether we want to
use it for encryption whether we want to
use it for key exchange this is the most
important and center operation on which
elliptic curve cryptography is based on
so so the generic procedure of doing an
elliptic curve cryptography is that both
parties agree to some public known items
for example the elliptic curve equation
so we have studied that the equations or
the form of Y squared equal to X cube
plus ax plus P that's an possible
elliptic curve equation similarly we
have got a generalized Weierstrass
equation so if I give you the values
that is the values of the curve the
constants then you essentially know the
corresponding card
okay so it is believed that everybody
the sender and the receiver and even the
adversary knows the power of equation
okay so the elliptic now you have to
basically define an elliptic group okay
so the elliptic group computed from the
elliptic curve equation and a base point
B which is from the elliptic group and
similar to something which is collagen
as what we have seen as generated used
in the quadratic in the context of the
previous public key ciphers
okay so similar to that we have got a
base point B which is again a public
domain information okay so therefore
these are the public domain information
the values of a and B okay so what is a
and what is with is that if you remember
the vaster equation Y square equal to X
cube plus ax plus P so therefore those
two a and B will be important in
understanding what is the corresponding
curve right so based upon that they have
got various varieties of curves we have
got random curves and there are other
forms of garbs also okay so and
similarly the prime P so therefore the
corresponding elements of the elliptic
curve are based based on some field
right so therefore that field could be a
prime field so in this case we are
assuming that it is a prime field it
could be a characteristic two field also
like GF 2 power of M okay it could be
some essentially some complex sets also
but if I assume that for our purpose let
us assume that the underlying elements
on the derivative curve are chosen from
FP that is it is chosen from the field
which is generated out of numbers from 0
to P minus 1 where P is a prime number
ok so the elements on the curves are
actually chosen from 0 to P minus 1 ok
and I mean although they I did not say
explicitly all the number of points
which are actually there on the elliptic
curves they are actually finite so that
is a basically a finite set of points
which are there on the elliptic curve
okay so therefore you have got your FP
which is your set of numbers from 0 to P
minus 1 where P is a prime number and
then you have got some points which you
are actually choosing on the elliptic
curve so those are actually ordered
pairs like condition points X comma Y
where X also belongs to FP Y also
belongs to you okay
so basically it is a subset of the
numbers from ZP cross
right so it's a again it's a finite set
okay so it's a finite set of numbers and
a finite set of points which actually
are there on the actuality curve okay
and by our previous construction of the
addition and the definition of the
addition operation and the points those
elements X comma Y actually form a
mathematical group right along with the
point at infinity they form a
mathematical group okay so therefore if
I chase take all these points X comma Y
which actually satisfy this virus
equation those points along with the
point or infinity form are what we is
called a mathematical group okay under
the definition of the addition and the
doubling operation right so therefore in
this case what we are saying is that the
public known data items are the values
of a B and the corresponding prime T
these are public moments and similarly
there is a base point which is also a
public domain now each user generates
their public or private key pair okay so
what is the private key pair here so it
could be an integer X which is selected
from the interval from 1 to P minus 1 so
from 1 to P minus 1 the private key is
any integer X which is selected at
random okay and the public key is
actually the product of X and P B okay
so therefore what you do is that first
of all you I mean if you want to use it
right you first of all choose a
corresponding kind of equation so y
equal to X cube plus ax plus B and
whenever you are doing it there is a
modulo P right because these elements x
and y are essentially chosen from ZP
cross ZP okay and these things that is
your I mean the the corresponding
private key which you are choosing is
another number so although it is X but
it is a different X actually the secret
X okay so that is X which is chosen from
from the set closed interval from 1 to P
minus 1 okay and your public key
actually x multiplied by the base okay
so bees again another public parameter
which is the base point of the curve so
that is generally provided by a central
body so we for example we have got nice
curves so therefore they essentially
gives you these values of a B and so I
think it is better to make it this a and
small a and small V so this a this small
V and small a and this B is generally
provided by a central body
okay chosen cars so then this is the way
how you choose or calculate this private
key and the public okay
so immediately you know that from from
our previous discussions if this X
number is chosen from 1 to P minus 1 and
this public key value is public right so
therefore everybody knows this X into P
so therefore our whenever you are using
it for cryptography it is therefore
obvious that one should not be able to
know this private key right so therefore
it becomes immediate that from this X B
it should be difficult to get a
knowledge of X right that is a basic
assumption so how do you get X into B
that is by adding B X x right so the
repeated additions will give you X into
P and this problem of getting X from X B
is what is the basic assumption okay
again the central believed to be
mathematically a difficult problem on
which elliptic curve cryptography relies
upon okay so anyway I'll come to that in
more details so at least first of all
see that how do we do the basic
encryption operation okay suppose Alice
wants to send to Bob an encrypted
message so both agree on a base point B
so Alice and Bob creates a public
private key so what Alice does is that
it chooses a private key a and the
corresponding public key is P a which is
a B that is me being added a number of
times
similarly Bob's private key is again
small B and the corresponding public
keys be multiplied by Big B okay so now
you know that this public keys are
actually available to everybody right it
is aired in the public kidding so if
Alice wants to
essentially encrypt a message em then it
has to somehow convert this message or
encode this message into a point on to
the curve so I call it p.m. right so
therefore the first thing is that let us
say we can actually assume that okay it
said taking this M somebody can encode
that into the point on the clock okay so
therefore obviously one may ask that how
do we essentially take this message m
and encode them into the point PM okay
so there are various ways how you can do
so but one very simple technique is
shown here so you consider this curve Y
square equal to X cube plus X plus B
okay so the plane so one way could be
like this that is the plane takes as
their numbers and English or Roman
characters whatever you say from 0 to 9
and from 10 to 35 okay so suppose
therefore if I want to send this
character B then this B will be encoded
as the number M equal to 11 okay so they
are very simple way of doing so you see
that you choose a public variable say K
equal to 20 okay and you start computing
X which is equal to M into K plus I and
you vary i from 1 to k minus 1 okay so
therefore what I am doing is this that
is you choose this you know that this
value that is K is a public known value
and you want to send the value M okay so
what you are doing is like this that is
I want to send the corresponding value
of m equal to 11
that is what my letter the character B
indicates or is encoded as okay so I
want to send this value m equal to 11 so
what I do is that I start computing X
and I start current reading XS M
multiplied by a publicly known value say
call it 20 and I start adding some value
I to it okay and I will vary this i from
1 to K minus 1 so K minus 1 K being
equal to 20 is 19 okay I keep on varying
this I at one step okay so for example
in this case it is 11 into 20 plus 1 to
begin with when I is equal to 1 so first
of all
in the first iteration I is one okay so
you get a corresponding value of x right
so you remember that you are always
doing a modulo P right so there is some
P through which you are doing on which
you are doing a modulo P operation okay
so let it be some value essentially so
now if you get this value of x and you
know that there is a corresponding curve
equation so Y square equal to X cube
plus ax plus B you take this X and we
substitute that into the Y and you know
that this is again a modulo P so
therefore that means that this number
which you get should be a quadratic
residue because if it is so then there
is an integral solution for y okay so
that you can check by our techniques
that we have seen previously you know
how to check whether a given value is a
quadratic residue modulo P or not right
so therefore you can check the whether
it is a quad ratio modulo P if it is so
then X comma Y is a corresponding
encoding okay otherwise you again start
incrementing this I to the next value -
okay and now you know that it is quite
easy you can you can check that if I
start varying from 1 to 19 at least one
of them will ensure that Y is a
quadratic acid so if I keep on
increasing this like this there at least
one of them will be will be ensuring
that it is a quadratic residue okay so
that you can just think about why it is
so
so therefore TM is encoded as X comma Y
and the decoding is very simple the
decoding is you take this X you subtract
1 from it divide it by K and take the
floor of this fellow so that is your M
okay so you know that X minus 1 divided
by K and you take a floor of this this
will give you M so therefore this away
how you can get this value of M from
this pair of X comma Y okay so I'll give
an example on this that is suppose P
7:51 and a is minus 1 B is 188 and case
20 so let this be some arbitrarily
chosen values and your M is again 11
okay and I choose this X as X is equal
to M into K plus 1 okay so therefore
here if I change take this value a me
being 11 and K being 20 if you multiply
level into 20 and add 1 you get
222 is it correct there is a mistake
right
it is 20 into eleven plus one okay this
one so that is 221 right the 221
it is 221 right so therefore this is
please correct it this is two two one
okay so this is two two one but
correspondingly we can see that there is
no solution for y so if you take this
value of x and plug into the curve
equation then you will not get an
integral value of y so that you can
check again but this we can this you can
check your offline okay
so similarly so we continue like this
and you keep on incrementing the value
of this one two three and so on and you
will find in this case that when this I
is equal to four
then your X being equal to 224 and then
you will get that there is a
corresponding value y equal to two four
eight which is an integral solution so
that means that this m equal to eleven
can be encoded as 2 2 4 comma 2 4 8 okay
so now I want to obtain back the value
of M from this so what I do is that I
take this 2 2 4 subtract out of 1 and
divide it by 20 and then take the seal
of this then that is equal to 11 okay so
that is essentially how you get back M
from the pair X comma Y okay so now I
think this should be okay from clear to
us that is why there will be at least
one value for which this Y is I mean for
which this pair is a valid pair okay so
I am leaving that to you to think but
this is a very simple encoding technique
there could be other principles or other
methods which you can do the encoding
also okay so what is the probability
that you will get at least one such
thing I mean if you try keep on trying
it will be so on and you try k number of
times and at least one of them will be a
possible encoding that means the
probability is 1 by K right that is so
therefore we repeat this K number of
times you should get one solution and
the decoding is simple right decoding is
exactly gives you back the starting
message M so therefore once we have
solved this that is once we have done or
an obtained these
value of p.m. so this p.m. is the
encoded thing it is we have taken the
message m encoded it into the on to the
elliptic curves it becomes p.m. okay so
p.m. is again a point that is it's a
pair of X comma Y then I mean it's a
it's an X comma Y it's a Cartesian point
okay so now I want to apply and now
generate the cipher text so what I do in
order to generate the cipher text I have
to use what I have to use the public key
right so what I do at rather what Alice
does is that it chooses a random integer
K from the integer 1 to P minus 1 okay
so therefore we choose the random
integer from 1 to P minus 1 call it K
and multiplies it by whose public key by
Bob's public key okay so therefore it
tells X bob's for public key SPB and
multiplies it with k okay so it
multiplies k with PB and adds it with
p.m. so note that all these additions
are are defined on on the curve okay so
therefore you you choose this and the
other pair is K into B so therefore you
already had the base point B you
multiply it scale early by the
corresponding K which you have chosen
and you are passing this pair as a
ciphertext so this remembers us of the
el-gamal encryption right on which i
mean what we have seen previously this
is exactly similar to that therefore it
is called a new T curve tiptoe system
which is analogous to the el-gamal
cryptosystem ok so you choose PM and you
so therefore you add it to K into P B so
PB was your public key of Bob you have
multiplied with K and you have passed it
so now you can note that in this
particular exponent if you want to
obtain PM from this p.m. plus K into PB
then what do you need to obtain so the
cipher text has got p.m. plus K into PB
right and what is this is equal to PM
plus K into the secret right the secret
is B and multiplied by the base point B
so what was the other corresponding
compo
they're the other component was k-b
right so so if the so when Bob receives
it Bob receives the ciphertext and Bob
has B right Bob has B because b is what
B is the corresponding private right so
what Bob does is that Bob takes the
first component KB and multiplies KB
with the corresponding value of B so if
you do so that is if you multiply this
KB with B then what you obtain is
nothing but K into V into B and that is
nothing but K into PB right
so therefore Bob by using its own
private key can actually obtain the
value of K into PB and after that it is
simple because you have to just subs you
to subtract out these value and in order
to that so that you get the value of
p.m. okay so that is what is shown here
that is if you want to do the decryption
then you take this B and you apply it
over KB and then you just do this
subtraction operation to eliminate these
two terms and to obtain back the value
of p.m. so p.m. is what p.m. is the
encoded message on the elliptic curve
then again by using the previous
decryption or the decoding algorithm
rather you can actually obtain back the
corresponding value of M the message
right so this is quite analogous to what
we have seen so Bob then decodes p.m. to
get the message M so therefore you have
to do the final decoding to get back the
original message right so that is how
you are actually doing the operation of
encryption and decryption okay so now so
so we are obviously extended for
signatures or authentication know that I
am not actually going into and that is
quite straightforward rather the other
interesting application of elliptic
curves is in the diffie-hellman key
exchange okay so if we just recap that
is
that is what we have seen in context to
the finite field P that is there is a
generator a value alpha you choose alpha
power of X a modulo Q and obtain back
obtain Y a and send this Y a to the
corresponding user B right so what the
user B does is that the user B obtains
computes a YB by again choosing alpha
and raising it to some secret value call
it xB and sending it back to the user a
so what both user a and user B does
subsequently is that uses its own secret
value and raises YB to that power and
the other what B does is that it take
takes Y a which it has obtained from
user a and raises to xB and what we know
is that this value of the output value
is the same right so therefore then
that's that's a final shared or
exchanged key right we just used for
subsequent encryptions so we see that
the same thing can be done in elliptic
curves also so elliptic curve and base
point so therefore these are actually
the points on that curve so so what do
you want is that you want to generate a
XY and B X Y and then you want to do
some operation on this and similar
operation on this and the expectation is
that the output should be the same right
because and that follows from the
elliptic curve definition right so you
take B X comma Y which Alice has
received but Alice uses its own private
key a or randomly chosen value a and
computes a B X Y and similarly Bob
computes ba X Y and since a b and b are
same that is their commutative
operations you actually get again
another share okay so details is like
this that is you get a private you the
private key a for example Alice has a
private key a and a public key is P a
and similarly Bob as a private key B and
a public key as P V okay so what Alice
does is that Alice obtains this
corresponding value of B into Big B okay
and multiplies it with its own private
key as a so that is a into B into Big B
and that is same as what Bob computes
because but Bob computes is that Bob
tends aim to be from
from from Alice and then what it does is
that it raises it or multiplies it with
B and since a into B same as B into a
both these two values are same right
therefore this is the final shared key
of a into B into B Big B okay so that is
basically that you can also apply
lipstick cards to perform the original D
FilmOn exchange as well okay this is
simple right to the same same but I mean
what we have seen previously so now why
do we use ECC's okay so in order to
understand that we have to understand
that how do we analyze crypto systems so
obviously that if I want to say that way
that RSA is greater than ECC then we
have to compare the difficulties of
their underlying problems okay so for
example RSA is based upon the integer
factorization your D Phi element is
based on some problems which is disputed
I mean is actually based on the
defilement assumption okay and similarly
if you want to see the el-gamal
cryptosystem that is based on the
discrete logarithm problem okay and in
the peak of cryptography is again based
on a diptych curve discrete logarithm
problem so therefore how do we measure
their difficulty so we examine the
algorithms which are used to solve these
problems okay see for example here are
some values which shows that elliptic
curve cryptography sizes so therefore if
you compare for example here like 163
bits you will see that a 1024 bit RSA
key size is equivalent to that of a 163
bit elliptic curve key size so therefore
here you see that there is a significant
shortening or shortening of the key size
the key size is significantly short is
almost 1 is to 6 ratio okay and as you
are going down the ratio is actually
increasing okay so which means that if
you want to apply or rather develop
public key cryptosystems on resource
constrained environments then you RIPTA
curve is actually a more promising
public key cipher okay so therefore you
will find that if the device is a small
they have limited storage and they have
come
additional power restrictions they're
actually ehtekaf to photography's idea
okay and that's why it's actually trying
to probably I mean is being adopted
worldwide okay so therefore if you want
to apply for wireless communications for
smart cards develop online transactions
web servers that is any application
where security is needed but also I mean
it the the the place or the platform
lacks sufficient power storage and
computational requirements so therefore
this is very very motivating and very
useful for the present-day applications
okay
so therefore the difficulty of the heart
or the so the question is why
essentially RSA has got such a bigger
key size and the peak of cryptography
has a comparatively much smaller key
size okay so that in order to answer
this it has got to do with the
underlying hardness of the problem that
is what is the corresponding what is the
corresponding difficulty of solving the
inherent internal problem that is how
hard is it to solve the defilement
problem in elliptic curves and how hard
it is to dissolve the diffie-hellman
problems in FP okay so that that is the
basic question so your elliptic curve
security okay so therefore the question
is that the heart problem is analogous
to discrete blocks that is Q is equal to
K into P so the question is that there
is a point P and there is a point Q and
the question is that given K and P it
should be I mean easy to compute Q but
it is should be hard to find the value
of small K that is the scalar so that is
this problem is known as the elliptic
curve discrete logarithm problem okay so
in this case we know that K must be
large enough that is if K is small say
wall r2 obviously it is not difficult
but it becomes difficult when is K is
really large right so elliptic curve
security relies on elliptic curve
logarithm problem and it can be compared
to other problems that we know of so
this is the basic definition of elliptic
curve discrete large in problem more
formally so let a be an elliptic curve
over the finite field FP okay
let P & Q be points in this AFP okay so
therefore there is a unity curve and
there is there are two paws up those n
points P and Q and we are actually
interested in the elliptic curve
discrete logarithm problem okay
so therefore the elliptic curve discrete
logarithm problem is the problem of
finding an integer n such that Q equal
to M PS satisfied and is given this
value of P and given this value of Q how
hard it is to compute this value of
integer n okay so we did not this
integer n as n is equal to log Q base P
okay so that is the elliptic curve
discrete logarithm of Q with respect to
P okay that is the elliptic curve I mean
that is correct elliptic curve discrete
logarithm of Q with respect to P so now
we will see certain interesting
properties of this elliptic curve
discrete logarithm problem okay so one
of the problem one of the things is that
this log Q base P may not be defined
okay that is you may choose two points Q
and P such that this log Q base P is
actually not defined okay why because it
is not necessary that always you will
find that Q is P maintains the relation
that is Q is equal to M into P okay so
it may be that there are two points for
which Q is never I mean Q is never equal
to n into P for any integer n okay so
that is actually some something which is
to be kept in mind but the thing is that
we we actually are not really faced with
any problem because of this fact because
of the nature in which how we are
actually applying our elliptic curve
cryptography because whenever we are
applying elliptic curve cryptography is
by repeated additions right so then the
corresponding Q and P that we are
generating or that we are concerned of
actually has got this glacier okay but
it is not true for any arbitrarily
chosen given P values okay so therefore
since there are fine I mean so therefore
it is important to be kept in mind that
is it is not necessary that for any Q
and
P this elliptic curve or this discrete
logarithm has to be defined okay but the
manner of the fashion in which we are
applying this elliptic curve okay that
we don't we do not face any significant
problem okay so now there is the other
important thing is that there is not a
single value for which this holds that
is it is not true that this Q equal to
NP is that is n into P is true only for
one unique value of M there can be
multiple solutions to this equation okay
so why let us just try to see this
because this is quite straight forward
that is suppose you know that you choose
any point P okay there will exist an s
such that s into P will be equal to O
okay so that is that follows from the
basic property that we have that with
that is of the underlying group that is
if you keep on adding P then there will
exists
one such integer s for which a seem to P
is equal to the identity of the group
okay I am the least such value for which
this holds is actually called the order
of the point P okay so now the the other
fact that also is important is that you
know that the points on the elliptic
curves are actually finite set of points
so if we just take any point P and you
consider at P 2 P 3 P 4 P and so on you
know that there must be two such values
inj for which they are the same because
it is a finite set of points right so
therefore if you choose I though there
must exist some value I there must exist
some value of J okay where I is greater
than J say with without any loss of
generality for which I into P is equal
to j into okay that means if you
rearrange then I minus J into P is equal
to O right so therefore if you say that
s is equal to I minus J and the smallest
set S is called the order of P so then
you know that there must exist some case
for which this I into P is equal to J
okay then so therefore if n 0 is an
empty yard such that Q is equal to n 0 P
suppose there is one such value that is
there is one such value for which n zero
there is once an integer n 0 for which Q
equal to n 0 P satisfied ok so then you
can actually choose any N by adding n 0
with I multiplied by s then this also
will sadly satisfy this equation of Q
equal to NP right because you know that
Q equal to NP is nothing but here n 0
plus I interior the order s that is the
order of the point P and you are adding
p2 are multiplying in P right so if that
is equal to n 0 into P plus I into s P
and what is s P this P is oh right so
what you get is back as in 0 P right and
you know that Q equal to n 0 P is
satisfied
so therefore this has actually holds so
therefore this logarithm is actually
when you are considering this logarithm
of the point Q with the respect of point
P and you are obtaining your
corresponding integer value is actually
a mapping right mapping from what to
what wrapping from two points right Q is
a point P is a point right so there are
two points on the curve say I call it a
point P 1 and point P 2 there are two
points on the curve to an integer n okay
and this empty are you can actually
denote as Z and you can actually choose
it as s said because you know that any
such thing will satisfy that is any n 0
plus I into s will satisfy but we are
actually interested in the least
representative of this class right and
therefore what we choose as the least
difference of the class is either by
this or so essentially this is my the
minimum set right so therefore I can
actually choose so I can actually you
obtain various classes and I'm
interested in this congruence class okay
so therefore that's the way how we
choose this corresponding thing okay so
therefore we are interested in the least
such value okay so we are interested in
actually a yeah sorry this is probably a
more customary thing it said it said
right so do you understand this that is
essentially there can be more than one
solutions to this discrete block Club
but what we are interested in is at
least such well okay so therefore if you
know that the order of the point B is s
we can actually take any value which
satisfies this and we can actually
obtain the corresponding modulus with
respect to s right that also will should
satisfy this equation right so how many
solutions are there there are large
number of solutions you can actually
keep on generating solutions like this
right now the question is how hard is
the elliptic curve discrete log problem
okay see so we have studied in context
to the previous algorithms like in
context to previous RSA when we have
studied el-gamal cryptosystem we
actually do not go much into the crypt
analysis of elgamal cryptosystems but
there are actually algorithms which are
better made for example if you remember
in context to factorization we have
decided discussed about algorithms which
had a complexity of o n to the power of
1 by 4th because if you want to generate
right that if you remember that
algorithms like Pollard's Rho algorithm
so they were quite efficient algorithms
right in order in order to factorize or
rather to find the prime factors of a
given composite number okay so that if
that problem is solved in RSA problem is
also solved all right so therefore now
the question is how hard is the elliptic
curve discrete logarithm problem okay
see for example just so if you remember
the birthday paradox considered as
approach which is similar to the
birthday paradox okay so we know that if
I generate two lists l1 and l2 base
upon say our random choice the values
like j1 to jr. and K 1 to K are so what
I do is that I guess generate J 1 to J
or randomly and all these things are
actually from 1 and P between 1 and P
you choose any arbitrary values ok so
what I do is that I Captain J 1 p j2 P
and so on Little J RP i generate
similarly another list which is based
based built upon like K 1 into P plus Q
K 2 into P plus Q ok and then kr into P
plus Q so if you find that in these two
lists there is a collision ok so then
you know that J u P that is for some U
is equal to kV plus P plus Q so
therefore you can immediately rearrange
and you know that one solution is J u
minus K V that means if I get this list
and if I get this list and then is there
are two such values for which the common
term occurs then you can actually solve
the elliptic curve discrete log problem
right now how difficult or rather what
should be the least value of this value
of R for which you get a collision so
you can actually you know that these
values being from 1 to P there are P
such values and if you apply the
birthday paradox if you set your arm to
be of the order of P to the power of
half or square root of P you know that
you have got a very good chance or very
high probability of finding a collision
right that is the customer about the
paradox approach so therefore you know
that if art is of the order of P power
of 1/2 then you can actually obtain an
elliptic curve discrete log solution
okay and the interesting thing is that
this is probably the kind of fastest
algorithm that has been yet been found
to solve the integral discrete log
problem which has got a complexity of 4
P power of 1/2 okay so there are
algorithms of the nature of something
which is called as index calculus
algorithms which actually are actually
having an order of something solving
when the run time is of the order of P
power of half but whereas for the
previous things like for the discrete
log problem in FP there are much more
advanced and much more faster algorithms
right so if you remember that what was
it I mean you can actually quite easily
find out whether I mean the not easy
together but you can find out if you
want to
tries a large composite number and if we
apply a pollard slow kind of algorithm
then you remember that the complexity of
that was if the factor of that is if any
can be factored as P into Q then the
complexity of that was oh people of the
rupee so and P is of the order of root
in so therefore the complexity was in to
the power of one by four right so that
was a faster kind of algorithm right
similarly but but in the context of each
elliptic curve discrete log problem
there has I mean of the fastest
algorithm which has been found to solve
this elliptic curve discrete log problem
is of the order of P power of half okay
and there are actually developments of
course in the context of elliptic curve
discrete log problem by bringing in the
concepts of pairings okay so first of
all pairings in cryptography were first
actually used to solve the elliptic
curve discrete log problem that is they
were used in that sense in a crypt era
Dixons but after that it was actually
used for the positive sense in
developing ciphers but the first use or
usage of pairings was in the crypt
analysis of elliptic curve discrete log
problems right
so therefore the general comment that we
can make is that the elliptic curve
discrete log problem is probably harder
than the discrete log problem in FP star
okay and the discrete log problem has
actually I mean FP has actually got
faster algorithms that means we can
actually do in elliptic curve discrete
log problem with a shorter key sides
that is the reason why we can actually
do away with shorter key sizes okay so I
can give you one question here that is
which you can take and think upon is
that suppose there is P which is greater
than three which is an odd prime and a
and B both belong to ZP ok so far the
suppose that the equation of this will
be X cube okay so it is X cube plus ax
plus B equal to 0 modulo P has got three
distinct roots in ZP okay so one
question is that prove that a
corresponding group that is G equal to E
Plus is actually not a cyclic group okay
so that is it is not a cyclic
so therefore you remember the definition
of cyclic group that is in this case you
can actually take any generator and you
can immediately apply the addition
operation on that and you should be able
to construct the entire - okay
so therefore the corresponding card of
corresponding order corresponding group
is G equal to e plus where E is defined
as Y square equal to X cube plus X plus
B and you are doing a modulo P operation
okay so the question is that you have to
prove that a corresponding group here is
actually not a cyclic group okay so we
have given you some hints here so the
first thing is that to prove then if you
take a point p1 say call it alpha 1
comma 0
this is actually an order of two so
order of two means what yeah so that
means that if I take P 1 and if I add P
1 with P 1 I should get oh alright so
this is the first exercise which you can
take and if I take P 1 and if I add P 1
with it then I get back oh so for that
you can it's very simple you can see
that you can if I want to obtain the
doubling operation here then I have to
take a differentiation of this you can
actually that there is a small catch
here that is you cannot apply the
doubling equation straight forward
because in the doubling if you remember
in the derivation we had assumed that Y
was not equal to 0 but here your Y is
equal to zero of this point so if I take
a differentiation here 2y dy/dx you know
that it is 3 sorry 2y dy/dx 3 X square
plus a that's a point right so therefore
the dy by DX at the point of say alpha 1
comma zero is not defined because you
are actually dividing by 2 y so that's
just what I call line so therefore the
vertical line will intersect the
elliptic curve and the point O so
therefore 2 into P 1 is actually equal
to that's why its order is 2 okay
so similarly you can actually generate
points like P 2 which is alpha 2 comma 0
and P 3 as alpha 3 comma 0 all of them
have got order of
- right so now if this alpha 1 alpha 2
alpha 3 are distinct roots of these
these 3 equations ok this equation then
you know that alpha 1 plus alpha 2 plus
alpha 3 is actually equal to what from
theory of equations it is equal to 0
because there is no term which is an x
squared term right so therefore alpha 1
plus alpha 2 plus alpha 3 is equal to 0
okay so using this you can actually show
that this P 1 P 2 and P 3 along with the
point and infinity oh actually forms a
group that is it forms a subgroup okay
and the other point to be noted here
that is that this subgroup that is
correspond consisting of P 1 P 2 P 3 and
O so subgroup means first of all you
have to define that it is a closed set
that is what you have to show the other
thing is that this subgroup is actually
not a cyclic subgroup okay that is there
is no generator which will generate all
of them and that is quite simple to
check and if the subgroup is not cyclic
then the group is also not cycling okay
so this is actually a problem from
Stinson okay so therefore this is a
sketch of the solution which you can
complete ok so these are some of the
references
along with have also used the standard
Douglas Stinson's book also as a
reference
okay so next day's topic will be
implementation of elliptic curve
cryptography
you