Implementation of Elliptic Curve Cryptography - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

okay so into this class we shall discuss
about implementation of elliptic curve
cryptography so as we have seen in the
previous classes is that elliptic curves
and elliptic curve cryptography
essentially relies upon point operations
like point addition and point doubling
operations so they are all actually
quite computational intensive operations
right therefore if I want to develop
either a software or a hardware we need
to take some more or there are some
interesting developments how you can
actually implement it in much more
efficiently okay so today's discussion
will be based on this so we shall
discuss about scalar multiplications and
we shall discuss about whether NSP first
or MSP first is approach I mean we will
try to compare between these two
approaches then we will discuss about
Montgomery technique of scalar
multiplication we and developed discuss
about fast scalar one division without
pre computations like before this there
were some people I mean there are some
implementations which were actually
based on pre computed values of suppose
I want to compute lambda P so they were
like some pre computed values where
already stored and then they were
combined to compute the value of lambda
P this is one approach could be like if
I want to compute lambda P then you take
the binary encoding of lambda and you
keep certain values of say maybe 2
lambda 3 or 4 lambda 8 lambda stored and
then you combine them in order to obtain
the value of lambda P okay so they're
actually like scalar multiplications
using pre computer tables right but
there may be applications I mean you may
not even be interested in spending so
much amount of memory and they were they
were quite nice paper I mean it's a nice
paper by Lopes and they have to show how
you can actually do fast scalar
multiplication without pre-computation
so we will study that and we will study
about Lopes and they have projective
transformation to reduce the number of
inversions or finite period versions
which are necessary discuss about the
read about mix coordinates not go much
into details and rather concentrate upon
some parallelization techniques we can
actually accelerate the scalar
multiplication operation okay so let us
go step by stop step so therefore this
is the how how are the broad diagram
of elliptic curve hierarchy looks like
so you can see that the basic elliptic
curve operation is based upon point
multiplication I called it KP that is K
is a scalar and P is a base point and
the other is at least based upon group
operations we have point addition and
point doubling okay and that is again
under langley based upon the finite
field operations like addition
subtraction and inversion and so on okay
so now you see that there are that means
that there are various levels of how
this elliptic curve cryptography
operation works so therefore if I want
to obtain accelerators then I will try
to paralyze these architectures right so
I will try to paralyze the point
multiplication I will try to paralyze
the group operations I will try to
paralyze this underlying arithmetic
operations so therefore what is
important is to understand where are the
scopes of these paralyze asians or how
you can actually obtain these
accelerations right so first first let
us consider it upon how to do this
scalar multiplication operation so there
is a point P and we are interested in
computing K multiplied by P okay so K is
my scalar which can actually be written
as a binary I mean encoded in a binary
format call it K 0 K 1 until ka minus 1
so K M is actually the first time when
one is encountered previous to that
everything is 0 you understand this so
therefore if I want to encode 7 it will
be 1 1 1 you want to encode as in got 5
that is if K is 5 then it is 1 0 1
previous to that it is all zeros okay so
therefore very simple way is what is
known as the double and add algorithm so
what we do is that we take this P and
stored in a temporary register call it Q
and for I equal to M minus 2 to M minus
0 that is the first one right so
therefore we take start from M minus 2
and go till 0 and whenever we see that
we always do a doubling operation and
whenever there is a 1 then we do a q
equal to Q plus P that is the point
addition operation so this in this case
you are actually parsing the scalar
from MSB to the LS this is the least
significant bit and this is the most
significant bit so we are going from MSB
to LSB
so therefore this algorithm is called
MSB first ok so in this case what is the
total number of computations necessary
you see that it records if there are I
mean of the I mean roughly if you just
say that it is M that is a lengthy same
it records roughly if M point doublings
because you are always doing a doubling
operation ok it is actually from M minus
2 to 0 so it is M minus 1 but
approximately I've written it just
throwing away the constant dumb ok any
roughly requires proportional to M point
doublings ok what about the number of
additions required so generally if you
assume a random K the K will have 1/2
number of ones and 1/2 number of zeros
if K is a thought to be a if I consider
the average complexity of this algorithm
so in that case there will be M minus 1
by 2 point additions which are necessary
okay so therefore I need to do so many
number of point additions that is half
number of point additions right that is
enough cost of this algorithm so
therefore you can consider an example if
I want to compute 7 into P I will encode
7 s 1 1 1 so you note that this is the
first time when you have got a 1 so when
you are encoding from MSB then this is
the first one that you are actually
considering ok if it is a 1 then you
have to do not only a 2 into P but also
add that with the corresponding P that
is how to do the doubling as well as you
have to do an addition operation and
next one is again a 1 so again that
means again you are doing a doubling and
add is adding with P that is 2 into 2 P
you see that 2 P plus P is 3 P into 2 is
6 P plus P 7 P so you see that 2
iterations are required the first one is
double and then add that's the principle
okay so first you are doing a doubling
and then you are doing an addition or
accumulation of price so you similarly
if you want to compute 6 P it is 1 into
1 into 0 so in this case you have to do
because of this one you have to do into
2 into P plus P but since this is 0 you
have to do only a doubling operation you
don't need to do the addition operation
right so in this case you see it is 3 P
into 2 which is 6 P right so
that is the MSB first approach of
obtaining the scalar product scalar tom
scalar multiplication similar to this
you can actually actually do an LS B
first algorithm also that is where you
go from K 0 and go to the MSB so in this
case again you see that km is 1 and
these are the corresponding terms
corresponding binary values so now I
want to compute again Q in Q equal to K
into P now for this what we do is that
we actually instead of having one
registered we actually choose two
registers call it you call one of them
as Q and the other one as R so what we
do is that we initialize Q to 0 and our
to the value of P ok now from I equal to
0 to M minus 1 if K is 1 then we add on
to this register Q that is Q is equal to
Q plus R and in the other registered we
are actually doing a doubling operation
ok so here you see that as opposed to
the previous algorithm previous
algorithm we are doing at doubling and
then you were doing an addition
operation so that means the there are
two steps which you cannot actually
paralyze they are sequential steps right
but in this case because you are doing
these operations on two different
registers and actually you are actually
giving more space you are actually
saving time so you can actually paralyze
these two operations and you can do the
accumulation and the doubling in two
different registers simultaneously right
you can do this q equal to Q plus R and
in the other transistor
you can do this R equal to 2 into R
operation right and this you can repeat
for all these values so therefore the
accumulation and doubling can be stored
in separate register on average there
are M by 2 point additions and M by 2
point doublings which are necessary why
so because you are doing the addition
and doubling in the in two different two
separate registers right so therefore
always there is a cost of M by 2 so
therefore you see that you are whenever
there is an addition required so if you
assume that half this K has got half
half one downs then half of the times
you will have that is M by 2 times you
you
an additional operation that is M by to
addition and when you do not need an
addition you need a doubling operation
right so therefore the total time is M
by 2 point additions plus M by 2 point
doubling operations now why it is not n
point doubling operations because the
addition generally will take more time
than the doubling operation so if you
even if you paralyze you can assume that
the addition will actually take more
time so you have to wait since there are
two parallel steps you have to wait for
the longest time right so that is M by 2
point additions and then you have to do
this rest on M by 2 point doubling
operations right so therefore you see
that there is some advantage because you
can actually paralyze these these
algorithm through this ok so therefore
this is the LSB first approach of doing
it so therefore now you see that this is
also can be seen this with the same 7p
and 6p example so here it is 1 1 1 Q is
equal to 0 and R is equal to P now you
see that in 3 time steps you can
actually do this Q plus R and in
parallel you can do this R equal to 2 R
into our operation ok so because this is
a 1 now you are doing LSB first so you
are first starting with this one
these are 1 so you are doing an addition
you are doing a doubling next time you
are again getting a 1 so you are again
doing an addition again doing a doubling
operation here ok next time you are
again seeing your wall you are doing an
addition we are doing an doubling
operation here so there is a result the
register is in the result is in Q
similarly when you are doing 1 1 0 the
first thing is 0 so therefore 0 means
you are not doing the addition operation
so Q is unaltered unaffected ok odd is
doubled so R becomes 2 into R right next
you get a 1 so therefore you add 0 with
2 P that is you add the current value of
Q and the current value of art and it
becomes 2 P you Double R it becomes 4 P
ok next time you add 2 P with 40 because
it is a 1 and you double but this is
inconsequential because the final result
is stored here 6p right so therefore you
see that you can still do the
computation 7p and 6p what in this case
you are actually parsing from the right
and going to the left right so you see
that there are small implications
whether you are doing with
from the left to the right or from the
right to the left which you can use to
your advantage depending upon the
platform where you're implementing your
constants okay
so therefore one example here shows that
if I want to compute 31 P and this is an
MSB first approach and this is the LSB
first approach you see that there is a
significant reduction in that in terms
of the time steps that are required to
do this operation but this cost that you
pay is two registers that's the cost
which you are P okay so therefore so
therefore it I mean we can say that
there is more scope of parallelism when
you are doing or taking an LSB first
approach
alright so now let us actually so this
is a small point about the scalar
multiplication so now let us go into the
implementations of the elliptic curve
point addition and the point doubling
operations so this is a dekappa
generation of the equations that we got
in the first class so this is the
addition of P and Q and P and Q are not
the same so this is the equation of
adding x1 y1 and x2 y2 and if the points
P and Q are same then this is the
corresponding W point similarly the
corresponding Y coordinates are shown
here okay so now the question is how do
we do this operation so here do you see
that point addition and another point
which is to be noted here that is if P
is equal to x1 comma y1 then minus P is
shown as x1 comma x1 plus y1 so how do
you get this minus P is you take this
curve you take any one any point x1
comma y1 and draw a vertical line
through these x1 comma y1 right so
wherever it intersects the elliptic
curve that is the in that is the
negative of okay so you can take this
and you can solve this I mean take a
what what Eagle Claw point and say call
it Y I mean it is a vertical point I
mean what is a line and that you have to
basically simultaneously solve with
these equations and then you can easily
show that the corresponding minus point
is minus P is equal to x1 comma x1 plus
y1 so I am NOT going into the derivation
which you can do yourself okay take it
as an exercise so now I want to add
these two points
I mean P and Q and store the result in
the register R so you note that point
addition and doubling each requires one
inversion and two multiplication
operations so if you observe your
addition and doubling here you see that
you need to do this one by X 1 plus X 2
so what that means that is one inversion
operation and that you need to multiply
with Y 1 plus y 2 in this case if I just
consider the addition operation in this
case you need to multiply with also with
X 1 plus X 3 that is one more
multiplication so note that
multiplications with constants and
multiplication and squarings are
neglected because that I believe that
you can that we will need that we can
also do it without multipliers okay so
the other thing is if you see that
corresponding doubling equation there
also you need to operate this one by x1
so that is one inversion is necessary
similarly the same 1 by X 1 can be used
here also the other thing is the
multiplication with is x3 ok so that is
the corresponding 3 that is unique are
you also required to multiply this with
this y1 so that is another
multiplication ok so that means you need
two multiplications and one inversion
for both point addition and for both
point doubling operations so we neglect
the costs of squaring and addition and
we also neglect the costs of multiplying
with constants okay like here you have
multiplied with B that is neglected ok
so if B is already a pre known value or
fixed value for the curve then you can
actually develop an architecture which
is devoid of multiplication ok now the
first thing which was interesting
behind what Montgomery noticed is that
the x-coordinate of 2 P does not depend
on the y coordinate of P so if you note
that this P equal to Q point a I mean
when you are doing the doubling
operation then the x-coordinate of this
output actually does not depend upon the
y-coordinate right so this was the
important observation that is you see
that the x-coordinate of 2 P you see
that does not depend upon the
corresponding y coordinate that if it
does not depend upon y1
it is only a function of x1 right so
based upon this Montgomery
and this was a very important
observation developed a faster method to
perform the scalar multiplication okay
so this is actually based upon an
invariant property where you say that
there are two points P 2 and P 1 and I
want to compute K into P okay so I
choose another I generate P 2 and P 1 at
each step or at each iteration such that
the difference of P 2 and P 1 is always
maintained to be P ok so I want to
compute this KP so I first of all encode
this in this fashion and I set P 1 as
big P and this P and I set P 2 as 2 P ok
and so you see that P 2 minus P 1 is
what is P and right so therefore what we
do is when we vary from I from L minus 2
to 0 so what is this is the MSB first
approach then if ki is equal to 1 then
what you are doing is that you are in P
1 you are adding that is you are doing P
1 plus P 2 and in P 2 you are doubling
that is you are doing 2 into P 2 but if
this ki is 0 then you are actually
adding in the P to register but while
you are doubling in the P 1 register so
you see that whether ki is 1 or whether
ki is 0 P 2 minus P 1 is always
invariant so you see that P 2 minus P 1
here is 2 P 2 minus P 1 plus P 2 which
is what which is P 2 minus P 1 similarly
here P 2 minus P 1 is also P 2 plus P 1
minus 2 P 1 which is again P 2 minus so
therefore P 2 minus P 1 is actually an
invariant for this algorithm you see
that right so now you are actually doing
this addition and doubling in this
fashion and therefore the idea is that P
1 actually finally stores the value of K
into P okay so one of the implications
of this algorithm then how essentially
and what is the relation I will what is
the efficiency factor I mean how to
implement these operations efficiently
okay so first of all let us see that
indeed it computes what we want that is
the correctness of the algorithm so I
want to compute 7p so therefore first of
all I
choose P 1 as P and P 2 as to P as we
have seen previously and the steps are
because first we start with this one
okay so therefore you see that this is 1
so in P 1 what are you doing you are
adding you are adding P with 2 P you are
getting 3 P what about this P 2 P 2 we
are doubling next time you are again
getting a 1 so again in P 1 you are
adding 3 P plus P 4 P 7 P and P 2 you
are doubling that is in consideration in
this case in this case it is 1 1 0 so
therefore in 1 again you are doing 3p
and 4p like previously but next time it
is 0 so you are actually adding in P 2
so therefore P 2 is 3 P plus 40 which is
7 P whereas P 1 while P 1 is double of P
1 so that is 6 P so again you are
returning P 1 as the result so you see
that the correctness of the algorithm is
still maintained right so therefore you
need P 1 stores the value of K
multiplied by P now what is the I mean
rather why essentially is this efficient
that is the important question right so
another why essentially do we do in this
fashion so therefore that brings us to
this point
topic of fast multiplication and
elliptic curves without pre-computation
that is I am not having any pre computed
values and still I am accelerating the
computation of lambda P ok or K into P
so for that there are certain results
which are important which I try to
discuss here that is suppose so for that
first of all let us observe the
corresponding sums here ok so the sums
of you know that X 3 is equal to so I am
just writing down the results so I'm
adding x1 comma y1 and if I add x2 comma
Y to the corresponding sum is stored as
y 1 plus y 2 divided by X 1 plus X 2
whole square plus y 1 plus y 2 divided
by X 1 plus X 2 plus X 1 plus X 2 plus a
right that is the sum I mean that is the
corresponding sum
x-axis x coordinate and the
corresponding y coordinate is as shown
here as y 1 plus y 2 divided by X 1 plus
X 2 into X 1 plus X 3 plus X 3 plus y 1
okay say for at this point let us just
concentrate on this term that is the
x-coordinate of the result okay so I
want to add this point X 1 and this
point x2y2
so now at this point let us make kind of
restriction also is that let us only be
concerned about elliptic curves which
are all points in characteristic 2 that
is the elements are chosen from GF 2 to
the power of M for any M for some some M
okay so now if I want to obtain the
corresponding sum of this x1 and y1
another x1 y1 and x2 y2 then I can
actually simplify this and I can write
it as X 1 plus X 2 whole square and the
numerator will be as Y 1 square plus y 2
squared Y because 2 y 1 y 2 is is in 0
right here so then you have got here X 1
plus X 2 into y 1 plus y 2 so that
becomes here X 1 y 1 plus X 1 y 2 plus X
2 y 1 plus y 1 y 2 all right plus X 1
plus X 2 whole square all right and the
X 1 plus X 2 whole cube so it is X 1
cube plus X 2 cube plus X 1 square X 2
plus X 2 square X 1 right X 2 square X 1
is it correct so 1 cube plus we are
multiplying this with this right so X 1
cube plus X 2 cube plus X 1 squared X 2
plus X 2 square X 1 plus a multiplied
with X 1 square plus a multiplied with X
2 square right and you note that X 1 Y 1
is a point on the elliptic curve okay so
you choose
you know that if this is your equation
then you know that since x1 comma y1 and
x2 comma y2 are points on the elliptic
curve you know that y 1 square plus X 1
y 1 is equal to X 1 cube plus a X 1
square plus P similarly your Y 2 square
plus X 2 y 2 is equal to X 2 cube plus a
X 2 square plus B right so that means if
you observe now this term then your
numerator becomes you can actually
combine and you see that you have got
like X 1 Y 2 plus X 2 y 1 that is this
term and this term okay plus you can
actually write Y 1 square plus X 1 Y 1
plus X 1 cube plus a X 1 square plus B
plus okay I am adding a be there and y2q
y 2 square plus X 2 y 2
Plus x2 cube plus a x2 square plus B
okay so if you do this then you know
that okay there are some more terms
there it is that X 1 square X 2 plus X 2
square X 1 so this full thing is there
in the numerator right so that means
this term and this term will go to 0
because they are points on the curve and
being in characteristic 2 field these
two terms goes to 0 so you have got X 1
plus X 2 whole square in the denominator
and in the numerator you have got X 1 y
2 plus X 2 y 1 plus X 1 square X 2 plus
X 2 square X 1 is it correct right so
that's your corresponding sum of x1 y1
and x2 comma y2 right so that is the
first result here which says that your
if you take x1 comma y1 and if you take
x2 comma y2 and these are points on the
elliptic curve then x coordinate of P 1
plus P 2 X 3 can be computed as X 1 y 2
plus X 2 y 1 plus X 1 squared X 2 plus X
2 square X 1 divided by X 1 plus X 2
whole square ok
so therefore you remember that the field
has got a characteristic 2 and that P 1
and P 2 are points on the curve so these
are the two things that we have used in
this result ok so therefore you know
that from this that if I if in this
Montgomery's algorithm that we know that
P was maintained to be equal to P 2
minus P 1 that was an invariant for the
Montgomerys algorithm right so therefore
P 2
was essentially the point like x-two and
y-two and one was P 1 P 1 was equal to X
1 comma X 1 plus y 1 I mean minus of P 1
is equal to X 1 comma X 1 plus y 1 right
so therefore the sum of these T's to the
rather of X 2 y 2 and X 1 comma X 1 plus
y 1 is nothing but X comma y right this
is the sum of these two points right ok
so therefore we know that from here your
X ok if you say that this X is equal to
I mean you know that this X you can
actually write this X as X 1 plus X 2
whole square into X 1 y 2 plus X 2 so
you have you can actually use this y
coordinate as X 1 plus y 1 plus X 1 X 2
square plus X 2 X 1 square right
basically I'm adding up these two things
and using the previous result right so
similarly you can add up these two these
terms okay so and if you want the sum of
P 1 and P 2 so I call it P 1 plus P 2
and call it as X 3 comma Y 3 then your X
3 was what we have previously got so I
am again writing that X 1 plus X 2 whole
square is X 1 Y 2 plus X 2 y 1 plus X 1
square X 2 plus X 2 square X 1 this was
1 X 3 so you can add these two equations
where you will get like X plus X 3 is
equal to X 1 plus X 2 whole square and
in the numerator you will see that X 1 Y
2 X 2 y 1 X 1 square X 2 and X 2 square
X 1 all of them will cancel so what you
will be remaining with is only X 1
x2 right so therefore you can actually
write x3 as you can rearrange these
terms and you can express X 3 as X plus
X 1 plus X 2 whole squared into X 1 X 2
right so now you see that if you want to
do this operation then how many you need
to multiply this right so therefore so
therefore the other way of writing this
in an equivalent fashion is like X plus
X 1 plus X 2 whole square X 1 square
plus X 2 divided by X 1 plus X 2 so this
symbol you see that if I can take X 1
plus X 2 whole square then X 1 square
will stay X 2 multiplied with X 1 plus X
2 so X 2 square will be there and the
other term will be X 1 into X 2 right so
you see this sorry this is 1 this is X 1
right so if in this case this X 1 square
and this X 1 square will get cancelled
right now what is the advantage of doing
this in this fashion so how many
inversions do you need to do you need to
do one inversion because you need to
compute 1 by X 1 plus X 2 and how many
multiplications you need to do you need
to multiply with only X 1 you need to I
want to compute this X 1 so I basically
do a 1 by X 1 plus X 2 where is one
inversion I multiplied with X 1 right
that is how many multiplications 1
multiplication and then I need to do a
squaring so how many multiplications I
did one multiplication but here I have
to multiply with X 2 I have to multiply
with X 1 so I needed to multiplication
operation right so you see that it's
quite interesting the same thing but if
we just rewrite and expand a little bit
you see that you are basically saving
the number of multiplication operations
that in
to do okay and so therefore that is your
result to that is if your P power P is
equal to P 2 minus P 1
okay the next coordinate of P 1 plus P 2
X 3 can be computed in terms of the x
coordinate as this so you see that here
whenever you are computing this X 3 that
is when you are you are computing P 1
plus P 2 you are not actually bothered
about the y coordinate you see that
right that means you can do the
operation entirely divided of y
coordinate so previously we are already
noticed one go I noticed that the
doubling was actually divided of the y
coordinate but then here we it was also
used I mean the thing which is used here
is that if you maintain this invariant
that is if P is equal to P 2 minus P 1
then the sum of P 1 plus P 2 is also may
divide of the y coordinate that means
you are not actually operating on to Y 2
coordinates you are actually operating
on only the x coordinates so that means
you need not care about the y coordinate
if you men during this write and that
actually gives you an amount of
efficiency right then you also need to
obtain the y coordinate finally right so
for that this result is used that is if
P is equal to X comma Y and and your P 1
is X 1 comma Y 1 and P 2 is X 2 comma Y
to be elliptic points and assume that P
2 minus P 1 is again equal to P and X is
not 0 then the y coordinate of P 1 can
be expressed in terms of P and the x
coordinates of P 1 and P 2 as follows
okay so here you are actually writing
this in a different way that is you are
writing this as you know that your
invariant is P equal to P 2 minus P 1
right so that's your invariant here so
therefore this you can actually rewrite
as P 1 being equal to P plus P 2 right
you can always write them in this
fashion that means P points where X
comma Y and P 2 was X 2 comma Y 2 and
your P 1
is x1 comma y1 right so therefore your X
so therefore you can actually add this
ok so they wrote something wrong here P
plus p1 right P plus P 1 is P 2 that is
P 2 is X 2 gamma by 2 and P 1 is X 1
comma y1 right so that means you can use
the previous result here to write or
express X 2 so your X 2 is actually
equal to X 1 plus X whole square and you
have got X 1 y plus X Y 1 plus X 1 X
square plus X X 1 square in the
numerator okay so that means this you
can write as so this is your X 2 so
therefore if I want to obtain the value
of x Y 1 if I target this X Y 1 then I
can express X Y 1 as X 2 into X 1 plus X
2 or another X 1 plus X whole square
plus X 1 y plus X 1 X square plus X X 1
square right that is equal to X 2
multiplied by X 1 square plus X square
plus X 1 y plus X 1 X square plus X X 1
square so now you can actually take out
from here you can take a comma of X 1
and you can write it as X 1 X 2 plus X 1
X plus X square plus y okay plus X into
X into X 2
so that is nothing but you're in here X
square into X 2 has been written in this
fashion so X square into X 2 is this
term okay and in the other part that is
X 1 so therefore you see that
here you have an X 1 so it is X 1 square
into X 2 just be written in this fashion
then you have got an X 1 multiplied with
Y which has been written in this and
then you have got an X 1 square X so
that is your this term X 1 squared X and
then you have got an X square X 1 so
that is X square X 1 is this term ok so
these are actually written into factors
like this
the reason is like if you write X 1 and
then now if I add say X 1 X 2 plus X 1 X
plus X square and add X X 2 plus X
square plus y so basically I am adding
here and X X 2 plus X square here okay
and then in the other town
I am also writing X X 2 plus X 2 X 1
plus X X 1 plus so that is another term
which you are adding here okay so do you
see this that this is what these are new
terms so it is X X 1 X 2 so X X 1 X 2
gets cancelled over here okay what is
the other term that is atom is X square
X 1 that is x squared X 1 okay and so
you see that this is the extra term that
is being added over here
right is it okay
so that you can write as if you take X 1
plus X common so you see that here X
Square + X square will get canceled out
okay and okay there is a + y term here
okay so there is a additional plus y
term here so if you see that this one is
X 1 into X 2 plus X 1 into X + X X 2 + y
okay what is this term here X X 2 plus X
2 X 1 plus X X 1 plus y that is the same
down basically right so therefore you
can take this as common and you can
write this as X 1 plus X into X 2 plus X
plus X square plus y plus X into y okay
so therefore now you can actually obtain
y 1 from here you can just take and
divide this by X you should get Y 1 1
okay that is what is written over here
that is y 1 is equal to X 1 plus X
multiplied with X 1 plus X into X 2 plus
X plus X square plus y divided by X plus
X Y by X so that is why okay so that
means that you are always doing whenever
whenever in this model what is algorithm
you are only bothered about the x
coordinates and you are doing it finally
at the end when you need the y
coordinate of the output also you can
apply this equation to get the y
coordinate right so therefore if you
write all these things in the form of an
algorithm then this is the way how you
can do so so you see that here we start
with X 1 equal to X that is the
x-coordinate of the point and what does
this indicate X 2 equal to x squared
plus B by X square what does this
indicate this indicates it is 2p right
and I am only bothered about the
x-coordinate I am not bothered about the
y-coordinate so X 2 is equal to X square
plus V by X square is only the
x-coordinate of twice P right you
remember the original no no no this is
the Montgomery algorithm right so
therefore we had P 1 storing P and P 2
storing twice P right and in this
operation I am only
bothered about the x-coordinates so
therefore here we only store the we
store the corresponding x-coordinates it
is X and this is the x squared plus B by
x squared now what we are doing is that
we have calculating a value of T equal
to X 1 by X 1 plus X 2 ok and then if
this value is 1 then we are doing an
additional operation here the addition
operation is defined only by doing X
plus T squared plus T so that is only
the x coordinate of the corresponding
sum of p1 and p2 are p1 and p2 ok
another an x1 and x2 and here you are
storing the doubling thing and when this
value is 0 here you are doing the
doubling in X world and you are doing
the addition operation in x2 ok and you
see you understand why it is X plus T
squared plus T that is from the result
to right that is from the result to
where you are doing this operation so
this is your T so this is T squared plus
T so you are doing that T squared plus T
only to do the addition operation ok so
finally you need to obtain the
y-coordinate so therefore you can obtain
the y-coordinate by doing this operation
okay so what is the advantage here you
can see I mean what is the number of
inversions multiplications the addition
and squaring required really should
shown here which you can work out ok so
therefore it is like if you want to do
the inversion you see that you are
always doing an inversion operation so
it is 1 by X 1 plus X 2 means that is a
cost of one inversion always and
whatever you do you are always doing an
inversion either here or you are doing
an inversion here so that means it's a
two inversions which are necessary all
right so there is one here and there is
either this one or this one so that is
two inversions multiplied by the number
of times you are doing this running this
loop okay plus one because you are doing
an another additional inversion
operation here similarly you can also
count the number of multiplication
operations here and additions and
squarings ok so you see that here still
you have got a large number of times you
have to do this inversion operation ok
so that means that and you know I mean
that inversion is actually a very costly
step in finite field operations right so
therefore there was in order to reduce
this number of inversions these are fine
their systems were actually converted
into something is called as projective
coordinates okay so that's basically a
three-dimensional space which is being
borrowed to reduce the number of
inversions which are necessary so for
example when n is greater than equal to
128 each inversion is actually like
equivalent to seven multipliers in
hardware design okay that means it's a
there's a lot of cost and therefore if
there is an importance of reducing the
number of inversions so therefore there
was one projective coordinates please
color as a Lopez they have projective
coordinates where XY and z are the three
projective systems and X and the affine
system small X is actually equal to XYZ
and a small Y is written as Y by Z
square okay so that is being written as
this X comma Y comma Z equivalence class
so the motivation is to now replace
these inversions by the multiplication
operations and then perform one
inversion and the end to obtain back the
affine quadrant so what is done in
projective coordinates is that all the
operations of addition and doubling are
done devoid of any inverses they are
done at the cost of increased number of
addition operations okay and increase
the amount of multiplication operations
and finally there is an eye surgery of
converting the output from the
projective coordinates back to the
affine coordinates there we need to do
one more inward step inversion step so
for example here if you remember that in
doubling this was the corresponding
equations in Montgomery Montgomery
system those are the values which are
being shown here that is you need to do
two inverses one general field
multiplication for addition and
squarings if you convert this into the
projective coordinates by the previous
transformations that we have seen okay
then you will see that you actually need
to do zero inverses there are no
inverses necessary but you need to do
increase number of multiplication and
addition and squaring operations
okay so therefore depending upon your
aim is to either show that is the number
of multipliers in your inverses this may
become handy
okay and may help to make your
implementations more efficient okay so
therefore if you convert this entire
system into projective coordinates this
is how the Montgomerys algorithm looks
like okay so here you see that here
have set your excess I mean X I mean x1
as small X Z 1 as 1 and X 2 is X to the
power of 4 plus B and Z 2 is X square
okay so X to the power of 4 plus B's so
you see that X - Lyz - art storing what
I'm storing the double point and here it
is storing the single point now you are
doing if ki is equal to 1 you are doing
in projective coordinates the additional
operations in x1 y1 okay and you are
doing the doubling in the x2 0 okay so
you see that you are not actually
working on the y2 point why because your
Montgomery's algorithm or the one is
technique does not need me to work on
the y coordinate it just needs only the
x coordinate okay then when your ki is 0
then also you need to do the addition
here and the doubling in the x1 z1
register and finally when you have got
the result then you need to convert this
back into the affine coordinates so for
that actually I mean I'm not going into
this but you need to do one more one
inversion at that point is necessary ok
so this is actually straightforward
because this is exactly like in the
previous algorithm you have basically
this step right so see for example you
had y1 as X 1 plus X into so basically
what you do did there was if you see the
y1 equation was X 1 plus X into X 1 plus
X into X 2 plus X plus X square plus y
this was divided by X plus y that was
your Y coordinates right so now your
transformation in your projective
coordinate system is X is equal to X by
Z your Y is y by my Z square ok so if
you do this then what you will write
here is you will take this point so
therefore you see that if you want to do
this conversion
okay you will write here this X is X
this X one point you will write as X 1
by Z 1 okay and your X 1 plus X again
you will write as X 1 by Z 1 plus X X 2
you will write as X 2 by Z 2 plus X
right plus X square plus y right and
that is divided by X and again point Y
is added when y is added right
so therefore this you can actually
simplify and you can write as X plus X 1
by Z 1 and this as X 1 plus X into Z 1 X
2 plus X into Z 2 so you see that there
is a Z 1 by Z 2 at the bottom then you
have got X square plus y and you can
actually write all these Z 1 Z 2 Z 1 Z 2
and minus inverse right so therefore X
into Z 1 Z 2 ok plus it's down Y right
there you see that all these terms X 1
and Y or X 2 and Y or X 1 and Y or X 2
and Y or Z 1 Z 2 are there in the
projective coordinates you are using
this projective coordinates and you are
basically applying only one inversion
operation to finally convert your
projective result back into the affine
coordinates right and the corresponding
x xax thing is very simple because you
just need to divide this by the
corresponding z to obtain the x
coordinate right so therefore the if you
want to obtain X 3 that is a result of
p1 and p1 plus p2 the x coordinate you
just need to divide x1 predictive value
at x1 by z1 and for the Y y coordinate
you need to do more operations actually
you need to do ten multiplications and
one inversion operation to do the five
transformation so if you do a neck to
neck comparison of the affine
coordinates and projective coordinates
this is how it looks likely there is a
mold the inversions are needed used but
they're multiplications and the
additions and the squarings have of
course increased right so therefore
whether you will go for your affine
coordinates or whether you will go for
projective coordinates the PI depends
upon your ice cream ratio that is in
your inverse how many multiplications or
multipliers are there okay so that
actually dictates whether this one is
more efficient or whether this one is
more efficient right so there are I mean
I will not go into this that is there
are some approaches which says that you
actually keep one of the points in
projective coordinates and keep the
other point in fine coordinates so that
is called as mixed coordinate systems so
there these are some equations we have
derived which you can check also offline
that is but in this case the main thing
we pointed out here is that the number
of multiplications are further reduced
squaring is increased a bit but they're
cheap in GF 2 power of L there is a 10%
improvement if a is not equal to zero
and if it's a zero then there is a 12%
improvement so mixed coordinate systems
are at times more efficient than even
the projective coordinate systems
so I'll just finally conclude with some
terrorise comments on paralyzing
strategies on the point doubling and the
point addition operation ok so you see
that in your point doubling so I am
considering the projective coordinates
here so in these are the operations that
you did okay so therefore you just think
of x1 comma y1 what you have done here
is this 30 s you have taken this x1
squared it sees at 1 squared Z 2 is T
into Z 1 square and finally you are
adding these T square plus M square and
this is your double point okay you see
come check ok that is this is exactly
the same as what we did previously so
how many multiplications are necessary
here there is one multiplication
operation a sorry multivision with
constant I am NOT again considering as
multiplication so if I have got one
multiplier then that's sufficient to do
this operation but what about doubling
you see that there are more number of
steps ok so here for example
is one multiplication here is another
multiplication so if I want to do a
paralyzation then I have to and there is
again a multiplication here again a
multiplication here so if I have got two
multipliers then I can actually paralyze
the step and I can't analyze these two
steps also right so therefore depending
upon my resource constraint I can
actually paralyze this point addition
also okay and what will be the final I
mean so if we just see of this
Montgomery's algorithm structure if I
want to paralyze this I can paralyze
this probably at various levels like a
recognizer paralyze this at this level
of KP or I can paralyze the inherent
internal doubling addition doubling and
addition operations
okay that is I can either paralyze level
one all I can paralyze level two okay so
here are some comments like suppose if
we allocate one multiplier to each of M
and an M double one multiplier to each
of a men and M double then we can
paralyze steps 5a and 5b okay so we have
got two multipliers we are allocating
one to the addition and one to the EE
right so you see that here you are
actually doing the addition and then you
are doing the doubling in parallel
because you have two multipliers we have
actually given one multiplier to this
and one multiplier to this and you can
actually doing both of them in
Corcoran's right so what will be the
cycle length requite will be that equal
to the that required for the addition
because addition is more right and you
know that from these steps if you have
got one multiplier it still have two
multipliers then for this you need two
time steps because first you have to do
this then you have to do this or I will
do this and then you have to do this you
can't do these two things in parallel
right similarly here you can do either
this or you can do this you cannot do
them in parallel so how many clock
cycles you need to do 1 2 3 & 4 so you
need to need 4 clock cycles for doing
this and therefore for every time step
you need to do for L so therefore if L
is the number of times you are iterating
this blue you require for L number of
clock cycles nearly forever but suppose
that if you can if you have got like if
you can paralyze the underlying M and M
M double then you cannot paralyze the
level 1 because you have got again a
constant of two multipliers so therefore
it
you can paralyze the underlying aim and
mmm double that means you have actually
given two multipliers to this right
because that's the way how you can
paralyze this then you cannot do the
addition and doubling simultaneously
because you have got a constraint of two
multipliers right because you don't have
three multipliers
right if you had three multiplayer you
could have done paralyze this as well as
perform the doubling and addition in
panel right so now since you have if you
have paralyze this you have to do this
and this in sequence which means for
this you need two clock cycles because
you have paralyze this and you paralyze
this so you get basically you can do
this addition in two clock cycles but
the doubling also will need one clock
cycle and since this doubling and
addition has to be done in sequence you
need three clock cycles to doing this
and this will even iterate and you will
require three L number of times for
doing the entire operation suppose you
have got three multipliers that is you
have got more resource sorry then like
you can actually do this operation in
lesser time you can do that in 12 clock
cycles right so that means you see that
Montgomery's algorithm is highly
parallelizable depending upon your
constraints and your requirements of
power and throughput you can actually
see a spelling mistake here is
throughput so therefore you can actually
make high-performance designs for doing
the scalar multiplications right so
there are a lot of things to consider
and think of all the earth so one of the
things is like there is something is
called comley's cow standardized by nist
or other formats y squared plus XY
called x cube plus ax squared plus 1
over a binary field I can take this
exercise to compute the number of
additions and doubling equations for
points on these curves and again compute
the number of multiplications and
inversions to be performed in a fine
projective and mixed coordinates what we
have seen okay so you can rework this on
specifically these kind of cars where
this constant a is equal to one so here
some of the references how the classic
papers that are followed are this this
Lopez and the hub just published
published in chess 1999 99 and also some
of the other important references I
mentioned here
and the books are standing on this so
next day we will take up the topic of
secret sharing scheme
you